Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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}$?

share|improve this question
1  
Presumably you mean "VERY sparse random matrices" in the title? –  Mark Meckes Jan 20 '12 at 18:02
    
Thanks! Fixed. –  mr.gondolier Jan 20 '12 at 18:27
add comment

2 Answers

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.

share|improve this answer
    
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? –  mr.gondolier Jan 21 '12 at 1:09
    
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? –  mr.gondolier Jan 21 '12 at 1:11
    
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. –  Kevin P. Costello Jan 21 '12 at 4:05
    
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). –  Kevin P. Costello Jan 21 '12 at 4:19
    
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. –  Kevin P. Costello Jan 21 '12 at 4:20
add comment

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.

share|improve this answer
    
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)$ ? –  mr.gondolier Jan 20 '12 at 18:29
    
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. –  Mark Meckes Jan 20 '12 at 18:40
add comment

Your Answer

 
discard

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.