algorithm - 从 Ax - Restricted Isometry Property 中恢复稀疏向量 x 的算法

Question

我遇到了这个问题，不知道该怎么做。帮助将不胜感激！我很确定矩阵的分布需要满足受限等距属性，但之后我不知道如何恢复向量：

假设 x 是 s 稀疏的，对于一个常数 s，为了方便我们将其设置为 s = 60。

找到最佳参数 k（您可以使用 O() 表示法）和大小为 k×n 的矩阵 A 的分布，以及有效的“恢复算法”，使得以下两个属性都成立：

(a) With probability at least 0.99, for all s-sparse vectors x ∈ R
    n with coefficients in {−1, 0, 1}, the recovery algorithm returns x upon input Ax, and
(b) For all non s-sparse vectors x with coefficients in {−1, 0, 1}, with
    probability at least 0.99, the algorithm returns ‘FAIL’.

注 1：（a）和（b）中量词的顺序颠倒了。在 [(a)] 中，你有 'with prob.... for all'，在 [(b) 中，你有 'for all...with prob'。
注2：可以去掉系数在{−1, 0, 1}的要求，对整数系数可以做更强的表述。

谢谢！

标签： algorithmmatrixlinear-algebrasparse-matrix