Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let us decompose matrix $A \in \mathbb{R}^{m\times n}$ as the multiplication of matrices $B \in \mathbb{R}^{m\times k}$ and $P \in \mathbb{R}^{k\times n}$ where some subset of the columns of $P$ make up $k\times k$ identity.

In observation 3.3 of "A randomized algorithm for the decomposition of matrices", it says that for any positive integer $k$ with $k\leq \min(m,n)$, there exists a rank-$k$ approximation to $A$ in the form of the decomposition above, such that the spectral norm $\|A-BP\|$ is less than $\sqrt{r^2 k(n-k)+1}\sigma_{k+1}$ where $\sigma_{k+1}$ is the $k$-th largest singular value of $A$ and the elements of $P$ are at most $r$.

I want to prove this inequality.

What I've done so far?

I first tried to prove that $k$-th greatest singular value of $P$ is at least 1. Thanks to H. Hanche-Olsen, he showed how to do it.

Then I proved that $\|P\|\leq \sqrt{r^2k(n-k)+1}$ if we assume that the largest element of $P$ can be at most $r$. I assumed that all the remaining columns of $P$ that are not making up the identity involve all $r$'s. Then I permuted $P$ as H. Hanche-Olsen does and followed the same steps. The eigenvalue of $PP^T$ is then at most $r^2k(n-k)+1$.

But I couldn't figure out how to use these to prove the bound for spectral norm of the reconstruction error (precision). Or I might be looking for these proofs unnecessarily. I might be stumbled into them since they are given just before the statement in the report I linked.

How can I prove this?

share|cite|improve this question
Intelligent Design does not have any real precision at all. – marty cohen Jan 6 '13 at 1:21
Sorry, but I couldn't understand the comment. What do you mean by Intelligent Design? – Helen Jan 6 '13 at 3:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.