Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 $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).

share|cite|improve this question
up vote 1 down vote accepted

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$.

share|cite|improve this answer
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
@ℝⁿ. Thanks. That's a mistake. – user1551 Feb 27 '13 at 10:04
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

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.