Achievable angles between two compressed sparse vectors under norm/distance constraints imposed by the restricted isometry property: A plane geometry approach

Ling Hua Chang, Jwo-Yuh Wu

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

The angle between two compressed sparse vectors subject to the norm/distance constraints imposed by the restricted isometry property (RIP) of the sensingmatrix plays a crucial role in the studies of many compressive sensing (CS) problems. Assuming that 1) u and v are two sparse vectors with and 2) the sensing matrix satisfies RIP, this paper is aimed at analytically characterizing the achievable angles between and . Motivated by geometric interpretations of RIP and with the aid of the well-known law of cosines, we propose a plane-geometry-based formulation for the study of the considered problem. It is shown that all the RIP-induced norm/distance constraints on and can be jointly depicted via a simple geometric diagram in the 2-D plane. This allows for a joint analysis of all the considered algebraic constraints from a geometric perspective. By conducting plane geometry analyses based on the constructed diagram, closed-form formulas for the maximal and minimal achievable angles are derived. Computer simulations confirm that the proposed solution is tighter than an existing algebraic-based estimate derived using the polarization identity. The obtained results are used to derive a tighter restricted isometry constant of structured sensing matrices of a certain kind, to wit, those in the form of a product of an orthogonal projection matrix and a random sensing matrix. Follow-up applications in CS are also discussed.

Original languageEnglish
Article number6384745
Pages (from-to)2059-2081
Number of pages23
JournalIEEE Transactions on Information Theory
Volume59
Issue number4
DOIs
StatePublished - Apr 2013

Keywords

  • Compressive sensing (CS)
  • Plane geometry
  • Restricted isometry constant (RIC)
  • Restricted isometry property (RIP)

Fingerprint

Dive into the research topics of 'Achievable angles between two compressed sparse vectors under norm/distance constraints imposed by the restricted isometry property: A plane geometry approach'. Together they form a unique fingerprint.

Cite this