5
$\begingroup$

Let $A\in\mathbb{R}^{r\times m}$ be a matrix of full row rank, and let $\cdot^+$ denote the Moore-Penrose inverse.

Consider a sequence of matrices $\{B_n\}_{n>1}$, $B_n\in\mathbb{R}^{m\times n}$, whose entries are i.i.d. random Gaussian variables with zero mean and finite variance. Numerical simulations suggest that $$ \|(AB_n)^+ - B_n^+ A^+\| \to 0\ \ \text{ as }\ \ n\to\infty $$ where $\|\cdot\|$ denotes the 2-norm of a matrix.

Is it possible to provide a formal proof of this claim?

My question could be either very silly (if so, please close it) or a well-known fact (if so, I will be glad if you can provide pointers to the literature). In any case, the observed numerical behavior looks quite surprising to me, since it is rather well-known that for $A$ and $B$ both of full row rank it holds $(AB)^+ \ne B^+ A^+$ (except for some very special cases).

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ I guess it's because $B$ has 'almost orthogonal' rows (by LLN/CLT-type properties), and $(AB)^+=B^+A^+$ is a property that holds true when $B$ has orthogonal rows. Probably someone more versed than me with random matrices knows how to make this more formal. $\endgroup$
    – Federico Poloni
    Commented Jan 2, 2019 at 13:10
  • $\begingroup$ I do not know much about random matrix theory, but is $B_n$ not of full rank with probability 1 independent of $n$? $\endgroup$
    – user114668
    Commented Jan 3, 2019 at 15:25
  • $\begingroup$ @N.T.: Yes, I would say that $B_n$ is of full (row or column, depending on $m$) rank with probability 1 for every $n$. Why? $\endgroup$
    – Ludwig
    Commented Jan 3, 2019 at 15:46
  • $\begingroup$ @Ludwig Ah, there is my mistake. $A$ has full row rank. Apologies! $\endgroup$
    – user114668
    Commented Jan 3, 2019 at 16:07
  • $\begingroup$ @FedericoPoloni: Thanks for your comment! I was wondering whether the rows of $B$ need to be orthonormal for $(AB)^+=B^+ A^+$ to hold true. $\endgroup$
    – Ludwig
    Commented Jan 3, 2019 at 16:53

1 Answer 1

Reset to default
2
$\begingroup$

As @FedericoPoloni pointed out, this must hinge on the fact that the rows of $B_n$ tend to be orthogonal as $n$ increases. In fact, $$\mathrm{E}[(B_n B_n^*)_{ij}] = n \sigma^2 \delta_{ij} \\ \mathrm{Cov}[(B_n B_n^*)_{ij}, (B_n B_n^*)_{i'j'}] = n \sigma^4 \, (\delta_{ii'} \delta_{jj'} + \delta_{ij'} \delta_{i'j})$$ so that we might as well write $$B_n B_n^* = n \sigma^2 I + \sqrt{n} \sigma^2 R$$ where $R$ is a random matrix with entries of zero mean and $O(1)$ variance. The near-orthogonality comes into play as $$\lim_{n \to \infty} \frac{1}{n} B_n B_n^* = \sigma^2 I$$ which should feature somehow in showing the suggestion.

To introduce this into the M-P inverse, the only thing that comes to mind right now is to take the limit definition $$A^+ = \lim_{\delta \searrow 0} A^* (A A^* + \delta I)^{-1}$$ to define a sequence $$(A B_n)^+_k = B_n^* A^* (A B_n B_n^* A^* + \tfrac{1}{k} I)^{-1}$$ that converges to $(A B_n)^+$. We also have $B_n^+ = B_n^* (B_n B_n^*)^{-1}$ a.s. for $n \ge m$ and $A^+ = A^* (A A^*)^{-1}$. Hence for a fixed $k$ we can evaluate $$\Vert (A B_n)^+_k - B_n^+ A^+ \Vert = \frac{1}{n} \left\Vert B_n^* A^* \left(A \, (\tfrac{1}{n} B_n B_n^*) \, A^* + \tfrac{1}{n k} I\right)^{-1} - B_n^* (\tfrac{1}{n} B_n B_n^*)^{-1} A^* (A A^*)^{-1} \right\Vert$$ which looks harmless enough to be pushed below any desired bound with a suitably large $n$.

If that's the case, pick $\epsilon > 0$ and use the triangle inequality $$\Vert (A B_n)^+ - B_n^+ A^+ \Vert \le \Vert (A B_n)^+ - (A B_n)^+_k \Vert + \Vert (A B_n)^+_k - B_n^+ A^+ \Vert$$ to look at each term on the rhs. individually: first find $k$ s.t. the first term is less than $\epsilon/2$, and then find $n$ s.t. the second term is less than $\epsilon/2$.

Moments of the entries of $BB^*$

For iid. normal entries $B_{ij}$ with zero mean and variance $\sigma^2$: $$\mathrm{E}[B_{ij} B_{kl}] = \sigma^2 \delta_{ik} \delta_{jl}$$ Hence the expectation: $$\mathrm{E}[(B B^*)_{ij}] = \sum_k \mathrm{E}[B_{ik} B_{jk}] = \sum_k \sigma^2 \delta_{ij} \delta_{kk} = n \sigma^2 \delta_{ij}$$ For jointly normal $X_1, X_2, X_3, X_4$ with zero mean: $$\mathrm{E}[X_1 X_2 X_3 X_4] = \mathrm{E}[X_1 X_2] \mathrm{E}[X_3 X_4] + \mathrm{E}[X_1 X_3] \mathrm{E}[X_2 X_4] + \mathrm{E}[X_1 X_4] \mathrm{E}[X_2 X_3]$$ Hence the covariance: $$ \mathrm{Cov}[(B B^*)_{ij}, (B B^*)_{i'j'}] = \sum_{k,k'} \mathrm{Cov}[B_{ik} B_{jk}, B_{i'k'} B_{j'k'}] \\ = \sum_{k,k'} \left\{\mathrm{E}[B_{ik} B_{jk} B_{i'k'} B_{j'k'}] - \mathrm{E}[B_{ik} B_{jk}] \mathrm{E}[B_{i'k'} B_{j'k'}]\right\} \\ = \sum_{k,k'} \left\{\mathrm{E}[B_{ik} B_{i'k'}] \mathrm{E}[B_{jk} B_{j'k'}] + \mathrm{E}[B_{ik} B_{j'k'}] \mathrm{E}[B_{jk} B_{i'k'}]\right\} \\ = \sum_{k,k'} \left\{\sigma^4 \delta_{ii'} \delta_{kk'} \delta_{jj'} \delta_{kk'} + \sigma^4 \delta_{ij'} \delta_{kk'} \delta_{i'j} \delta_{kk'}\right\} \\ = n \sigma^4 (\delta_{ii'} \delta_{jj'} + \delta_{ij'} \delta_{i'j})$$

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for your answer. Could you please elaborate a little more (or provide a reference) on the derivation of the first two displayed equations? $\endgroup$
    – Ludwig
    Commented Jan 11, 2019 at 9:26
  • $\begingroup$ You get the expectation and covariance from the fact the entries of $B_n$ are independent and normal. I have added the steps to the answer, below the line. $\endgroup$
    – user114668
    Commented Jan 11, 2019 at 10:07
  • $\begingroup$ Oh I see, sorry for the silly question. One last comment: which type of convergence are you considering when you write $\lim_{n\to \infty} \frac{1}{n} B_n B_n^*=\sigma^2 I$? $\endgroup$
    – Ludwig
    Commented Jan 11, 2019 at 10:15
  • $\begingroup$ Note that this limit is just a heuristic and not used; the important step is to find a suitable $n$ later on, which you would have to make rigorous. Nevertheless, if you want to know the limit, I would expect (at least) convergence in probability relatively straightforwardly from Markov's inequality for $\Pr[\frac{\sigma^2}{\sqrt{n}} \Vert R \Vert > \epsilon]$ plus some variance-type inequality for $\mathrm{E}[\Vert R \Vert^k]$ in the assumed norm, since $R$ is of fixed size $m \times m$ and does not grow with $n$. $\endgroup$
    – user114668
    Commented Jan 11, 2019 at 12:30
  • $\begingroup$ I see, thank you for clarifying! So the missing step is to show that $\|(AB_n)^+-B_n^+A^+\|$ tends to zero (in probability?) as $n$ goes to infinity, and this should follow from the fact that $B_n$ is almost orthogonal as $n$ tends to infinity. Am I correct? $\endgroup$
    – Ludwig
    Commented Jan 15, 2019 at 16:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .