2013/06/11 by Myung Cho, Cho, Myung, Weiyu Xu +1
Computer Science · Engineering · #Blind Source Separation Techniques #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1306.2665
openalex publication_date 2013/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
In this paper, we propose new efficient algorithms to verify the null space condition in compressed sensing (CS). Given an (n-m) × n (m>0) CS matrix A and a positive k, we are interested in computing αk = max_\z: Az=0,z≠ 0\max_\K: |K|≤ k\ ‖zK ‖1‖z‖1, where K represents subsets of \1,2,...,n\, and |K| is the cardinality of K. In particular, we are interested in finding the maximum k such that αk < 12. However, computing αk is known to be extremely challenging. In this paper, we first propose a series of new polynomial-time algorithms to compute upper bounds on αk. Based on these new polynomial-time algorithms, we further design a new sandwiching algorithm, to compute the exact αk with greatly reduced complexity. When needed, this new sandwiching algorithm also achieves a smooth tradeoff between computational complexity and result accuracy. Empirical results show the performance improvements of our algorithm over existing known methods; and our algorithm outputs precise values of αk, with much lower complexity than exhaustive search.