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?
