0
$\begingroup$

Let $G \in \mathbb{R}^{n \times m}$ (m > n, m = O(n)) whose all entries are i.i.d. distributed as $\mathcal{N}(0, 1) * \text{Ber}(p)$. Let $V \in \mathbb{R}^{m \times n}$ be a fixed semi-orthogonal matrix i.e. the columns of $V$ are orthonormal vectors. Define $A=GV$, then what is the smallest value of $p$ so that we can give a polynomial upper bound with probablity $1-o(1)$ on the condition number of $A$ i.e. $\kappa(A) \leq \text{poly}(n)$?

Interesting subcase/related problems:

  1. Let $V$ be defined as $V_{i, j} = 1$ if $i = j$ and $V_{i, j} = 0$ otherwise. Let $G = [g_1, g_2, \ldots, g_m]$, in this case $A = GV = [g_1, g_2, \ldots, g_n]$. Hence in this case $A$ has the same distribution as $G$ except $m = n$. This was studied by Basak and Rudelson who proved that $\kappa(A) \leq \text{poly}(n)$ for $p = \Omega(\log n)/n$.

  2. For $p = 1$, $G$ is just a random Gaussian matrix and $A = GV$ can also be seen to be random gaussian matrix are gaussian vectors are isotropic. This is just a subcase of 1.

  3. For $m = n$, $V$ is just an orthonormal matrix hence $\kappa(V) = 1$ and from 1. we have $\kappa(G) \leq \text{poly}(n)$ if $p = \Omega(\log n)/n$. Hence we get $\kappa(A) \leq \kappa(G)*\kappa(V) \leq \text{poly}(n)$.

$\endgroup$
3
  • 1
    $\begingroup$ $G$ is a random matrix, but you seem to be looking for a deterministic upper bound? Please clarify. $\endgroup$ Apr 5, 2020 at 5:06
  • $\begingroup$ I meant a w.h.p. bound, edited. $\endgroup$ Apr 5, 2020 at 11:04
  • 1
    $\begingroup$ The Basak rudelson result is difficult because they handle a general class of distributions (they only assume finite fourth moments ...). In this case since you know so much about $G$, it might be just easier to expand the product $Ax$ and use a simple net argument, especially since you only want a 1-o(1) probability bound $\endgroup$ Apr 6, 2020 at 0:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.