Recovering a rank-one matrix from its eigendecomposition after randomized rounding 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 &amp; \mbox{ with probability } A_{ij} \\ 0 &amp; \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 &gt; 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&gt;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.)
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&gt;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 &gt; 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&gt;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