Skip to main content
2 of 2
added 479 characters in body
morgan
  • 121
  • 3

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 & \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

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. 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?

morgan
  • 121
  • 3