Recovering Low-Rank Matrices From Few Coefﬁcients In Any Basis

Recovering Low-Rank Matrices From Few Coefﬁcients In Any Basis-David Gross

引

依旧是一个重构矩阵的问题，这篇论文的符号有些奇怪，注意一下。假设有一个矩阵 $\rho \in \mathbb{R}^{n \times n}$ ,其秩为 $r \ll n$ 。有一组基 $w_a, a=1,\ldots, n^2$ ，是已知的。假设我们观测到的是，一组内积 $\{ (\rho, w_a) | a \in \Omega \}$ ，其中 $(\rho, w_a) = tr(\rho^{\dagger}w_a)$ ， $\rho^{\dagger}$ 表示 $\rho$ 的共轭转置。在这些条件下，我们是否能够从 $\{ (\rho, w_a) | a \in \Omega \}$ 中恢复出 $\rho$ 。

一些符号说明：
$\|\rho\|_1$ 为 $\rho$ 的奇异值之和，即此为矩阵核范数。
$\|\rho\|_2$ 为 $\rho$ 的F范数，而非一般符号代表的谱范数。
$\|\rho\|$ 为 $\rho$ 的谱范数。

作者强调，这个问题，是可以办到的，不过其基需要满足一个coherence条件：

在这里插入图片描述

且，即为酉矩阵（不过作者提到，似乎即便不满足此条件，也可以通过一种转化来求解）。

主要结果

作者通过求解下述问题来恢复矩阵 $\rho$ :

在这里插入图片描述

需要指明的一点是，如果中大部分为0，那么想要恢复出是非常困难的（因为这意味着我们可用的信息非常少）。

定理2，3

下为定理2，其中的标准基为： $\{e_i e_j^{\dagger}\}_{i,j=1}^n$ ，即仅有 $i$ 行 $j$ 列元素为1，其余均为0的 $n \times n$ 矩阵所构成的基。

在这里插入图片描述

作者的结论更为一般，可以拓展到任意的基：

在这里插入图片描述

定理4

接下来还有定理4：

在这里插入图片描述

定理4针对的是一种特殊的基——Fourier-type基，介绍此的原因是，作者先证明此定理，再通过一些转换来证明定理3的。

直观解释

作者通过俩幅图，给出了一些直观的解释。

在这里插入图片描述

先来看(a)。我们可以将整个线性空间分成和。因为我们已有的信息是，问题(1)中满足约束的矩阵在空间中形成一个超平面，即图中的，而我们所期望的是其中的一点。

再来看(b)，因为我们希望的是 $\rho$ 是问题(1)的最优解，最好还是唯一的。如果真的如此，那么 $B = \{\sigma | \|\sigma\|_1 \le \|\rho\|_1\}$ 这个集合只能在平面 $A$ 的上方或者下方，实际上，就是平面A是 $B$ 的支撑超平面，其支撑点为 $\rho$ 。

当然，这个性质并没有这么容易达成，其等价于要满足：
$\|\rho + \Delta\|_1 \ge \|\rho\|_1$
对于 $A$ 中任意的点 $\rho + \Delta \neq \rho$ 成立。但是呢，直接证明是困难的，所以作者寻求一个对偶条件即下式：
$\|\rho + \Delta\|_1 > \|\rho\|_1 + (Y, \Delta)，\Delta \neq 0$
关于某个 $Y$ 成立，而且 $Y$ 必须与超平面 $A$ 垂直。这个 $Y$ 能否找到，就是 $\rho$ 能否恢复的关键。

最后编辑于：2019.04.25 17:50:27