How to use real-valued sparse recovery algorithms for complex-valued sparse recovery?
How to use real-valued sparse recovery algorithms for complex-valued sparse recovery?
复制标题
DOI：
10.5281/zenodo.52350
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
Arsalan Sharifnassab;M. Kharratzadeh;M. Babaie-zadeh;C. Jutten
中科院分区：
文献类型：
--
作者：
Arsalan Sharifnassab;M. Kharratzadeh;M. Babaie-zadeh;C. Jutten
在过去的十年里，求解欠定线性方程组的稀疏解(即所谓的稀疏恢复问题)得到了广泛的研究，因为它在许多不同的领域都有应用。因此，现在有许多稀疏恢复算法(和程序代码)可用。然而，这些算法中的大多数都是为实值系统开发的。本文还讨论了一种使用现有的实值算法(或程序代码)来解决复值问题的方法。其基本思想是将复值问题转化为等价的实值问题，并使用任意实值稀疏恢复算法来求解这种新的实值问题。还将讨论这种方法成功的理论保证。另一方面，一种广泛使用的稀疏恢复思想是寻找最小ℓ1范数解。对于实值系统，这种思想需要求解线性规划(LP)问题，而对于复值系统，它需要求解二阶锥规划(SOCP)问题，这需要更多的计算量。然而，基于本文的方法，复杂的情况也可以用线性规划来解决，尽管找到稀疏解的理论保证是有限的。
Finding the sparse solution of an underdetermined system of linear equations (the so called sparse recovery problem) has been extensively studied in the last decade because of its applications in many different areas. So, there are now many sparse recovery algorithms (and program codes) available. However, most of these algorithms have been developed for real-valued systems. This paper discusses an approach for using available real-valued algorithms (or program codes) to solve complex-valued problems, too. The basic idea is to convert the complex-valued problem to an equivalent real-valued problem and solve this new real-valued problem using any real-valued sparse recovery algorithm. Theoretical guarantees for the success of this approach will be discussed, too. On the other hand, a widely used sparse recovery idea is finding the minimum ℓ1 norm solution. For real-valued systems, this idea requires to solve a linear programming (LP) problem, but for complex-valued systems it needs to solve a second-order cone programming (SOCP) problem, which demands more computational load. However, based on the approach of this paper, the complex case can also be solved by linear programming, although the theoretical guarantee for finding the sparse solution is more limited.