Sparse Recovery over Graph Incidence Matrices
Sparse Recovery over Graph Incidence Matrices
复制标题
DOI：
10.1109/cdc.2018.8619666
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Mengnan Zhao;M. Kaba;R. Vidal;Daniel P. Robinson;Enrique Mallada
中科院分区：
文献类型：
--
作者：
Mengnan Zhao;M. Kaba;R. Vidal;Daniel P. Robinson;Enrique Mallada
稀疏恢复的经典结果保证了在字典上太强或NP-难检验的假设下准确地重构S稀疏信号。此外，这些结果在实践中可能是悲观的，因为它们是基于最坏情况的分析。在本文中，我们考虑定义在图上的信号的稀疏恢复，对于该图，字典采用关联矩阵的形式。我们导出了稀疏恢复的充要条件，这些条件依赖于图的可在多项式时间内检查的圈的性质。我们还导出了稀疏恢复的支持度相关条件，这些条件仅依赖于图的圈与信号支持度的交集。最后，我们利用度量的稀疏性和关联矩阵的结构提出了一种专门的基于子图的恢复算法，该算法的性能优于标准的HELL{1}最小化方法。
Classical results in sparse recovery guarantee the exact reconstruction of s-sparse signals under assumptions on the dictionary that are either too strong or NP-hard to check. Moreover, such results may be pessimistic in practice since they are based on a worst-case analysis. In this paper, we consider the sparse recovery of signals defined over a graph, for which the dictionary takes the form of an incidence matrix. We derive necessary and sufficient conditions for sparse recovery, which depend on properties of the cycles of the graph that can be checked in polynomial time. We also derive support-dependent conditions for sparse recovery that depend only on the intersection of the cycles of the graph with the support of the signal. Finally, we exploit sparsity properties on the measurements and the structure of incidence matrices to propose a specialized sub-graph-based recovery algorithm that outperforms the standard $\ell_{1}$ -minimization approach.