Recovering a rank-one matrix from its eigendecomposition after randomized rounding

Question

Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting $$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ with probability } A_{ij} \\ 0 & \mbox{ with probability } 1-A_{ij} \end{cases} $$

Is it possible to recover $x$ by looking at the principal eigenvector of $A_{\rm rounded}$? In other words, suppose $v$ is the principal eigenvector of $A$; is it true that, after rescaling $v$ and $x$ to have unit norm, the two vectors are nearly the same? In particular, can one show that $P( || \frac{x}{||x||_2} - \frac{v}{||v||_{2}} ||_{\infty} \geq \epsilon)$ goes to zero for any $\epsilon > 0$ as $n \rightarrow \infty$?

I wrote a quick MATLAB simulation that suggests the answer is yes. Here is my code:

n=20000; %matrix size

%generate matrix;

x = rand(n,1);

y = rand(n,1);

A = x*y';

%generate rounded matrix

B = zeros(n,n);

for i=1:n

for j =1:n

    if rand>A(i,j)

        B(i,j)=0;

    else

        B(i,j) =1;

    end

end

end

%eigendecomposition of B

[v,d]=eig(B);

%figure out the index of the principal eigenvector;

m = max(abs(d));

mm = max(m);

i = find(m==mm);

%compare principal eigenvector to true answer

y = v(:,i)/norm(v(:,i)) - x/norm(x);

norm(y,inf)

Running this code with matrix size of 20,000 took me a few hours and returned $|| v/||v||_2 - x/||x||_2 ||_{\infty} \approx 0.02$, suggesting that the answer is positive. Since the answer is likely yes, is this something that is present in the literature? And is there a simple argument to see that recovery is possible, in this or a related model?

(I previously asked this question on MO without receiving an answer.)

Answer 1

I think that, as the question is currently formulated, the answer is no.

Here is a proposed counterexample. Fix arbitrarily large $n$. Take $xy^T$ to be the matrix having each coordinate equal to $\delta/n$, for a sufficiently small constant $\delta>0$ (so $x$ is uniform). $A$ is then a random matrix where each entry is $1$ with probability $\delta/n$ and otherwise zero.

Here is a proof that this is indeed a counterexample to the conjecture in the post.

Lemma 1. With probability $\Omega(\delta)$, $A$ has a dominant eigenvector $v'$ such that $$\Big\|\frac{x}{\|x\|_2} - \frac{v'}{\|v'\|_2}\Big\|_\infty = \Big|\frac{1}{\sqrt n} - 1\Big| \approx 1.$$

Proof. Consider the directed graph $G=(V,E)$ with adjacency matrix $A$, that is $V=\{1,\ldots,n\}$ and $E=\{(i,j) : A_{ij} = 1\}$. So $G$ is a random digraph where each possible edge (including self-loops) is independently present with probability $\delta/n$.

Let $X$ be the event that $G$ has a directed cycle of length 2 or more. By the naive union bound, the probability that there is such a cycle is less than $\sum_{\ell\ge 2} n^\ell (\delta/n)^\ell = \sum_{\ell\ge 2} \delta^\ell = \delta^2/(1-\delta)$.

Let $Y$ be the event that $G$ has at least one vertex $i$ with a self-loop but no other outgoing edges. (That is, $A_{ii}=1$ and every other entry in row $i$ is zero.) By calculation, event $Y$ happens with probability about $1-e^{-\delta/e^\delta} = \Omega(\delta)$.

So the probability that $Y$ happens and $X$ does not is $\Omega(\delta) - O(\delta^2) = \Omega(\delta)$. Assume that $Y$ happens and $X$ does not. Because $Y$ happens, there is a row $i$ of $A$ where $A_{ii} =1$ but all other entries are zero. So $A$ has an eigenvector $v'$ where $v'_{i} = 1$ is the only non-zero entry. But $x_i/\|x\|_2 = 1/\sqrt n$, so, for this eigenvector, $$\Big\|\frac{x}{\|x\|_2} - \frac{v'}{\|v'\|_2}\Big\|_\infty = \Big|\frac{1}{\sqrt n} - 1\Big| \approx 1.$$

To finish, we show that $v'$ is a dominant eigenvector, that is, that the largest eigenvalue of $A$ is 1. Consider any eigenvector $v$. Let $\lambda$ be the eigenvalue of $v$, so $Av = \lambda v$. Let $C=\{i : v_i > 0\}$ be the support of $v$. Consider the subgraph $G_C$ induced by $C$ (as a set of vertices in $G$). Since $X$ does not happen, $G_C$ has no cycle of length 2 or more, so each strongly connected component of $G_C$ is a single vertex. Hence, $G_C$ contains a single vertex $i$ having no incoming edges in $G_C$, except possibly a self-loop. Now, because $v$ is an eigenvector with support $C$, this implies $A_{ii} v_i = \lambda v_i$. Since $v_i>0$ this implies $\lambda =A_{ii} \in\{0, 1\}$. $~~\Box$

I think that the above argument suggests that $G$ can have multiple dominant eigenvectors (each with eigenvalue 1), and that some of those eigenvectors could have larger support --- size $\Omega(\log n)$, maybe? And such an eigenvector $v$ could have $\max_i v_i/\|v\|_2 = O(1/\log n)$, and so could meet the proposed condition for being "the same" as $x$. But see Remark 1 below.

---

Remark 1. The condition currently suggested in the post for $x$ and $v$ to be "the same", namely, $$\Big\|\frac{x}{\|x\|_2} - \frac{v}{\|v\|_2}\Big\|_\infty \le \epsilon,$$ seems to be too weak. It can only be violated if $x$ or $v$ has at least one very large coordinate.

For example, suppose the first $n/2$ coordinates of $x$ are 1 and the rest are zero, while the first $n/2$ coordinates of $v$ are zero, and the rest are 1. Then $x$ and $v$ are orthogonal, so arguably not at all "the same". But $x_i/\|x\|_2 \le \sqrt{2/n}$ and $v_i/\|v\|_2 \le \sqrt{2/n}$, so, assuming $n \ge 2/\epsilon^2$, the suggested condition is satisfied.

Of course, if the condition were strengthened, the counterexample above should still hold...

---

Remark 2. Tangentially, the behavior of eigenvectors of sparse random graphs (where the edge probability is around $1/n$ or so), seems to be fairly complicated. Among the references I found, the most relevant to the argument was [1]. It considers the case when $\delta$ is just below 1, and shows that each strongly connected component of $G$ is either a single vertex or a cycle of constant size (possibly with self-loops).

The case when the edge probability is slightly larger, above $\log(n)/n$, say, seems to be more well studied, and in that case I think (although I'm not sure) that the eigenvectors of $G$ are more uniform. Search Google Scholar for "eigenvectors of sparse random graphs".

[1] Luczak, T. and Seierstad, T. G.. The critical behavior of random digraphs. Random Structures and Algorithms 35, 271-293 (2009). http://folk.uio.no/taralgs/artikler/digraph.pdf