ChapterZero

I spent several days trying to compute how many random rank one sign matrices (each entry in ) you need to ensure that the projection of a fixed matrix onto their span, satisfies with high probability for some fixed.

First I noticed that the easiest way to approach this is to ask what needs to be for to be full rank; equivalently, take Then I noticed that since (by the SVD), this is equivalent to asking when is full rank.

My first approach, to bound the moments of using symmetrization and the trace method to reduce to estimation of , then Markov's inequality to get a tail bound, was promising at first. Since each where and are uniformly distributed random sign vectors, a lot of cancellation occurs, and basically you're left with a counting problem (count which terms in the expectation don't vanish). Unfortunately, this counting problem's a tough nut to crack, at least for me--- attempting to do so is what led me to the nasty recursion I mentioned in a previous post.

Then I came across Recht's paper, "A Simpler Approach to Matrix Completion", in which he proves the following Noncommutative Bernstein inequality:

Let be independent zero-mean random matrices of dimension . Suppose and almost surely for all Then for any

(apparently related Operator Bernstein and Vector Bernstein inequalities are provided in Gross’s “Recovering low-rank matrices from few coefficients in any basis.”)

With this tool, the problem’s trivial: take . Then and by plugging through the calculations, when

is small, so is full rank with high probability.

I’m satisfied with the sharpness of this estimate for : the smallest any collection of matrices spanning could be is , and it seems unlikely that with the restriction of them being rank sign matrices, you’d easily find such a collection of random matrices. The factor seems like a reasonable price to pay; in fact, because of the coupon collector phenomena, maybe it’s the same price you’d need to pay for a collection of random matrices selected from the standard euclidean basis matrices. In that light, this is an unexpectedly good result.

Possibly relevant posts:

• One direction in Khintchine’s inequality for Rademacher sums (9/26/2008)
• A lower bound on the norm of a useful class of matrices (1/12/2009)
• Is uniqueness important? (2/17/2010)

Came across this at Raving Black Lunatic. What does it say about me that the first thing the sung portion made me think was that this would be perfect on the soundtrack of one of the Faustian Supernatural episodes?

Possibly relevant posts:

• Meet Sade (if you haven’t already) (2/25/2010)
• computer Business (5/19/2003)
• Finding a barbershop (4/2/2007)

A fellow student asked me that question today, and I came up with the following answer: Clearly the top eigenvalue is continuous, as it’s just the norm. Then by writing , the sum of the top eigenvalues of , as the SDP

we see that is convex (since a function of the form , i.e. the supremum of linear functions, is convex). Since a convex function on an open set is continuous, we see that is continuous on the positive semidefinite cone, so is continuous on the same set also.

Another interesting question: are the eigenvalues of a general square matrix continuous w.r.t. to its entries? I believe that’s the case, because we’re talking about roots of polynomials, after all, but I don’t know a simple argument off the top of my head.

Possibly relevant posts:

• Semidefinite program from the norm of a PSD matrix (1/21/2010)
• Spectral Mapping Theorem (6/14/2006)
• What good are eigensystems? (9/16/2005)

I’m within of having a new roommate, so naturally I’m planning what I’ll do with the extra $625/month I’ll be saving. Guffaw. The first two months are spoken for already— it’s past time for new glasses, and I haven’t paid off my Caltech dining account in several months—, then I’ll start saving up to get a car, since it looks like I’m going to be here another 3 years or so. After that, I dream of actually adding to my savings account for the first time in over a year.

Possibly relevant posts:

• (Not) Getting Paid (11/7/2003)
• Banking and Rolling (10/31/2003)
• The one-month gap (7/27/2006)

I’ve “reduced” a problem to solving this recursion:

This looks nasty, and certainly beyond my experience. Any ideas on how to proceed? I guess I could try Z-transforms, but … just yuck.

Possibly relevant posts:

• Linear Recursion Equations (11/24/2005)
• A failed attempt to use an SDP to find a nonorthogonal factorization (1/17/2010)
• Spherical Mean Value (6/6/2005)

One of the reasons why I use Matlab more than Mathematica is Matlab supports convenient convex optimization via the open source CVX package, while Mathematica doesn’t seem to have any support even via (open source) third party packages for convex optimization.

Now it seems I’ve found a relatively easy way to rectify this, by interfacing Mathematica with the CVXOPT Python package using Pythonika. At least under Ubuntu, this was a hasslefree process: apt-get python-cvxopt, then download and compile Pythonika. The only modifications that I needed to make to the Pythonika makefile were to add a ‘-lrt’ linker flag and point to the correct python version and the correct Mathematica Linker library. Then I was able to use CVXOPT to solve a linear program from Mathematica!

CVXOPT doesn’t seem to provide the same type of natural mathematical language interface as CVX does, and I’m not sure how flexible/convenient the interface between Python and Mathematica provided by Pyhtonika is, but this is an interesting development.

Possibly relevant posts:

• CVX in Mathematica via Mathematica <-> Java <-> Matlab? (9/1/2009)
• PyPI package basicCAS (7/24/2005)
• User directory python package installation (3/21/2007)

One idea for getting sign decompositions of a matrix, inspired by Grothendieck’s inequality (the dual formulation) is to get a factorization which realizes and then round the entries of to signs somehow, take to be an appropriate scaling matrix, and use as your approximate sign decomposition of .

You can use this as the primitive step in a greedy algorithm, and get pretty good results (if! you use least squares to calculate )– I implemented this method, simply replacing the entries of with their signs–, but it’s not a particularly smart way of getting sign decompositions. For one thing, you could probably equally as well use random sign matrices , because if you use least squares projection, you’re guaranteed that with reasonable probability at each step (take this with a grain of salt: I think this is easy to show, but I've not checked that it's true), which is all that you can hope to say even if you use the from the decomposition. That is to say, there's nothing inherently special or useful about the decomposition.

To drive home the point, first notice that , so . Therefore we can find a wide range of factorizations achieving : take to be any orthonormal matrix. So there's definitely not anything special about the factors, or the signs you'd round them to, in the general case.

Second, and more importantly, it seems difficult to prove anything about the rate of convergence of these types of greedy algorithms. And (this is just a gripe, because even a factorization corresponding to can be far from sparse), although the factorizations I've seen returned with my particular greedy scheme have reasonably many terms, there's no kind of guarantee of sparseness.

Possibly relevant posts:

• Factorization norm details (2/9/2010)
• An observation on the norming functionals of the norm ball (2/24/2010)
• Is uniqueness important? (2/17/2010)

Update: The dual SDP for can be more simply written as

subject to
,

So it’s surprising that the which solves this seems to be in the 1/2-ball. It’s easy to see that this ball is included in the feasible points, but no reason to think that it is the entire set of feasible points.

I spend mucho time deriving and checking this duality, then implementing it in CVX, so I record it here so hopefully I don’t have to redo this (I realize I could’ve looked this up, but the point is to derive it so I have a better chance of remembering it myself):

The dual of the SDP s.t. , . is the SDP s.t. . ,

In particular, this implies the dual of the SDP I mentioned before gives is the SDP

s.t. , ,

where I decomposed as follows

If , then and its components break down as follows: , , , , , and

As you can see, this is an unwieldy SDP to write out, but it has its benefits as a method for calculating . Specifically, I believe that is a matrix in the unit ball which achieves :

Numerical experiments indicate this is so, but I’d like to establish it. Here’s some CVX code to test this out (mostly this is just here– as is this entire post and all posts relating to my research– for archival purposes):

% solve the dual SDP for a random matrix
A = randn(20,20);
[n,m] = size(A);
cvx_begin
    variable s(n+m);
    variable lambda(n+m+1, n+m+1);
    variable Z(n+m+1, n+m+1) symmetric;
    maximize( trace( lambda * [zeros(n) A zeros(n,1); A.' zeros(m,m+1); zeros(1,n+m+1)] ));
    subject to
        s >= 0;
        Z == semidefinite(n+m+1);
        [diag(s) zeros(n+m,1); zeros(1,n+m) -ones(n+m,1).'*s] - ...
            [zeros(n) lambda(1:n, n+1:n+m+1); ...
             lambda(n+1:n+m, 1:n) zeros(m) lambda(n+1:n+m, n+m+1); ...
             lambda(n+m+1, 1:n+m) 0] + diag([zeros(1,n+m) 1]) - Z == 0; 
cvx_end
B = lambda(1:n, n+1:n+m);
% the solution to the dual SDP, the primal SDP, and  (lambda_2, A) (inner product) should
% all be the same
[cvx_optval gamma2norm(A) trace(2*B.'*A)] 
gamma2dualnorm(2*B) % check 2lambda_2 is in the gamma2dual norm ball

Possibly relevant posts:

• Trace dual of the norm (1/19/2010)
• Equivalence of the norm and the norm (1/27/2010)
• Estimation of the norm using an SDP (1/27/2010)

Sade is one of those artists I heard about constantly growing up, (you know how black people get about their Saw-day) so it’s kind of odd that I just started listening to her for real last week– growing up, of course I was familiar with “The Sweetest Taboo” and “Smooth Operator”, but I couldn’t say I knew she sung them. The title track from her latest album, “Soldier of Love”, is what caused me to start paying close attention. It must be that I needed to spread my musical wings before I could appreciate her style of music.

Anyhoo, here’re some of my favorite songs by her (if nothing else, check out “By Your Side”):

You is welcome, kinfolk!

Possibly relevant posts:

• release the stars? (5/22/2007)
• Brandi Carlile (10/9/2008)
• Canzoni Stonate (5/27/2007)