ChapterZero

I’m looking at a nonorthogonal factorization problem: given a symmetric matrix , write it as where the columns of all have norm less than one, is diagonal, and are chosen to achieve , where the minimization is taken over all such .

Why do I care about this problem? My advisor suggested it when I mentioned my interest in copositive programming, because it’s likelier that I’ll be able to prove something in this area than in that— the positivity constraints in completely positive programs make them NASTY.

What’s the usefulness of such a factorization? For one, it would allow statisticians to use nonorthogonal factor models, and for two, it might be useful (if you generalize it to the case ) for collaborative filtering type problems like the Netflix problem: here would represent categories, would represent user weights, and would represent the universal importance of the factors.

The “norm” is like a dictionary norm, where the dictionary is a subset of the rank one matrices– minimizing the norm corresponds intuitively to minimizing the complexity of the explanation of . Note that the number of columns of aren’t specified. My advisor hinted that you can assume this norm is achieved when is square — I have no idea why that should be the case. Two more interesting questions: why use the norm, and why constrain the norm of the columns of ? I don’t think, as has been suggested to me, that the norm is there for its sparsity promoting properties, since one would always expect to have no zeros (since we could just drop the columns of corresponding to zero entries on ‘s diagonal).

I attempted using the following SDP to find the desired factorization:

Here’s a CVX formulation:

n = 3; % size of A
k = n; % number of columns in G
 
% construct an example so I know a decomposition exists
Gorig = randi(10, n, k);
Dorig = diag(randi(10, 1, k));
A = Gorig*Dorig*Gorig.';
 
% try to find the best decomposition for this example
cvx_begin
    variable Dpos(k,k) diagonal;
    variable Dneg(k,k) diagonal;
    variable G(n,k);
    minimize sum(inv_pos(diag(Dpos - Dneg)))
    subject to
        [A,   G,         zeros(n, n+k); ...
         G.', Dpos+Dneg, zeros(k, n+k); ...
         zeros(n, n+k),   -A , G; ...
         zeros(k, n+k),   G.', -(Dpos+Dneg)] == semidefinite(2*(n+k));
         G < = ones(n,k);
         G >= -ones(n,k);
cvx_end

Unfortunately, this doesn’t work in practice: CVX says the program is infeasible. Obviously it’s not, since I explicitly constructed the example so there’s at least one feasible point. The moral is that just because you can write something as an SDP doesn’t mean you can solve it: rewriting as and isn’t efficient enough.

Update: Nope, the moral was that I should refresh my linear algebra. Obviously a matrix can be psd only if its diagonal blocks are, and is nsd, so the program is infeasible. (in forming the program, I forgot that not only must the Schur complement be positive, the top principal matrix must also be positive).

Possibly relevant posts:

• Trace dual of the norm (1/19/2010)
• Semidefinite program from the norm of a PSD matrix (1/21/2010)
• K-means as a matrix optimization problem (1/9/2010)