# Induced $2$-matrix Norm Restricted on Sparse Vectors

Let $A$ be a real matrix of size $m \times N$ with $m <M$. Suppose we are interested in measuring its induced $2$-norm when acting on the set of all column vectors $x$ that have at most $s$ nonzero entries. In other words, we are interested in computing the quantity $\Gamma_s=\displaystyle\max_{x \neq0, ||x||_0\le s} \frac{||Ax||_2}{||x||_2}$. Is it true that $\Gamma_s = \displaystyle\max_{S \subset [N]: |S|=s} ||A_S^T A_S - I_s||_2$, where $[N]=\left\{1,\cdots,N\right\}$ and $A_S$ is the $m \times s$ matrix obtained by deleting every column of $A$ outside the index set $S$? ($||\cdot||_0$ equals to the number of nonzero entries of its argument).

-

Let $T$ denotes the set of vectors $x$ that has at most $s$ nonzero entries. Then $T=\bigcup\limits_{S\subset|N|,\,|S|=s}\operatorname{span}\{e_i: i\in S\}$. Therefore \begin{align*} \Gamma_s &=\max\limits_{x \in T\setminus0} \frac{||Ax||_2}{||x||_2}\\ &=\max\limits_{S\subset|N|,\,|S|=s}\ \max\limits_{x \in \operatorname{span}\{e_i: i\in S\}\setminus0} \frac{||Ax||_2}{||x||_2}\\ &=\max\limits_{S\subset|N|,\,|S|=s}\ \max\limits_{x \in \mathbb{R}^s\setminus0} \frac{||A_Sy||_2}{||y||_2}\\ &=\max\limits_{S\subset|N|,\,|S|=s}\ ||A_S||_2. \end{align*} So it appears that $\Gamma_s$ is different from $\max\limits_{S \subset [N]: |S|=s} ||A_S^T A_S - I_s||_2$. For example, when $A=(3,3)$ and $s=1$, we have $\Gamma_1=3$, but $\max\limits_{S \subset [N]: |S|=s} ||A_S^T A_S - I_s||_2=\|3^2-1\|_2=8$.
How is $S$ not closed? It is the union of $\binom Ns$ closed subspaces. Besides, it certainly looks to me that when $A=\begin{bmatrix}1&1\\1&1\end{bmatrix}$, we have $\Gamma_1=1\ne2=\sigma_1(A)$, contradicting your conclusion. – Rahul Feb 27 '13 at 9:59
Now it works, though the variable $y$ comes out of nowhere. You need to say something to the effect of "We can associate any vector $x$ in the subspace corresponding to $S$ with a vector $y\in\mathbb R^s$ such that $y=Px$ and $x=P^Ty$, where $P$ is the $s\times N$ projection matrix that deletes the components which are not in $S$." – Rahul Feb 27 '13 at 10:22