CS: A postdoc, Spectral Estimatiion, CS of Block-Sparse, MAP Estimation, matrix rank minimizaion, Linear Transport Theory, SAIC

Wotao Yin is looking for a postdoc who would work in Compressed Sensing, Machine Learning, and Optimization at Rice University. The Department of Computational and Applied Mathematics at Rice University invites applications for a postdoctoral research associate position. The initial term of appointment is one year with a possible second year contingent upon availability of funding. The term of appointment will begin on or after August 1, 2009. The focus of the research is on compressed sensing, machine learning, optimization, as well as their applications. Candidates should have finished a PhD in applied/computational mathematics, electrical engineering, statistics, operations research, or a related field by August 2009 or the time of appointment and no earlier than December 2006. The salary will be competitive. More information is available here. The information is also listed in the Compressive Sensing job page.

Also I found the following four papers on the interwebs over the week-end. Compressive Spectral Estimation for Nonstationary Random Processes by Alexander Jung, Georg Taubock, and Franz Hlawatsch. The abstract reads:

We propose a “compressive” estimator of the Wigner-Ville spectrum (WVS) for time-frequency sparse, underspread, nonstationary random processes. A novel WVS estimator involving the signal’s Gabor coefficients on an undersampled time-frequency grid is combined with a compressed sensing transformation in order to reduce the number of measurements required. The performance of the compressive WVS estimator is analyzed via a bound on the mean square error and through simulations. We also propose an efficient implementation using a special construction of the measurement matrix.

Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery by Yonina C. Eldar, Patrick Kuppinger, Helmut Bölcskei. The abstract reads:

We consider compressed sensing of block-sparse signals, i.e., sparse signals that have nonzero coefficients occurring in clusters. An uncertainty relation for block-sparse signals is derived, based on a block-coherence measure, which we introduce. We then show that a block-version of the orthogonal matching pursuit algorithm recovers block $k$-sparse signals in no more than $k$ steps if the block-coherence is sufficiently small. The same condition on block-coherence is shown to guarantee successful recovery through a mixed $\ell_2/\ell_1$-optimization approach. This complements previous recovery results for the block-sparse case which relied on small block-restricted isometry constants. The significance of the results presented in this paper lies in the fact that making explicit use of block-sparsity can provably yield better reconstruction properties than treating the signal as being sparse in the conventional sense, thereby ignoring the additional structure in the problem.

Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing by Sundeep Rangan, Alyson K. Fletcher, Vivek K Goyal. The abstract reads:

The replica method is a non-rigorous but widely-accepted technique from statistical physics used in the asymptotic analysis of large, random, nonlinear problems. This paper applies the replica method to non-Gaussian maximum a posteriori (MAP) estimation. It is shown that with random linear measurements and Gaussian noise, the asymptotic behavior of the MAP estimate of an n-dimensional vector decouples as n scalar MAP estimators. The result is a counterpart to Guo and Verdu's replica analysis of minimum mean-squared error estimation.
The replica MAP analysis can be readily applied to many estimators used in compressed sensing, including basis pursuit, lasso, linear estimation with thresholding, and sparsity-regularized estimation. In the case of lasso estimation the scalar estimator reduces to a soft-thresholding operator, and for sparsity-regularized estimation it reduces to a hard threshold. Among other benefits, the replica method provides a computationally-tractable method for exactly computing various performance metrics including mean-squared error and sparsity pattern recovery probability.

Convergence of fixed point continuation algorithms for matrix rank minimization by Donald Goldfarb and Shiqian Ma. The abstract reads:

The matrix rank minimization problem has applications in many fields such as system identification, optimal control, low-dimensional embedding etc. As this problem is NP-hard in general, its tightest convex relaxation, the nuclear norm minimization problem is often solved instead. Recently, Ma, Goldfarb and Chen proposed a fixed point continuation algorithm for solving the nuclear norm minimization problem. By incorporating an approximate singular value decomposition technique in this algorithm, the solution to the matrix rank minimization problem is usually obtained. In this paper, we study the convergence/recoverability properties of the fixed point continuation algorithm and its variants for matrix rank minimization. Heuristics for determining the rank of the matrix when its true rank is not known are also proposed. Some of these algorithms are closely related to greedy algorithms in compressed sensing. Numerical results for these algorithms for solving affinely constrained matrix rank minimization problems are reported.

On a totally unrelated note, the book Linear Transport Theory by Kenneth M. Case and Paul F. Zweifel has been scanned by Google. This is an out of print book that is a very nice exposition of what is known as Caseology in the linear transport theory field. Caseology is the technique developed that finds the singular eigen-functions of the homogenous linear transport transport equation (they are not functions but rather distributions). As a side note, Gerry Pomraning the author of the paper above was one of the people who co-founded SAIC back in 1969, a Fortune 500 company. This really tells me that you can do linear transport theory and be an outstanding and thoughtful entrepreneur. I met him back in 1997 at the ICTT before he passed away. A very nice guy on top of his publication record. The next ICTT will take place in Torino.


Credit: NASA/JPL/Space Science Institute, Janus' Ring Shadow Premiere four days ago.