ChapterZero

Update: Ok, it turns out this isn’t true. You get a nice upper bound, but not the exact operator norm. Last night when I tested on three random matrices, the program gave the operator norm (it works with the example matrix below), but this morning none of the random matrices I’m trying work. Weird

Learned something interesting today: it seems that the operator norm of a PSD matrix can be found exactly, using a semidefinite program. This is unexpected, because for general matrices that norm is NP-hard to compute.

Consider the primal program defining the norm of a positive matrix :

The dual program is

I wasn’t expecting strong duality to hold, since the primal program is not convex, but from experiments it seems that it does. Tomorrow I’m going to review the conditions for strong duality and see if I can prove it does hold.

Unfortunately, there’s no easy way to go from the semidefinite program to a specific vector of signs that achieves This is what I really need: the primal problem came up when I considered greedily approximating in the form of a sum of low rank matrices where . The projection step where you find the low rank matrix most collinear with the current residual is exactly the primal problem above.

All you know about an optimal from the primal problem is that assuming strong duality holds.

Since I love cvx, here’s a little test case:

% the infty->1 norm of this matrix is 6292 a la this Mathematica snippet:
% Max[# . A . # & /@ Tuples[{-1, 1}, n]]
A = [381,59,-18,33,100,-4,-61,-6,6;
    59,220,-46,22,4,-6,-18,93,-10;
    -18,-46,323,102,25,-130,119,-10,14;
    33,22,102,194,-154,-125,11,-8,-108;
    100,4,25,-154,320,168,0,153,137;
    -4,-6,-130,-125,168,257,-93,135,101;
    -61,-18,119,11,0,-93,140,-32,16;
    -6,93,-10,-8,153,135,-32,390,37;
    6,-10,14,-108,137,101,16,37,283];
 
cvx_begin
    variable lambda(9);
    minimize(sum(lambda.*ones(9,1)));
    subject to
        lambda >= 0;
        diag(lambda)-A == semidefinite(9);
cvx_end

Possibly relevant posts:

• Trace dual of the norm (1/19/2010)
• Dual of an inequality and equality constrained SDP (2/26/2010)
• Equivalence of the norm and the norm (1/27/2010)