<p>I think that, as the question is currently formulated, the answer is no.  </p>

<p>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.  </p>

<p>Here is a proof that this is indeed a counterexample to the conjecture in the post.</p>

<p><strong>Lemma 1.</strong> <em>With probability $\Omega(\delta)$, $A$ has a dominant eigenvector $v'$ such that</em> $$\Big\|\frac{x}{\|x\|_2} - \frac{v'}{\|v'\|_2}\Big\|_\infty = \Big|\frac{1}{\sqrt n} - 1\Big| \approx 1.$$</p>

<p><em>Proof.</em> 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$.</p>

<p>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)$.</p>

<p>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)$. </p>

<p>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.$$</p>

<p>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$</p>

<p>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.</p>

<hr>

<p><strong>Remark 1.</strong> 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.  </p>

<p>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 <em>orthogonal</em>, 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.</p>

<p>Of course, if the condition were strengthened, the counterexample above should still hold...</p>

<hr>

<p><strong>Remark 2.</strong> 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).</p>

<p>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".</p>

<p>[1]  Luczak, T. and Seierstad, T. G.. The critical behavior of random digraphs. Random Structures and Algorithms 35, 271-293 (2009).
<a href="http://folk.uio.no/taralgs/artikler/digraph.pdf" rel="nofollow noreferrer">http://folk.uio.no/taralgs/artikler/digraph.pdf</a></p>

CC BY-SA 4.0
2018-09-10T01:54:39.663Z
2018-09-10T15:59:37.587Z
2018-09-10T15:59:37.587Z
Neal Young
<p>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} $$</p>

<p>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$?</p>

<p>I wrote a quick MATLAB simulation that suggests the answer is yes. Here is my code:</p>

<blockquote>
  <p>n=20000; %matrix size</p>
  
  <p>%generate matrix; </p>
  
  <p>x = rand(n,1);</p>
  
  <p>y = rand(n,1);</p>
  
  <p>A = x*y';</p>
  
  <p>%generate rounded matrix</p>
  
  <p>B = zeros(n,n);</p>
  
  <p>for i=1:n</p>

<pre><code>for j =1:n

    if rand&gt;A(i,j)

        B(i,j)=0;

    else

        B(i,j) =1;

    end

end
</code></pre>
  
  <p>end</p>
  
  <p>%eigendecomposition of B</p>
  
  <p>[v,d]=eig(B);</p>
  
  <p>%figure out the index of the principal eigenvector;</p>
  
  <p>m = max(abs(d));</p>
  
  <p>mm = max(m);</p>
  
  <p>i = find(m==mm);</p>
  
  <p>%compare principal eigenvector to true answer</p>
  
  <p>y = v(:,i)/norm(v(:,i)) - x/norm(x);  </p>
  
  <p>norm(y,inf)</p>
</blockquote>

<p>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? </p>

<p>(I previously <a href="https://mathoverflow.net/questions/309441/recovering-a-rank-one-matrix-from-its-eigendecomposition-after-randomized-roundi">asked this question on MO</a> without receiving an answer.)</p>

CC BY-SA 4.0
2018-09-07T02:07:03.897Z
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 (https://www.sciencedirect.com/science/article/pii/S0001870811000570 ). Here noise is not small but you compensate with many samples.
morgan
CC BY-SA 4.0
2018-09-07T11:40:11.997Z
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.
Neal Young
CC BY-SA 4.0
2018-09-10T15:30:27.867Z
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.
Neal Young
<linear-algebra><pr.probability>
Recovering a rank-one matrix from its eigendecomposition after randomized rounding
morgan
# Recovering a rank-one matrix from its eigendecomposition after randomized rounding

(Asked by: username_0 on 2018-09-04)

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

**Tags:** linear-algebra, pr.probability
> **Comments:**
> **username_0**: 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 (https://www.sciencedirect.com/science/article/pii/S0001870811000570 ). Here noise is not small but you compensate with many samples.  
> **username_1**: 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.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2018-09-10. Score: 1 | Accepted 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>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>


---

