Sparse Estimation From Noisy Observations of an Overdetermined Linear System / On the Randomized Kaczmarz Algorithm

I wonder why I  never see the Donoho-Tanner phase transition in these overdetermined linear systems papers. Anyway today, we have some solvers in that area: 

Sparse Estimation From Noisy Observations of an Overdetermined Linear System by Liang Dai, Kristiaan Pelckmans

This note studies a method for the efficient estimation of a finite number of unknown parameters from linear equations, which are perturbed by Gaussian noise.

In case the unknown parameters have only few nonzero entries, the proposed estimator performs more efficiently than a traditional approach. The method consists of three steps:

(1) a classical Least Squares Estimate (LSE),

(2) the support is recovered through a Linear Programming (LP) optimization problem which can be computed using a soft-thresholding step,

(3) a de-biasing step using a LSE on the estimated support set.

The main contribution of this note is a formal derivation of an associated ORACLE property of the final estimate.

That is, when the number of samples is large enough, the estimate is shown to equal the LSE based on the support of the {\em true} parameters.

On the Randomized Kaczmarz Algorithm by Liang Dai, Mojtaba Soltanalian, Kristiaan Pelckmans

The Randomized Kaczmarz Algorithm is a randomized method which aims at solving a consistent system of over determined linear equations. This note discusses how to find an optimized randomization scheme for this algorithm, which is related to the question raised by \cite{c2}. Illustrative experiments are conducted to support the findings.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.