ChapterZero

A colleague and I are now looking at a generalization of the problem from the previous post: Let be a collection of rank one sign matrices. How large does need to be for to span a -dimensional subspace of
Our idea was to note this is equivalent to asking when

has [...]

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 [...]

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’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)
Spherical Mean Value (6/6/2005)
A failed attempt to use an SDP to find a nonorthogonal factorization (1/17/2010)

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 [...]

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 [...]

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 [...]

Here’s a nice observation due to a colleague of mine: if is the sign factorization of corresponding to , and we take , and is an extreme point on the unit ball satisfying , then

so each is either 1 or 0.
Thus, for each rank one sign matrix in the [...]

I’ve found a tentative algorithm for sign factorization. I’ve only tested it on random matrices (generated using rand and randn) in Matlab– as opposed to theoretically verifying that it holds, or even testing on real datasets– so it may turn out that it just works with high probability for random matrices generated in those particular [...]