Suppose $G$ is an $m \times n$ matrix such that each entry of $G$ is a standard normal variable. We know that the spectral norm of $G$ scales as $\sqrt m + \sqrt n$. Now, given a set of indices $S$ suppose we construct a new matrix $A$ such that $A_{ij} = G_{ij}$ if $(i,j) \in S$, and 0 otherwise. Can we show that the spectral norm of $A$ is upper bounded by the spectral norm of $G$?

edit: The spectral norm is the largest singular value of the matrix: $\| G \| = \sigma_1(G)$

  • $\begingroup$ Can you please add the definition of the spectral norm of a matrix to make the question more readable? $\endgroup$ – Xi'an Feb 5 '15 at 8:20
  • 1
    $\begingroup$ Hi Xi'an , I just added the definition. $\endgroup$ – NSR Feb 5 '15 at 12:47

No, counterexample:

$$ G = \begin{bmatrix}-1& 1& 1\\ 1 &1 &1\\ 1& 1& -1\end{bmatrix}, \qquad A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \end{bmatrix} $$

The spectral norm of $G$ is 2, the spectral norm of $A$ is about 2.4.

I think in general making things sparse shouldn't have any guaranteed effect on the spectral properties unless there is some additional structure.

  • $\begingroup$ Interesting. @additional structure, I then assume that if G were a Gaussian matrix, things would not necessarily change? What if I zero out "enough" entries? In the extreme case A would be the all 0 matrix and then the result holds of course. $\endgroup$ – NSR Apr 7 '15 at 0:53
  • $\begingroup$ Actually, I think you could probably say something "with x probability" or even "with high probability" (most of my random examples seem to work as you hypothesized) but I guess my point is you can never guarantee anything. If in a (possibly rare) chance you come across that pathological example, it wouldn't work. $\endgroup$ – Y. S. Apr 8 '15 at 1:34
  • $\begingroup$ Ah yea, I think the statement holds with high probability. $\endgroup$ – NSR Apr 8 '15 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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