ChapterZero

I’ve often been asked how I feel about death. (Because, as you know, if you don’t believe in an afterlife, then you must be terrified to die). A couple days ago, I was listening to Poses and reencountered this gem, “In a Graveyard”. I love the piano, but this is one of his songs that I fell in love with just for the lyrics. It pretty much captures my attitude towards death. Death can be good, something to be desired even: can you imagine what it’d be like to be doomed to live forever? To put up with all the foibles of humanity forever? Much better to live a full life and then exit, stage left. Life is a struggle, death is the cessation.

Wandering properties of death
Arresting moons within our eyes and smiles
We did rest
Amongst the granite tombs to catch our breath

Worldly sounds of endless warring
Were for just a moment silent stars
Worldly boundaries of dying
Were for just a moment never ours
All was new
Just as the black horizons blue

Then along the bending path away
I smiled in knowing I’d be back one day.

Possibly relevant posts:

• Rufus in the morning (4/2/2007)
• Two Unsatisfactory Theories of Government (10/4/2002)
• The joke (2/7/2005)

In some Hilbert space, let be a unit ball polytope of some norm and be the unit ball of its dual norm. Is it the case that for every face in there is a vertex of which defines a normal on that face, and vice versa?

I just looked up this stuff, so I barely know what a face is, much less how to tackle this problem right now. My intuition comes only from the knowledge that the dual of the ball is the ball, in which case it’s easy to see that this is the case.

Another question: what are the vertices of the and norm balls? (Are these balls even polyhedral? I think so.)

Possibly relevant posts:

• Equivalence of the norm and the norm (1/27/2010)
• Trace dual of the norm (1/19/2010)
• Some norm stuff (10/1/2007)

Update: This is utter bollocks, but I’ve yet to get around to correcting it.
Continuing in the vein of the previous post, we have that , so if we’re interested in approximating (which looks like it’s hard to compute exactly), then we’d find it useful to be able to compute . It turns out this is easily done with an SDP when is strictly positive:

Then . I’m not sure what happens if isn’t full rank, and this definitely won’t work if is not positive semi-definite.

Possibly relevant posts:

• Trace dual of the norm (1/19/2010)
• A failed attempt to use an SDP to find a nonorthogonal factorization (1/17/2010)
• Semidefinite program from the norm of a PSD matrix (1/21/2010)

It turns out that the norm ( the trace dual of the norm, explicitly given as ) is equivalent to the factorization norm, which is defined as Note that constraining the norm constrains the Euclidean norms of the rows of and

A quick proof relies on Grothendieck’s inequality, which more or less states that

If is a real matrix, then for every choice of unit vectors in a real Hilbert space,

where is an absolute constant.

Note that the trace dual norm of is

where the supremum is over all choices of lengths for .

Therefore so (it’s easy to check that if then and that )

To show the other direction, , observe that

since the second maximum is taken over all lengths for

Putting the two inequalities together,

As an aside, note that now we have the terminology, we can more concisely write Grothendieck’s inequality as

If is a real matrix, then

Possibly relevant posts:

• Trace dual of the norm (1/19/2010)
• Some Schatten norm stuff (6/17/2008)
• Convex set questions (1/28/2010)

I realized that I’ve been attempting to do greedy approximation in the set of symmetric matrices using the “dictionary” without checking that this is indeed a dictionary: is the closure of the span of this set the set of all symmetric matrices?

As someone just pointed out, this is obviously not the case, since the diagonals of symmetric rank one sign matrices are constant. Darn (and don’t I feel stupid). Ok, I guess I’ll have to settle for greedy approximation with the dictionary

Maybe that original dictionary of symmetric rank one sign matrices is a dictionary for the Hilbert space of symmetric matrices with constant diagonals? I don’t have time to think about that. Doesn’t seem bloody useful: you’d only be able to apply this to covariance matrices of equivariant variables.

Possibly relevant posts:

• CVX implementation of Alon and Naor’s SDP for approximating the cut norm (infinity to 1 operator norm) (1/27/2010)
• A research problem, in matrix completion (8/7/2009)
• A failed attempt to use an SDP to find a nonorthogonal factorization (1/17/2010)

Surprisingly, I couldn’t find this in an Internet search, so I implemented the algorithm using CVX.

%% [X,Y,VAL] = INF1NORM(A) provides a probabilistic lower bound on the
% infinity->1 operator norm of A, to within a guaranteed factor, in
% expectation.
%
% (since the quality of the approximation is only guaranteed in
% expectation, you should call several times and retain the highest VAL and
% the corresponding X,Y)
%
% given a positive semidefinite matrix A, approximates the infinity->1 
% operator norm of A to, on average, within a factor of at least 0.56 and 
% returns the approximation as VAL. X is a sign vector satisfying 
% VAL = X.'*A*X; Y=X.
%
% if A is not PSD, returns an approximation that is on average within a factor 
% of at least .27, and X,Y are sign vectors satisfying VAL = X.'*A*Y;
%
% Reference: Alon and Naor. Approximating the Cut-norm via Grothendieck's
% Inequality.
 
function [x, y, val] = approxinf1norm(A)
 
[n,m] = size(A);
if n==m && all(eig(A) > 0)
    cvx_begin
        variable W(n,n) symmetric;
        maximize(trace(A*W));
        subject to
            diag(W) == ones(n,1);
            W == semidefinite(n);
    cvx_end
 
    G = randn(n,1);
    R = chol(W);
    x = sign(R.'*G);
    y = x;
    val = x.'*A*x;
else
    cvx_begin
        variable W(n+m,n+m) symmetric;
        maximize(trace([zeros(n,n) A; A.' zeros(m,m)]*W));
        subject to
            diag(W) == ones(n+m,1);
            W == semidefinite(n+m);
    cvx_end
 
    G = randn(n+m,1);
    R = chol(W);
    U = R(:, 1:n);
    V = R(:, n+1:end);
 
    x = sign(U.'*G);
    y = sign(V.'*G);
    val = x.'*A*y;
end   
 
end

Possibly relevant posts:

• Semidefinite program from the norm of a PSD matrix (1/21/2010)
• Trace dual of the norm (1/19/2010)
• A failed attempt to use an SDP to find a nonorthogonal factorization (1/17/2010)

I watched half of the premiere for Spartacus: Blood and Sand last night. I didn’t get any further because I’m just not that into it: the storyline is not at all original— to be fair, I don’t think it’s reasonable to expect the show to shine until the stage has been set for political machinations— and the CGI is horrible. At some point I’ll finish watching the premiere, and may even continue to watch the series, just because a red-headed Xena Lucy Lawless seems to be on the cast.

As I expected, there were several pointless sex scenes. It was the kind of sex that in better shows, is implied and not shown, not because of prudishness, but simply because its presence doesn’t add to the show. It caught my attention that the legate performed cunnilingus on his wife; if I recall correctly, the Romans looked down on oral sex. I’m sure there were other more important historical inaccuracies, but that one popped out at me. I looked up the Roman attitude towards oral sex, just to be sure, but I couldn’t find a definitive statement about the time period Spartacus is set in: but at least in the time period of Pompeii, oral sex was definitely socially taboo.

The whole Roman-attitude-towards-sex thought stream got me thinking about the song “Origin of Love” from the soundtrack to Hedwig and the Angry Inch. It’s a musical adaptation of a speech Aristophanes gave in Plato’s Symposium (which takes liberties); and yes, I’m aware that makes this Greek, not Roman.

Here’re animated versions of the song and the speech it’s based on:

Possibly relevant posts:

• I’m a bad black person too (8/26/2008)
• The death of Purgatory Limbo (4/27/2007)
• Convocation (9/17/2006)

Hashes are one of my favorite types of meal to make; they’re incredibly versatile. I made one today to use up the remnants of a rather bland chicken I roasted earlier in the week. Here’s the recipe:

Ingredients:

• 1/3 a roasted or baked chicken, shredded
• turkey pastrami, finely cubed (about 1/2 as much as the chicken)
• a stalk of celery, finely chopped
• a medium red bell pepper, finely chopped
• 4 serrano peppers, seeded and finely chopped
• half a tsp of garlic, chopped
• slightly more cubed cooked yukon gold potatoes than meat, by volume
• 3/2 tsp. of S-bend hot sauce (or some other mustardy, vinegary type hot sauce)
• a good barbecue sauce (one that’s not too strong or eccentricly flavored; probably a mustard based sauce is best, but I used what I had on hand: Stubb’s original barbecue sauce)
• salt, italian seasoning, and paprika
• olive oil

Instructions:
Add just a little bit of olive oil to a pot (you don’t want the hash to be oily, since you’re adding barbecue sauce, so use just enough to keep the meat and vegetable mix from scorching before it starts to release its juices) and sautee the garlic. Dump in the vegetables and meat mix, season with salt, paprika, and italian seasoning, and heat while mixing until about a minute after the vegetables start releasing their water. Incidentally, mixing helps shred the chicken further. Mix in the barbecue sauce and hot sauce and let heat through. Mix in the potato, being sure to coat each chunk, and heat for a couple minutes.

I ate some immediately after cooking, and was disappointed — not only could I taste the red pepper and celery as individual components, the hot sauce also overpowered the rest of the flavoring, and the potatoes didn’t pick up the seasoning. I just had some again, and it was much better this time around. Apparently you have to let this hash sit and cool so the flavors blend. You might also want to add some onion: I didn’t because I was too lazy to do any more chopping.

Update: Pictures!

chicken and potato hash before adding bbq sauce

chicken and potato hash with bbq sauce

Possibly relevant posts:

• My favorite tuna recipe (2/7/2007)
• Spicy Pesto Lasagna (6/3/2009)
• Goat cheese, arugula, and chorizo (9/14/2008)

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)
• Equivalence of the norm and the norm (1/27/2010)
• A failed attempt to use an SDP to find a nonorthogonal factorization (1/17/2010)