2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks, I fixed it. The code doesn't recover $y$: I use the variable $y$ in the code for $v./x$. Eventually, I'd be curious to recover $A$, but my first question was whether this algorithm recovers $x$; if so, you could use the same approach to recover $y$ and recover $A$ at least up to scaling. My intuition is that this is similar to the model where you are given $A=xy^T + W$ where $W$ is noise, and in that case, recovery is possible if the $W$ is small enough (sciencedirect.com/science/article/pii/S0001870811000570 ). Here noise is not small but you compensate with many samples. $\endgroup$ – morgan Sep 7 '18 at 2:07
  • $\begingroup$ Do you have any reason to think that the behavior for random x and y (as your code tests) has any bearing on what should hold for all x and y? That seems far-fetched to me. $\endgroup$ – Neal Young Sep 7 '18 at 11:40
  • $\begingroup$ The condition you are currently proposing for $x$ and $v$ to be "the same" is very weak. E.g., in the example in your post, surely w.h.p. you will have $\|x\|_2 \approx \sqrt {n/2}$, so $\max_i x_i/\|x\|_2 \le \sqrt{2/n} \approx 0.01$. So $\big\|v/\|v\|_2 - x/\|x\|_2\big\|_\infty \approx 0.02$ is not surprising, and says little about $v$ and $x$ being similar. E.g., it will hold for any $v$ such that $|v\|_2 \approx \sqrt{2/n}$ and $v_i \le 1$. You probably need to use a norm other than the $\infty$ norm, or you need $\epsilon$ to decrease with $n$. See also Remark 1 in my answer below. $\endgroup$ – Neal Young Sep 10 '18 at 15:30
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.