Universal compressed sensing

Shirin Jalali; H. Vincent Poor

doi:10.1109/ISIT.2016.7541723

Universal compressed sensing

Shirin Jalali, H. Vincent Poor

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Scopus citations

Abstract

In this paper, the problem of developing universal algorithms for noiseless compressed sensing of stochastic processes is studied. First, Rényi's notion of information dimension (ID) is generalized to analog stationary processes. This provides a measure of complexity for such processes and is connected to the number of measurements required for their accurate recovery. Then the so-called Lagrangian minimum entropy pursuit (Lagrangian-MEP) algorithm, originally proposed by Baron et al. as a heuristic universal recovery algorithm, is studied. It is shown that, if the normalized number of randomized measurements is larger than the ID of the source process, for the right set of parameters, asymptotically, the Lagrangian-MEP algorithm recovers any stationary process satisfying some mixing constraints almost losslessly, without having any prior information about the source distribution.

Original language	English (US)
Title of host publication	Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2369-2373
Number of pages	5
ISBN (Electronic)	9781509018062
DOIs	https://doi.org/10.1109/ISIT.2016.7541723
State	Published - Aug 10 2016
Event	2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain Duration: Jul 10 2016 → Jul 15 2016

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2016-August
ISSN (Print)	2157-8095

Other

Other	2016 IEEE International Symposium on Information Theory, ISIT 2016
Country/Territory	Spain
City	Barcelona
Period	7/10/16 → 7/15/16

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Keywords

Compressed Sensing
Information Dimension
Mixing processes
Universal coding

Access to Document

10.1109/ISIT.2016.7541723

Cite this

@inproceedings{1c0ef788cc1d476fb607d45ddca99d7f,

title = "Universal compressed sensing",

abstract = "In this paper, the problem of developing universal algorithms for noiseless compressed sensing of stochastic processes is studied. First, R{\'e}nyi's notion of information dimension (ID) is generalized to analog stationary processes. This provides a measure of complexity for such processes and is connected to the number of measurements required for their accurate recovery. Then the so-called Lagrangian minimum entropy pursuit (Lagrangian-MEP) algorithm, originally proposed by Baron et al. as a heuristic universal recovery algorithm, is studied. It is shown that, if the normalized number of randomized measurements is larger than the ID of the source process, for the right set of parameters, asymptotically, the Lagrangian-MEP algorithm recovers any stationary process satisfying some mixing constraints almost losslessly, without having any prior information about the source distribution.",

keywords = "Compressed Sensing, Information Dimension, Mixing processes, Universal coding",

author = "Shirin Jalali and Poor, {H. Vincent}",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 2016 IEEE International Symposium on Information Theory, ISIT 2016 ; Conference date: 10-07-2016 Through 15-07-2016",

year = "2016",

month = aug,

day = "10",

doi = "10.1109/ISIT.2016.7541723",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2369--2373",

booktitle = "Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory",

address = "United States",

}

Jalali, S & Poor, HV 2016, Universal compressed sensing. in Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory., 7541723, IEEE International Symposium on Information Theory - Proceedings, vol. 2016-August, Institute of Electrical and Electronics Engineers Inc., pp. 2369-2373, 2016 IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, 7/10/16. https://doi.org/10.1109/ISIT.2016.7541723

Universal compressed sensing. / Jalali, Shirin; Poor, H. Vincent.
Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory. Institute of Electrical and Electronics Engineers Inc., 2016. p. 2369-2373 7541723 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Universal compressed sensing

AU - Jalali, Shirin

AU - Poor, H. Vincent

PY - 2016/8/10

Y1 - 2016/8/10

N2 - In this paper, the problem of developing universal algorithms for noiseless compressed sensing of stochastic processes is studied. First, Rényi's notion of information dimension (ID) is generalized to analog stationary processes. This provides a measure of complexity for such processes and is connected to the number of measurements required for their accurate recovery. Then the so-called Lagrangian minimum entropy pursuit (Lagrangian-MEP) algorithm, originally proposed by Baron et al. as a heuristic universal recovery algorithm, is studied. It is shown that, if the normalized number of randomized measurements is larger than the ID of the source process, for the right set of parameters, asymptotically, the Lagrangian-MEP algorithm recovers any stationary process satisfying some mixing constraints almost losslessly, without having any prior information about the source distribution.

AB - In this paper, the problem of developing universal algorithms for noiseless compressed sensing of stochastic processes is studied. First, Rényi's notion of information dimension (ID) is generalized to analog stationary processes. This provides a measure of complexity for such processes and is connected to the number of measurements required for their accurate recovery. Then the so-called Lagrangian minimum entropy pursuit (Lagrangian-MEP) algorithm, originally proposed by Baron et al. as a heuristic universal recovery algorithm, is studied. It is shown that, if the normalized number of randomized measurements is larger than the ID of the source process, for the right set of parameters, asymptotically, the Lagrangian-MEP algorithm recovers any stationary process satisfying some mixing constraints almost losslessly, without having any prior information about the source distribution.

KW - Compressed Sensing

KW - Information Dimension

KW - Mixing processes

KW - Universal coding

UR - http://www.scopus.com/inward/record.url?scp=84985905101&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84985905101&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2016.7541723

DO - 10.1109/ISIT.2016.7541723

M3 - Conference contribution

AN - SCOPUS:84985905101

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2369

EP - 2373

BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016

Y2 - 10 July 2016 through 15 July 2016

ER -

Universal compressed sensing

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this