Proceedings

Density Corrected Sparse Recovery when R.I.P. Condition Is Broken

Ming Lin, Zhen-Zhong Lan, Alexander G. Hauptmann

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Machine Learning. Pages 3664-3669.

Abstract

The Restricted Isometric Property (R.I.P.) is a very important condition for recovering sparse vectors from high dimensional space. Traditional methods often rely on R.I.P or its relaxed variants. However, in real applications, features are often correlated to each other, which makes these assumptions too strong to be useful. In this paper, we study the sparse recovery problem in which the feature matrix is strictly non-R.I.P. We prove that when features exhibit cluster structures, which often happens in real applications, we are able to recover the sparse vector consistently. The consistency comes from our proposed density correction algorithm, which removes the variance of estimated cluster centers using cluster density. The proposed algorithm converges geometrically, achieves nearly optimal recovery bound O(s2 log(d)) where s is the sparsity and d is the nominal dimension.

Ming Lin, Zhen-Zhong Lan, and Alexander G. Hauptmann. 2015. Density Corrected Sparse Recovery when R.I.P. Condition Is Broken. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 3664–3669. https://ijcai.org/proceedings/2015/515
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards