A generalized uncertainty principle and sparse representation in pairs of bases

Author

Elad, Michael ; Bruckstein, Alfred M.

Author_Institution

Dept. of Comput. Sci., Stanford Univ., CA, USA

Volume

48

Issue

9

fYear

2002

fDate

9/1/2002 12:00:00 AM

Firstpage

2558

Lastpage

2567

Abstract

An elementary proof of a basic uncertainty principle concerning pairs of representations of R^N vectors in different orthonormal bases is provided. The result, slightly stronger than stated before, has a direct impact on the uniqueness property of the sparse representation of such vectors using pairs of orthonormal bases as overcomplete dictionaries. The main contribution in this paper is the improvement of an important result due to Donoho and Huo (2001) concerning the replacement of the l₀ optimization problem by a linear programming (LP) minimization when searching for the unique sparse representation.

Keywords

dynamic programming; minimisation; signal representation; generalized uncertainty principle; linear programming minimization; optimization; orthonormal bases; overcomplete dictionaries; pairs of bases; sparse representation; uniqueness property; Cities and towns; Computer science; Dictionaries; Electronic mail; Image coding; Image processing; Linear algebra; Linear programming; Uncertainty; Vectors;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2002.801410

Filename

1027784