ChapterZero

Numerical Rank

Filed under: Mathematics — Alex @ 5:40 pm 6/16/2008

I spent today looking through several papers. Most of them were about finding graph sparsifiers by sampling– apparently this relates to a generalization of the sparsification problem I’ve been thinking about, where instead of looking for a sparsifier in the spectral norm, you look for one in the $\infty \rightarrow 1$ norm.

I snuck in a paper by Rudelson and Vershynin, to gain some familiarity with the more typical tools in this area, and came across the neat idea of the numerical rank of a matrix: $r(A) = \frac{\|A\|_F^2}{\|A\|_2^2}$ . It’s clear that this satisfies $1/n \leq r(A) \leq \text{rank}(A)$ , but it’s also stable in the sense that if is close to a low rank matrix, then r(A) is also low. I’m looking forward to seeing how they use this quantity.