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 $A$ by looking at the principal eigenvector of $A_{\rm rounded}$? 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)./x; > > %ideally, y is a multiple of the all-ones vector. > > %check how far this is from being the case > > J = eye(n,n)-(1/n)*ones(n,n); > > norm(J*y) Running this code with matrix size of 20,000 took me a few hours and returned the following result: if $v$ is the principal eigenvector of $A_{\rm rounded}$, and $v/x$ is the elementwise ratio of $v$ and $x$, then $ ||(I - (1/n) {\bf 1} {\bf 1}^T) v/x||_2 \approx 0.06$. Given that $v$ and $x$ are in $\mathbb{R}^{20,000}$, this strongly suggests 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?