Meet Sade (if you haven’t already)

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:

Feb 25th, 2010 | Filed under General
Tags:

An observation on the norming functionals of the (\infty,1)^\star norm ball

Here’s a nice observation due to a colleague of mine: if B = UDV^t is the sign factorization of B corresponding to \|B\|_{\infty \rightarrow 1}^\star, and we take D \geq 0, and  A is an extreme point on the \infty \rightarrow 1 unit ball satisfying \|B\|_{\infty \rightarrow 1}^\star = \langle A, B \rangle, then

 \displaystyle \|B\|_{\infty \rightarrow 1}^\star =\sum d_i \langle A, u_iv_i^t \rangle \leq \sum d_i \max_{\|v\|_\infty, \|u\|_\infty \leq 1 }  v^t A u = \sum d_i = \|B\|_{\infty \rightarrow 1}^\star

so each \langle A, u_iv_i^t \rangle is either 1 or 0.

Thus, for each rank one sign matrix in the decomposition of B, \langle A, u_iv_i^t \rangle = 1 . Inteeeeresting…

Possibly relevant posts:

Feb 24th, 2010 | Filed under Mathematics
Tags:

Any good book suggestions?

It looks like I might soon have some spending money. I haven’t gone on a fiction buying spree in a while. Any suggestions? I’m going to pre-order The Desert Spear, because Warded Man was too awesome for me to miss out on the sequel, but other than that, it’s up in the wind. I’ve been out of the sci-fi/fantasy book loop.

Looking for suggestions… I’d prefer one offs and completed series over incomplete series.

Possibly relevant posts:

Feb 23rd, 2010 | Filed under General
Tags:

A tentative (no theoretical analysis) sign factorization

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 ways … but hey, that’d be a result.

The error bound looks to be something like \| A - \hat{A} \|_{\text{F}} \leq c(A)^p\|A\|_{\text{F}} where \hat{A} is the sign matrix factorization and c(A) depends on the size of A (it may also depend on \|A\|_{1 \rightarrow \infty}), and the integer p represents the number of times you do a greedy type recursion.

Fingers crossed! as I’m off to attempt an analysis.

Update: Oops, it seems you can’t get that c(A)^p factor arbitrarily small.

Possibly relevant posts:

Feb 22nd, 2010 | Filed under Mathematics
Tags:

Best sign vector

It seems reasonable that
 \argmin_{s \in \pm^n} \mathbb{E}_x | \langle s, x \rangle - \langle u,x \rangle |,
where x is uniform over the unit sphere, is given by the sign vector of u.

Thankfully, I don’t really need to know this, but it’s interesting to ponder. The proof might be simple if you use the square of the absolute value.

Possibly relevant posts:

Feb 22nd, 2010 | Filed under Mathematics
Tags:

Two talks in one day

I gave two talks on Friday. The first was a rehash of the talk I gave at the ACM tea; this time I gave it at a lunch meeting for EE grad students. It was horrible: the students looked like I poleaxed them and they were waiting for their throats to be cut. It wasn’t until after, when my office mate asked me to refresh his memory on the Frobenius norm that I realized just how unsuitable my presentation was. The one EE course I sat in at here gave me the impression that the EE students would have a firmer grasp of linear algebra than the applied math students, but apparently that’s far from the case. So, lesson learned: make sure you know your audience!

The second was a new talk for the ACM tea, on the matrix complexity/decomposition norm stuff I’ve been looking into for the past several weeks. I didn’t start prepping the presentation until after the lunch meeting, so although I had intended to show an application of the \gamma_2 norm to the matrix completion problem, the presentation I knocked out ended up covering a lot less. This turned out to be boon, since I still had enough material for a very interactive 45 minute talk; also, to be honest, the matrix completion thing is more of a red herring than a practical application.

I first presented a rather abstract motivation for considering the sign matrix decomposition: you can consider it as giving a measure of the complexity of the matrix. Applications to statistics or data analysis are more practical, but given that I don’t have any even conjectured at this point, I thought it’d be less distracting to give a clear albeit abstract motivation. Then I introduced the nuclear norm, and the probability that it’s hard to actually compute it, much less to find a corresponding decomposition— and I really should try to verify this, or check that it’s already known. Then I introduced the relationship to the \gamma_2 norm via Grothendieck’s inequality and the dual inequality. This was the fun part: just as Alon-Naor provide a computational (SDP) implementation of Grothendieck’s inequality to under-estimate the \infty\rightarrow 1 norm, the SDP for the \gamma_2 norm is an implementation of the dual inequality which over-estimates the nuclear norm.

If and when I crack the sign decomposition problem, I’m going to do a follow-up talk.

Possibly relevant posts:

Feb 20th, 2010 | Filed under General, Mathematics
Tags:

Is uniqueness important?

We’ve been trying to find rank one sign matrix decompositions for arbitrary matrices: A = UDV^t where U,V are sign matrices of conformal dimensions, and D is diagonal.

Pretty much, my advisor seems be aiming for any such sign decomposition, but I’m uncomfortable with that. Experimentally, I’ve constructed matrices as sums of 10 randomly weighted sign matrices, and found that just taking any decomposition (I used basis pursuit to find one) can give you about half as many possible rank one matrices having nonzero coefficients. So, if A was n \times n with n = 5, you might get 128 out of 256 rank one matrices contributing to A. (I counted uv^t,  (-u)v^t, u(-v)^t, and (-u)(-v)^t as the same matrix, so there are 2^{2n-2} unique rank one sign matrices in my dictionary).

This says two things to me: 1) we need to somehow be choosy about the decomposition we aim for, to ensure it has nice properties in some sense, even if it doesn’t give the holy grail of sparse representation, and 2) in this context, we shouldn’t think that representations whose \ell_1 coefficients are minimal are remotely similar to the sparse representations. The latter point is because the dictionary in this case (of rank one sign matrices) definitely doesn’t satisfy a RIP.

Possibly relevant posts:

Feb 17th, 2010 | Filed under Mathematics
Tags:

An interesting simple algebraic fact

Did you know this?

Let \varphi_0, \varphi_1, \ldots, \varphi_n be linear forms on a linear space (without any topology). Then the following are equivalent:

  1. \varphi_0 \in \span\{\varphi_i\}_{i=1}^n;
  2. \text{ker} \varphi_0 \supset \cap_{i=1}^n \text{ker} \varphi_i.

Can you prove it?

Possibly relevant posts:

Feb 13th, 2010 | Filed under Mathematics
Tags:

Meet Fink

I’ve had “Distance & Time” and “Sort of Revolution” looping in my mp3 player for the last two weeks, so I thought I’d share the wealth. I couldn’t decide between the following songs. They’re all slices of heaven.







Possibly relevant posts:

Feb 11th, 2010 | Filed under General
Tags: