Compressibility of Deterministic and Random Infinite Sequences

被引：40

作者：

Amini, Arash ^{[1
]}

Unser, Michael ^{[2
]}

Marvasti, Farokh ^{[1
]}

机构：

[1] Sharif Univ Technol, Adv Commun Res Inst ACRI, Dept Elect Engn, Tehran 113659363, Iran

[2] Ecole Polytech Fed Lausanne, Biomed Imaging Grp BIG, CH-1015 Lausanne, Switzerland

来源：

IEEE TRANSACTIONS ON SIGNAL PROCESSING | 2011年 / 59卷 / 11期

基金：

瑞士国家科学基金会;

关键词：

Compressible prior; heavy-tail distribution; order statistics; stable law;

D O I：

10.1109/TSP.2011.2162952

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

We introduce a definition of the notion of compressibility for infinite deterministic and i.i.d. random sequences which is based on the asymptotic behavior of truncated subsequences. For this purpose, we use asymptotic results regarding the distribution of order statistics for heavy-tail distributions and their link with alpha-stable laws for1 < alpha < 2. In many cases, our proposed definition of compressibility coincides with intuition. In particular, we prove that heavy-tail (polynomial decaying) distributions fulfill the requirements of compressibility. On the other hand, exponential decaying distributions like Laplace and Gaussian do not. The results are such that two compressible distributions can be compared with each other in terms of their degree of compressibility.

引用

页码：5193 / 5201

页数：9

共 15 条

[1]

Candes E. J., 2006, P INT C MATH MADR SP, V3, P1433, DOI DOI 10.4171/022-3/69

[2] Robust uncertainty principles:: Exact signal reconstruction from highly incomplete frequency information [J].

Candès, EJ ;

Romberg, J ;

Tao, T .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (02) :489-509

[3] Near-optimal signal recovery from random projections: Universal encoding strategies? [J].

Candes, Emmanuel J. ;

Tao, Terence .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (12) :5406-5425

[4]

Cevher V., 2008, NEUR INF PROC SYST N

[5]

Cevher V, 2009, 2009 IEEE INFORMATION THEORY WORKSHOP (ITW 2009), P353, DOI 10.1109/ITW.2009.5351508

[6]

Cohen A, 2009, J AM MATH SOC, V22, P211

[7]

DeVore R. A., 1998, Acta Numerica, V7, P51, DOI 10.1017/S0962492900002816

[8] Compressed sensing [J].

Donoho, DL .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (04) :1289-1306

[9]

Feller W., 1991, INTRO PROBABILITY TH, V2

[10]

Gribonval R., 2011, COMPRESSIBLE PRIORS

← 1 2 →