ChapterZero

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:

release the stars? (5/22/2007)
Brandi Carlile (10/9/2008)
Canzoni Stonate (5/27/2007)

No comments

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 corresponding to $\|B\|_{\infty \rightarrow 1}^\star$ , and we take $D \geq 0$ , and 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 , $\langle A, u_iv_i^t \rangle = 1$ . Inteeeeresting…

Possibly relevant posts:

Equivalence of the $\gamma_2$ norm and the $\|\cdot\|_{\infty \rightarrow 1}^\star$ norm (1/27/2010)
Trace dual of the $\|\cdot\|_{\infty\rightarrow 1}$ norm (1/19/2010)
Factorization norm details (2/9/2010)

No comments

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:

Fiction interests (6/13/2005)
Acquisitions (9/30/2009)
Twilight zone for book ordering (8/15/2006)

No comments

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 (it may also depend on $\|A\|_{1 \rightarrow \infty}$ ), and the integer 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:

A way not to get sign decompositions (2/26/2010)
Matrix of random signs, redux (6/1/2009)
Factorization norm details (2/9/2010)

No comments

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 is uniform over the unit sphere, is given by the sign vector of

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:

An observation on the norming functionals of the $(\infty,1)^\star$ norm ball (2/24/2010)
Wiener filtering (2/17/2009)
A family of optimization problems (7/22/2008)

No comments

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:

A way not to get sign decompositions (2/26/2010)
Equivalence of the $\gamma_2$ norm and the $\|\cdot\|_{\infty \rightarrow 1}^\star$ norm (1/27/2010)
Articles on communications complexity (2/9/2010)

No comments

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 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 was $n \times n$ with n = 5 , you might get 128 out of 256 rank one matrices contributing to . (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:

A dictionary, or not? (1/27/2010)
A way not to get sign decompositions (2/26/2010)
Research agenda (5/2/2008)

No comments

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:

$\varphi_0 \in \span\{\varphi_i\}_{i=1}^n;$

$\text{ker} \varphi_0 \supset \cap_{i=1}^n \text{ker} \varphi_i.$

Can you prove it?

Possibly relevant posts:

Dr. Singh’s Take on the Fourier Unicity Theorem (via Invariant Subspaces) (6/17/2005)
Adjoints (in Hilbert spaces) (10/5/2005)
Every finite spanning set is a frame (5/26/2006)

No comments

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.