Idioma:

Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit

Donoho, D. L. ; Tsaig, Y. ; Drori, I. ; Starck, J-L

IEEE transactions on information theory, 2012-02, Vol.58 (2), p.1094-1121 [Periódico revisado por pares]

New York, NY: IEEE

Texto completo disponível

Citações Citado por

Enviar para

Título:
Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit
Autor: Donoho, D. L. ; Tsaig, Y. ; Drori, I. ; Starck, J-L
Assuntos: Applied sciences ; Approximation ; Approximation methods ; Approximations ; Coding, codes ; Compressed sensing ; Decoding ; decoding error-correcting codes ; Detection, estimation, filtering, equalization, prediction ; ell _{1} minimization ; Equations ; Error correction & detection ; Exact sciences and technology ; false alarm rate ; false discovery rate ; Gaussian noise ; Information theory ; Information, signal and communications theory ; iterative thresholding ; Least squares method ; Linear algebra ; Linear equations ; Matching ; Matching pursuit algorithms ; Mathematical analysis ; Mathematical models ; Minimization ; mutual access interference ; phase transition ; Sampling, quantization ; Signal and communications theory ; Signal, noise ; Sparse matrices ; sparse overcomplete representation ; Sparsity ; stepwise regression ; Telecommunications and information theory ; Vectors
É parte de: IEEE transactions on information theory, 2012-02, Vol.58 (2), p.1094-1121
Notas: ObjectType-Article-2
SourceType-Scholarly Journals-1
ObjectType-Feature-1
content type line 23
Descrição: Finding the sparsest solution to underdetermined systems of linear equations y = Φ x is NP-hard in general. We show here that for systems with "typical"/"random" Φ, a good approximation to the sparsest solution is obtained by applying a fixed number of standard operations from linear algebra. Our proposal, Stagewise Orthogonal Matching Pursuit (StOMP), successively transforms the signal into a negligible residual. Starting with initial residual r 0 = y , at the s -th stage it forms the "matched filter" Φ T rs-1 , identifies all coordinates with amplitudes exceeding a specially chosen threshold, solves a least-squares problem using the selected coordinates, and subtracts the least-squares fit, producing a new residual. After a fixed number of stages (e.g., 10), it stops. In contrast to Orthogonal Matching Pursuit (OMP), many coefficients can enter the model at each stage in StOMP while only one enters per stage in OMP; and StOMP takes a fixed number of stages (e.g., 10), while OMP can take many (e.g., n ). We give both theoretical and empirical support for the large-system effectiveness of StOMP. We give numerical examples showing that StOMP rapidly and reliably finds sparse solutions in compressed sensing, decoding of error-correcting codes, and overcomplete representation.
Editor: New York, NY: IEEE
Idioma: Inglês

Links

View record in Pascal Francis

Voltar para lista de resultados

Realização: Logos de Redes Sociais:

Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit

Donoho, D. L. ; Tsaig, Y. ; Drori, I. ; Starck, J-L

New York, NY: IEEE

Buscando em bases de dados remotas. Favor aguardar.