Compressed Counting Meets Compressed Sensing

Ping Li, Cun-Hui Zhang, Tong Zhang
Proceedings of The 27th Conference on Learning Theory, PMLR 35:1058-1077, 2014.

Abstract

Compressed sensing (sparse signal recovery) has been a popular and important research topic in recent years. By observing that natural signals (e.g., images or network data) are often nonnegative, we propose a framework for nonnegative signal recovery using \em Compressed Counting (CC). CC is a technique built on \em maximally-skewed α-stable random projections originally developed for data stream computations (e.g., entropy estimations). Our recovery procedure is computationally efficient in that it requires only one linear scan of the coordinates. In our settings, the signal \mathbfx∈\mathbbR^N is assumed to be nonnegative, i.e., x_i≥0, ∀i. We prove that, when α∈(0, 0.5], it suffices to use M=(C_α+o(1)) ε^-α \left(\sum_i=1^N x_i^α\right)\log N/δmeasurements so that, with probability 1-δ, all coordinates will be recovered within εadditive precision, in one scan of the coordinates. The constant C_α=1 when α\rightarrow0 and C_α=\pi/2 when α=0.5. In particular, when α\rightarrow0, the required number of measurements is essentially M=K\log N/δ, where K = \sum_i=1^N 1{x_i≠0} is the number of nonzero coordinates of the signal.

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-li14, title = {Compressed Counting Meets Compressed Sensing}, author = {Li, Ping and Zhang, Cun-Hui and Zhang, Tong}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {1058--1077}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/li14.pdf}, url = {https://proceedings.mlr.press/v35/li14.html}, abstract = {Compressed sensing (sparse signal recovery) has been a popular and important research topic in recent years. By observing that natural signals (e.g., images or network data) are often nonnegative, we propose a framework for nonnegative signal recovery using \em Compressed Counting (CC). CC is a technique built on \em maximally-skewed α-stable random projections originally developed for data stream computations (e.g., entropy estimations). Our recovery procedure is computationally efficient in that it requires only one linear scan of the coordinates. In our settings, the signal \mathbfx∈\mathbbR^N is assumed to be nonnegative, i.e., x_i≥0, ∀i. We prove that, when α∈(0, 0.5], it suffices to use M=(C_α+o(1)) ε^-α \left(\sum_i=1^N x_i^α\right)\log N/δmeasurements so that, with probability 1-δ, all coordinates will be recovered within εadditive precision, in one scan of the coordinates. The constant C_α=1 when α\rightarrow0 and C_α=\pi/2 when α=0.5. In particular, when α\rightarrow0, the required number of measurements is essentially M=K\log N/δ, where K = \sum_i=1^N 1{x_i≠0} is the number of nonzero coordinates of the signal.} }
Endnote
%0 Conference Paper %T Compressed Counting Meets Compressed Sensing %A Ping Li %A Cun-Hui Zhang %A Tong Zhang %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-li14 %I PMLR %P 1058--1077 %U https://proceedings.mlr.press/v35/li14.html %V 35 %X Compressed sensing (sparse signal recovery) has been a popular and important research topic in recent years. By observing that natural signals (e.g., images or network data) are often nonnegative, we propose a framework for nonnegative signal recovery using \em Compressed Counting (CC). CC is a technique built on \em maximally-skewed α-stable random projections originally developed for data stream computations (e.g., entropy estimations). Our recovery procedure is computationally efficient in that it requires only one linear scan of the coordinates. In our settings, the signal \mathbfx∈\mathbbR^N is assumed to be nonnegative, i.e., x_i≥0, ∀i. We prove that, when α∈(0, 0.5], it suffices to use M=(C_α+o(1)) ε^-α \left(\sum_i=1^N x_i^α\right)\log N/δmeasurements so that, with probability 1-δ, all coordinates will be recovered within εadditive precision, in one scan of the coordinates. The constant C_α=1 when α\rightarrow0 and C_α=\pi/2 when α=0.5. In particular, when α\rightarrow0, the required number of measurements is essentially M=K\log N/δ, where K = \sum_i=1^N 1{x_i≠0} is the number of nonzero coordinates of the signal.
RIS
TY - CPAPER TI - Compressed Counting Meets Compressed Sensing AU - Ping Li AU - Cun-Hui Zhang AU - Tong Zhang BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-li14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 1058 EP - 1077 L1 - http://proceedings.mlr.press/v35/li14.pdf UR - https://proceedings.mlr.press/v35/li14.html AB - Compressed sensing (sparse signal recovery) has been a popular and important research topic in recent years. By observing that natural signals (e.g., images or network data) are often nonnegative, we propose a framework for nonnegative signal recovery using \em Compressed Counting (CC). CC is a technique built on \em maximally-skewed α-stable random projections originally developed for data stream computations (e.g., entropy estimations). Our recovery procedure is computationally efficient in that it requires only one linear scan of the coordinates. In our settings, the signal \mathbfx∈\mathbbR^N is assumed to be nonnegative, i.e., x_i≥0, ∀i. We prove that, when α∈(0, 0.5], it suffices to use M=(C_α+o(1)) ε^-α \left(\sum_i=1^N x_i^α\right)\log N/δmeasurements so that, with probability 1-δ, all coordinates will be recovered within εadditive precision, in one scan of the coordinates. The constant C_α=1 when α\rightarrow0 and C_α=\pi/2 when α=0.5. In particular, when α\rightarrow0, the required number of measurements is essentially M=K\log N/δ, where K = \sum_i=1^N 1{x_i≠0} is the number of nonzero coordinates of the signal. ER -
APA
Li, P., Zhang, C. & Zhang, T.. (2014). Compressed Counting Meets Compressed Sensing. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:1058-1077 Available from https://proceedings.mlr.press/v35/li14.html.

Related Material