论文标题
非常稀疏的矩阵完成的检测阈值
Detection thresholds in very sparse matrix completion
论文作者
论文摘要
令$ a $为尺寸$ m \ times n $的矩形矩阵，$ a_1 $是随机矩阵，其中$ a $的每个条目都乘以独立$ \ {0,1 \} $ - bernoulli随机变量与参数$ 1/2 $。本文是关于随机引起的非对称矩阵$ a_1（a-a_1）^*$ and $（a-a_1）^*a_1 $的何时，如何，方式和原因，捕获了更多有关$ a $的主要组件结构的相关信息，而不是通过其svd或eigen-eigen-spect $ $ a^*a^*a^*a^*a^*a^************************************提示：诱导随机性的不对称性破坏了削弱SVD的回声室效应。 我们说明了这种引人注目的现象在低级矩阵完成问题上的应用，以在每个条目中以概率$ d/n $观察到每个条目，其中包括非常稀疏的制度，其中$ d $属于订单$ 1 $，其中矩阵通过$ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a a $ a $ a $ a $ a a $ a $ a $ a a $ a $ a $ a。我们确定了一个渐近，矩阵依赖性的，非普遍检测阈值，在该阈值中，使用新的，通用的数据驱动的矩阵完整算法可靠，统计上最佳的矩阵恢复。证明左右特征向量可以改善恢复的矩阵，但不能改善检测阈值。我们定义了这种不对称过程的另一个变体，该过程绕过随机步骤，并具有恒定因子的检测阈值，但其计算成本较小，而观察到的条目数量的多项式因素较大。由于众所周知的信息限制$ d \ asymp \ log n $，对于文献中的矩阵完成，这两个检测阈值都破坏了看起来障碍。
Let $A$ be a rectangular matrix of size $m\times n$ and $A_1$ be the random matrix where each entry of $A$ is multiplied by an independent $\{0,1\}$-Bernoulli random variable with parameter $1/2$. This paper is about when, how and why the non-Hermitian eigen-spectra of the randomly induced asymmetric matrices $A_1 (A - A_1)^*$ and $(A-A_1)^*A_1$ captures more of the relevant information about the principal component structure of $A$ than via its SVD or the eigen-spectra of $A A^*$ and $A^* A$, respectively. Hint: the asymmetry inducing randomness breaks the echo-chamber effect that cripples the SVD. We illustrate the application of this striking phenomenon on the low-rank matrix completion problem for the setting where each entry is observed with probability $d/n$, including the very sparse regime where $d$ is of order $1$, where matrix completion via the SVD of $A$ fails or produces unreliable recovery. We determine an asymptotically exact, matrix-dependent, non-universal detection threshold above which reliable, statistically optimal matrix recovery using a new, universal data-driven matrix-completion algorithm is possible. Averaging the left and right eigenvectors provably improves the recovered matrix but not the detection threshold. We define another variant of this asymmetric procedure that bypasses the randomization step and has a detection threshold that is smaller by a constant factor but with a computational cost that is larger by a polynomial factor of the number of observed entries. Both detection thresholds shatter the seeming barrier due to the well-known information theoretical limit $d \asymp \log n$ for matrix completion found in the literature.
