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}$? In other words, if $v$ is the principal eigenvector of $A$, can one show that $P(||v./x - {\bf 1}||_2 \geq \epsilon)$ goes to zero for any $\epsilon > 0$ as $n \rightarrow \infty$, where ${\bf 1}$ is the all ones vector and $./$ refers to the elementwise division of two vectors?
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 endend
%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. Moreover, in some additional simulations for lower dimensions I seem to be getting that $ ||(I - (1/n) {\bf 1} {\bf 1}^T) v/x||_2 $ generated as above decreases as a function of the dimension of $n$.
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?
