---
title: "Density Corrected Sparse Recovery when R.I.P. Condition Is Broken"
authors:
  - "Ming Lin"
  - "Zhen-Zhong Lan"
  - "Alexander G. Hauptmann"
doi: ""
url: "https://ijcai.org/proceedings/2015/515"
pdf: "https://ijcai.org/proceedings/2015/0515.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "3664-3669"
track: "Special Track on Machine Learning"
keywords:
---

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

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

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, 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.