4
$\begingroup$

Consider an $n\times n$ random binary matrix $M$ with i.i.d. entries $m_{ij} \sim {\rm Bernoulli}(p)$, where $p = n^{-\beta}$ with $\beta \in (1,2)$. I am interested in the behavior of the singular value decomposition of $$M = \sum_{i=1}^{rank(M)} \sigma_i u_i v_i',$$ where $\sigma_i$ are ranked in decreasing order.

Some intuitive observation (which might NOT be all true!):

1) By subtracting the mean we can write $M = p {\bf 1} {\bf 1}' + A$, where $A$ has indepedent entries with zero mean and variance $p(1-p)$. Therefore I expect the leading singular vector is approximately parallel to the all-one vector ${\bf 1}$, and the largest singular value is $\sigma_1 \approx p n$. If the SVD of $A$ behaves similarly to that of the usual iid matrices, it is probably true that the second largest singular value of $M$ (i.e., the largest singular value of $A$) is approximately $\sigma_2 \approx \sqrt{p n}$.

2) $rank(M)$ is pretty small: since $\mathbb{P}(\text{the first}~ m \text{ rows are all zero}) = (1-p)^{n m}\geq 1-pmn$. Therefore $rank(M) \leq n^{\beta-1}$ with high probability. This is wrong... this only says that $rank(M) \leq n-n^{\beta-1}$.

Are there any rigorous results about the SVD of this matrix ensemble? Is it true that except for $u_1,v_1$ which are approximately $\frac{1}{\sqrt{n}} {\bf 1}$, the remaining singular vectors are independently and uniformly distributed over $S^{n-1}$?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Presumably you mean "VERY sparse random matrices" in the title? $\endgroup$
    – Mark Meckes
    Commented Jan 20, 2012 at 18:02

2 Answers 2

Reset to default
3
$\begingroup$

Also in the "a little too involved for a comment" class: A matrix that's this sparse is usually going to be a block diagonal matrix with very small blocks.

Let $k$ be any fixed constant, and suppose that your matrix contains no $k+1 \times k+1$ principal submatrix with at least $k$ nonzero entries. Then your matrix has a block decomposition with all blocks having size at most $k+1$ (If you start with a given nonzero entry and "grow" it by adding entries in the same row/column as an entry already added, you'll stop by the time you've reached $k-1$ added entries, and each addition increases the size of your block by at most $1$). In this case we can upper bound the probably a submatrix of this size exists by $$\binom{n}{k+1} \binom{(k+1)^2}{k} p^{k} \leq C_k n^{k+1-k \beta}$$ Which goes to $0$ for any $\beta$ in your range if $k$ sufficiently large.

This means you'll usually see singular vectors with very small support, and that the $\sigma_2$ should be much larger than $\sqrt{np}$ (maybe equal to $\sigma_1$ in most cases?) You might be able to get something more explicit by enumerating all the possible structures of blocks and the expected number of occurrences of each.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks Kevin. I understand your calculation of the probability but I didn't quite get what you meant by block decomposition. Can you elaborate a bit? $\endgroup$
    – gondolier
    Commented Jan 21, 2012 at 1:09
  • $\begingroup$ Also, what do you think about $rank(M)$? Your thesis seems to deal with the case with $p>=\log n / n$, i.e., $\beta \leq 1$ and rank is full whp. Here probably rank is roughly number of non-zero rows/columns? $\endgroup$
    – gondolier
    Commented Jan 21, 2012 at 1:11
  • $\begingroup$ A Block Decomposition here means partitioning the indices from $1$ to $n$ into blocks $A_1, A_2, \dots A_m$ such that $a_{ij}$ is zero if $i$ and $j$ are in different blocks. It corresponds to an ordering of the indices where the matrix is block diagonal. You can take a set of singular vectors/values coming from the singular vectors/values of each block. $\endgroup$
    – Kevin P. Costello
    Commented Jan 21, 2012 at 4:05
  • $\begingroup$ If $\beta>3/2$ the rank should be equal to the number of nonzero rows/columns, just because with high probability no row/column has two nonzero entries. For smaller $\beta$, I think they should still be nearly equal, but not exactly. You should be able to bound the difference by something like the number of nonzero entries in the same row/column as another nonzero entry, which is on the order of $n^{3-2\beta}$, compared to $n^{2-\beta}$ rows with nonzero entries). $\endgroup$
    – Kevin P. Costello
    Commented Jan 21, 2012 at 4:19
  • $\begingroup$ But on the other hand there should be pairs of columns each having exactly one nonzero entry both in the same row, and vice versa, leading to dependencies among the nonzero rows/columns. $\endgroup$
    – Kevin P. Costello
    Commented Jan 21, 2012 at 4:20
1
$\begingroup$

Here's just one quick remark (a little involved for a comment) about how you can start making greater use of your suggested reduction to $A$. Since $M-A$ has rank 1, $$ \sigma_3(A) \le \sigma_2(M) \le \sigma_1(A). $$ Classical results imply that $\sigma_1(A), \sigma_3(A) \approx \sqrt{pn}$, so $\sigma_2(M) \approx \sqrt{pn}$ too.

For more, this paper by Van Vu probably (I haven't read it yet) has a lot that's relevant to your questions.

Improve this answer
$\endgroup$
2
  • $\begingroup$ could you give a bit more details on the classical result, because here the entrywise distribution of $A$ varies with the dimension, so presumably you need some non-asymptotic bounds on $\sigma_{\cdot}(A)$ ? $\endgroup$
    – gondolier
    Commented Jan 20, 2012 at 18:29
  • $\begingroup$ Ack, that's what I get for writing in a hurry. You're right, classical results don't apply directly. I'll think some more and try to write again. $\endgroup$
    – Mark Meckes
    Commented Jan 20, 2012 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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