论文标题
正交匹配追踪的信号依赖性性能分析，以确切稀疏恢复
Signal-Dependent Performance Analysis of Orthogonal Matching Pursuit for Exact Sparse Recovery
论文作者
论文摘要
从线性测量$ y = ax $中的$ k $ -sparse信号$ x \ in \ mathbb {r}^{n} $中的精确恢复，其中$ a \ in \ mathbb {r}^{m \ times n} $是一个传感矩阵，来自许多应用程序。正交匹配追踪（OMP）算法广泛用于重建$ x $。 OMP性能分析的一个基本问题是，随机矩阵$ a $的精确恢复$ x $的概率和最小$ m $以保证目标恢复性能。在许多实际应用中，除了稀疏外，$ x $还具有一些其他属性。本文表明，这些属性可用于完善上述问题的答案。在本文中，我们首先证明$ x $的非零条目的先前信息可用于在$ \ | x \ | _1^2/\ | x \ | _2^2 $上提供上限。然后，我们使用此上限来使用$ k $迭代中的oPM恢复$ x $的概率开发出下限。此外，我们对测量数量$ m $开发了一个下限，以确保使用$ k $ tererations的确切恢复概率不小于给定的目标概率。最后，我们表明，当$ k = o（\ sqrt {\ ln n}）$，因为$ n $和$ k $均为无限，任何$ 0 <ζ\ leq 1/\sqrtπ$，$ m = 2k \ ln（n/pecriments）不足以确保$ $ $ $ k $ k $ k $ k y $ k y $ k y $ k y $ k y $ k y $ k y $ k y $ k y $ k y $ k y $ k y $ k y $ k y $ - $ k $ tererations。对于$ k $ -sparse $α$ -stronglongly腐烂的信号，对于$ k $ -sparse $ x $，其非零条目独立且相同遵循高斯分布，足以进行精确恢复的测量数，概率不低于$ 1-ζ$，以进一步减少$ m =（\ sqrt {k} +4 \ sqrt {\ frac {α+1} {α-1} \ ln（n/ζ）}）^2 $，分别为$ m \ y Insymply $ m \ of 1.9k \ ln（n/pe）$。
Exact recovery of $K$-sparse signals $x \in \mathbb{R}^{n}$ from linear measurements $y=Ax$, where $A\in \mathbb{R}^{m\times n}$ is a sensing matrix, arises from many applications. The orthogonal matching pursuit (OMP) algorithm is widely used for reconstructing $x$. A fundamental question in the performance analysis of OMP is the characterizations of the probability of exact recovery of $x$ for random matrix $A$ and the minimal $m$ to guarantee a target recovery performance. In many practical applications, in addition to sparsity, $x$ also has some additional properties. This paper shows that these properties can be used to refine the answer to the above question. In this paper, we first show that the prior information of the nonzero entries of $x$ can be used to provide an upper bound on $\|x\|_1^2/\|x\|_2^2$. Then, we use this upper bound to develop a lower bound on the probability of exact recovery of $x$ using OMP in $K$ iterations. Furthermore, we develop a lower bound on the number of measurements $m$ to guarantee that the exact recovery probability using $K$ iterations of OMP is no smaller than a given target probability. Finally, we show that when $K=O(\sqrt{\ln n})$, as both $n$ and $K$ go to infinity, for any $0<ζ\leq 1/\sqrtπ$, $m=2K\ln (n/ζ)$ measurements are sufficient to ensure that the probability of exact recovering any $K$-sparse $x$ is no lower than $1-ζ$ with $K$ iterations of OMP. For $K$-sparse $α$-strongly decaying signals and for $K$-sparse $x$ whose nonzero entries independently and identically follow the Gaussian distribution, the number of measurements sufficient for exact recovery with probability no lower than $1-ζ$ reduces further to $m=(\sqrt{K}+4\sqrt{\frac{α+1}{α-1}\ln(n/ζ)})^2$ and asymptotically $m\approx 1.9K\ln (n/ζ)$, respectively.
