矩阵复原问题的可解性研究(4)
2.1可识别性，在无噪声情况下的精确恢复
对理解约束核范数最小化重要的一步是在无噪声情况下对低秩矩阵精确恢复的研究，这也致使了足够的可识别性条件.在低秩矩阵恢复中一种广泛运用的框架就是在矩阵设置中的约束等距性（RIP）.然而，RIP框架并不是很适用于ROP模型而且会导致次优的结果.2.2节会有更多关于RIP的讨论.在本节中，我们将通过约束核范数最小化来介绍受限制的一致有界性（RUB）状况，它表明可确保在无噪声的情况下的低秩矩阵的精确恢复以及有噪情况下的稳定恢复.它也表明，RUB有很高概率满足一系列随机映射.
定义2.1（受限制的一致有界性）.对于线性映射 ,如果存在统一常数C1 和C2使得对于所有非零秩r矩阵 有
,
其中 是向量ℓ1范数，那么我们说 满足阶 r和常量C1 及C2的受限制的一致有界性（RUB）.
在无噪声的情况下，我们令 ，并通过约束核范数最小化预估矩阵A
(2.1) .
下面的定理表明RUB条件保证了所有秩r矩阵的精确恢复.
定理2.1 设k≥2是整数.假设 满足kr阶RUB模型以及 条件.那么核范数最小化的方法可恢复所有秩r矩阵.也就是说，对于所有秩r矩阵A和 ，我们有A *= A，其中A *由（2.1）给出.
定理2.1表明，在有噪情况下，对于低秩矩阵复原模型（1.1）来说，RUB中kr和 是充分性条件.下面的结果表明，若有足够数目的测量值，在ROP模型下，RUB状况也是有很高的可能性满足条件的.
定理2.2 假设 为标准正态分布的ROP.对于整数k≥2，正数C1<1/3 和C2 > 1，存在不依赖于 p1, p2和 r的常数C和δ，这样
(2.2) ,
至少有 的概率，使得 满足阶为kr和常量C1 及C2.的RUB.
备注2.1 测量值需要满足条件 ，才能使RUB满足C1> 0.注意到所有秩r矩阵 的自由度为 .如果 必存在一个非零秩r矩阵 使得 .导致 的RUB没有非无效解.
定理2.1和2.2的直接结论，若ROP满足有 的测量值可以保证所有秩r矩阵的精确复原.
推论2.1 假设 是标准正态分布的ROP.存在统一常数C和δ，当 时，在（2.1）中给出的约束核范数最小化估计量A*有至少 的概率来复原所有秩r矩阵 .
需要注意的是测量数量 在最优率以上最佳，因为秩r矩阵 的自由度为 ，并且在任何情况下恢复A所需的测量值都至少是 .
上一篇：如何选择定期死亡保险的投保期限
下一篇：Aczel不等式的推广