CS: The real long post of the week

If you are doing research in the audio/sound business, I just asked a question on Bob Sturm's blog. In other news, how do you know Compressive Sensing is making it in the mainstream ? what about it being featured in a course not focused on compressed sensing as in lecture 23 (Dynamic MRI image reconstruction. PDF, PPTX ) of the following course CS5540: Computational Techniques for Analyzing Clinical Data taught by Ramin Zabih and Ashish Raj at Cornell. In the meantime, here is an application in MRI that features a more advanced subject than just reconstruction as traditionally done in compressive sensing. Kayhan Batmanghelich, a long time reader of this blog, sent me the following:

Dear Igor

My name is Kayhan Batmanghelich and I am graduate student in University of Pennsylvania. I have followed your informative weblog over past three years and I have sent you emails before if you remember. I would like to draw your attention to a new paper by myself and my advisors Christos Davatzikos and Ben Taskar:

title: Application of Trace-Norm and Low-Rank Matrix Decomposition for
Computational Anatomy
web:https://www.rad.upenn.edu/sbia/Nematollah.Batmanghelich/Kayhan.Batmanghelich/Publications_files/PID1265849.pdf

This paper is accepted in MMBIA (CVPR workshop in Mathematical Methods
in Biomedical Image Analysis)

Basically, this is an application of Robust Principal Component Analysis paper (by Candes, [1]) that you addressed earlier. Actually, I came up with the idea when I read your post back in 2009. This is still quite preliminary work and we still need to work on it more but I thought you may want to check it out.


Regards,
Kayhan
[1] E. J. Candès, X. Li, Y. Ma, and J. Wright. Robust Principal Component Analysis

Thanks Kayhan. The paper and the abstract are here: Application of Trace-Norm and Low-Rank Matrix Decomposition for Computational Anatomy by Nematollah Batmanghelich, Ali Gooya, Stathis Kanterakis, Ben Taskar, Christos Davatzikos. The abstract reads:

We propose a generative model to distinguish normal anatomical variations from abnormal deformations given a group of images with normal and abnormal subjects. We assume that abnormal subjects share common factors which characterize the abnormality. These factors are hard to discover due to large variance of normal anatomical differences. Assuming that the deformation fields are parametrized by their stationary velocity fields, these factors constitute a low-rank subspace (abnormal space) that is corrupted by high variance normal anatomical differences. We assume that these normal anatomical variations are not correlated. We form an optimization problem and propose an efficient iterative algorithm to recover the low-rank subspace. The algorithm iterates between image registration and the decomposition steps and hence can be seen as a group-wise registration algorithm. We apply our method on synthetic and real data and discover abnormality of the population that cannot be recovered by some of the well-known matrix decompositions (e.g. Singular Value Decomposition).

This is a very smart decomposition!

If you recall a previous entry on the subject of combinatorial software testing, I just found the following relevant presentation on the subject of group testing and software: Combinatorial Group Testing for Software Integration by Leslie Wu. Interesting outlook. Which brings me to the following two papers:

Efficiently Decodable Non-adaptive Group Testing by Piotr Indyk, Hung Q. Ngo and Atri Rudra. The abstract reads:

We consider the following \efficiently decodable" nonadaptive group testing problem. There is an unknown string x 2 f0; 1gn with at most d ones in it. We are allowed to test any subset S [n] of the indices. The answer to the test tells whether xi = 0 for all i 2 S or not. The objective is to design as few tests as possible (say, t tests) such that x can be identi ed as fast as possible (say, poly(t)-time). Efficiently decodable non-adaptive group testing has applications in many areas, including data stream algorithms and data forensics. A non-adaptive group testing strategy can be represented by a t x n matrix, which is the stacking of all the characteristic vectors of the tests. It is well-known that if this matrix is d-disjunct, then any test outcome corresponds uniquely to an unknown input string. Furthermore, we know how to construct d-disjunct matrices with t = O(d2 log n) efficiently. However, these matrices so far only allow for a \decoding" time of O(nt), which can be exponentially larger than poly(t) for relatively small values of d. This paper presents a randomness efficient construction of d-disjunct matrices with t = O(d2 log n) that can be decoded in time poly(d) t log2 t + O(t2). To the best of our knowledge, this is the rst result that achieves an efficient decoding time and matches the best known O(d2 log n) bound on the number of tests. We also derandomize the construction, which results in a polynomial time deterministic construction of such matrices when d = O(log n= log log n). A crucial building block in our construction is the notion of (d; `)-list disjunct matrices, which represent the more general \list group testing" problem whose goal is to output less than d + ` positions in x, including all the (at most d) positions that have a one in them. List disjunct matrices turn out to be interesting objects in their own right and were also considered independently by [Cheraghchi, FCT 2009]. We present connections between list disjunct matrices, expanders, dispersers and disjunct matrices. List disjunct matrices have applications in constructing (d; `)- sparsity separator structures [Ganguly, ISAAC 2008] and in constructing tolerant testers for Reed-Solomon codes in the data stream model.

and A survey on Sparse Recovery Using Sparse Matrices by Anna Gilbert and Piotr Indyk. The abstract reads:

We survey algorithms for sparse recovery problems that are based on sparse random matrices. Such matrices has several attractive properties: they support algorithms with low computational complexity, and make it easy to perform incremental updates to signals. We discuss applications to several areas, including compressive sensing, data stream computing and group testing.

From one of the author, we also have:
Lower Bounds for Sparse Recovery by Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodru ff . The abstract reads:

We consider the following k-sparse recovery problem: design an m x n matrix A, such that for any signal x, given Ax we can efficiently recover ^x satisfying kx �� ^xk1 C mink-sparse x0 kx �� x0k1. It is known that there exist matrices A with this property that have only O(k log(n=k)) rows. In this paper we show that this bound is tight. Our bound holds even for the more general randomized version of the problem, where A is a random variable, and the recovery algorithm is required to work for any xed x with constant probability (over A).

Isn't it time we refer to group testing as a way of doing compressed sensing ?

Of interest, we have:
High-Dimensional Matched Subspace Detection When Data are Missing by Laura Balzano, Robert Nowak, and Benjamin Recht. The abstract reads:

We consider the problem of deciding whether a highly incomplete signal lies within a given subspace. This problem, Matched Subspace Detection, is a classical, wellstudied problem when the signal is completely observed. Highdimensional testing problems in which it may be prohibitive or impossible to obtain a complete observation motivate this work. The signal is represented as a vector in Rn, but we only observe m n of its elements.We show that reliable detection is possible, under mild incoherence conditions, as long as m is slightly greater than the dimension of the subspace in question.

Expanding the realm of the 1-bit compressed sensing subject here is: Sample Complexity for 1-bit Compressed Sensing and Sparse Classification by Ankit Gupta, Robert Nowak, and Benjamin Recht. The abstract reads:

This paper considers the problem of identifying the support set of a high-dimensional sparse vector, from noise corrupted 1-bit measurements. We present passive and adaptive algorithms for this problem, both requiring no more than O(d log(D)) measurements to recover the unknown support. The adaptive algorithm has the additional benefit of robustness to the dynamic range of the unknown signal.

From one off the same author, it looks like we have a revised version of Null Space Conditions and Thresholds for Rank Minimization by Benjamin Recht, Weiyu Xu, Babak Hassibi. The abstract reads:

Minimizing the rank of a matrix subject to constraints is a challenging problem that arises in many applications in Machine Learning, Control Theory, and discrete geometry. This class of optimization problems, known as rank minimization, is NP-HARD, and for most practical problems there are no efficient algorithms that yield exact solutions. A popular heuristic replaces the rank function with the nuclear norm|equal to the sum of the singular values|of the decision variable and has been shown to provide the optimal low rank solution in a variety of scenarios. In this paper, we assess the practical performance of this heuristic for finding the minimum rank matrix subject to linear equality constraints. We characterize properties of the null space of the linear operator de fining the constraint set that are necessary and sufficient for the heuristic to succeed. We then analyze linear constraints sampled uniformly at random, and obtain dimension-free bounds under which our null space properties hold almost surely as the matrix dimensions tend to in nity. Finally, we provide empirical evidence that these probabilistic bounds provide accurate predictions of the heuristic's performance in non-asymptotic scenarios.

Compressing POMDPs using Locality Preserving Non-Negative Matrix Factorization by Georgios Theocharous and Sridhar Mahadevan. The abstract reads:

Partially Observable Markov Decision Processes (POMDPs) are a well-established and rigorous framework for sequential decision-making under uncertainty. POMDPs are well-known to be intractable to solve exactly, and there has been significant work on finding tractable approximation methods. One well-studied approach is to find a compression of the original POMDP by projecting the belief states to a lower-dimensional space. We present a novel dimensionality reduction method for POMDPs based on locality preserving non-negative matrix factorization. Unlike previous approaches, such as Krylov compression and regular non-negative matrix factorization, our approach preserves the local geometry of the belief space manifold. We present results on standard benchmark POMDPs showing improved performance over previously explored compression algorithms for POMDPs.

Proximal Methods for Sparse Hierarchical Dictionary Learning by Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, Francis Bach. The abstract reads:

We propose to combine two approaches for modeling data admitting sparse representations: on the one hand, dictionary learning has proven effective for various signal processing tasks. On the other hand, recent work on structured sparsity provides a natural framework for modeling dependencies between dictionary elements. We thus consider a tree-structured sparse regularization to learn dictionaries embedded in a hierarchy. The involved proximal operator is computable exactly via a primal-dual method, allowing the use of accelerated gradient techniques. Experiments show that for natural image patches, learned dictionary elements organize themselves in such a hierarchical structure, leading to an improved performance for restoration tasks. When applied to text documents, our method learns hierarchies of topics, thus providing a competitive alternative to probabilistic topic models.

The following is a surprising paper: Probabilistic Matching Pursuit for Compressive Sensing by Atul Divekar, Okan Ersoy. The introduction reads:

Compressive sensing investigates the recovery of a signal that can be sparsely represented in an orthonormal basis or overcomplete dictionary given a small number of linear combinations of the signal. We present a novel matching pursuit algorithm that uses the measurements to probabilistically select a subset of bases that is likely to contain the true bases constituting the signal. The algorithm is successful in recovering the original signal in cases where deterministic matching pursuit algorithms fail. We also show that exact recovery is possible when the number of nonzero coefficients is upto one less than the number of measurements. This overturns a previously held assumption in compressive sensing research.

From the Rice page, there is now an updated version of Model selection: Two fundamental measures of coherence and their algorithmic significance by Waheed U. Bajwa, Robert Calderbank, and Sina Jafarpour. The abstract reads:

The problem of model selection arises in a number of contexts, such as compressed sensing, subset selection in linear regression, estimation of structures in graphical models, and signal denoising. This paper generalizes the notion of \emph{incoherence} in the existing literature on model selection and introduces two fundamental measures of coherence---termed as the worst-case coherence and the average coherence---among the columns of a design matrix. In particular, it utilizes these two measures of coherence to provide an in-depth analysis of a simple one-step thresholding (OST) algorithm for model selection. One of the key insights offered by the ensuing analysis is that OST is feasible for model selection as long as the design matrix obeys an easily verifiable property. In addition, the paper also characterizes the model-selection performance of OST in terms of the worst-case coherence, \mu, and establishes that OST performs near-optimally in the low signal-to-noise ratio regime for N x C design matrices with \mu = O(N^{-1/2}). Finally, in contrast to some of the existing literature on model selection, the analysis in the paper is nonasymptotic in nature, it does not require knowledge of the true model order, it is applicable to generic (random or deterministic) design matrices, and it neither requires submatrices of the design matrix to have full rank, nor does it assume a statistical prior on the values of the nonzero entries of the data vector.

and Dictionary Optimization for Block-Sparse Representations by Kevin Rosenblum, Lihi Zelnik-Manor, Yonina Eldar. The abstract reads:

Recent work has demonstrated that using a carefully designed dictionary instead of a predefined one, can improve the sparsity in jointly representing a class of signals. This has motivated the derivation of learning methods for designing a dictionary which leads to the sparsest representation for a given set of signals. In some applications, the signals of interest can have further structure, so that they can be well approximated by a union of a small number of subspaces (e.g., face recognition and motion segmentation). This implies the existence of a dictionary which enables block-sparse representations of the input signals once its atoms are properly sorted into blocks. In this paper, we propose an algorithm for learning a block-sparsifying dictionary of a given set of signals. We do not require prior knowledge on the association of signals into groups (subspaces). Instead, we develop a method that automatically detects the underlying block structure. This is achieved by iteratively alternating between updating the block structure of the dictionary and updating the dictionary atoms to better fit the data. Our experiments show that for block-sparse data the proposed algorithm significantly improves the dictionary recovery ability and lowers the representation error compared to dictionary learning methods that do not employ block structure.

In a different direction, we have: Optimized intrinsic dimension estimation using nearest neighbor graphs by Kumar Sricharan, Raviv Raich, Alfred O. Hero III. The abstract reads:

We develop an approach to intrinsic dimension estimation based on k-nearest neighbor (kNN) distances. The dimension estimator is derived using a general theory on functionals of kNN density estimates. This enables us to predict the performance of the dimension estimation algorithm. In addition, it allows for optimization of free parameters in the algorithm. We validate our theory through simulations and compare our estimator to previous kNN based dimensionality estimation approaches.

An Improved Estimate for Restricted Isometry Constant for the \ell_1 Minimization by Ming-Jun Lai. The abstract reads:

In [4], Candes proved that when the restricted isometry constant 2s < 1="2.">

Jieping Ye has a tutorial given at SDM10: Mining Sparse Representations: Formulations, Algorithms, and Applications.

From the Modern Massive Data Sets Workshop page:

Registration is now open:

MMDS is now accepting registration from corporate, government, academic and student participants. The event dates are June 15-18th. Please proceed to the registration page to ensure your spot at the event. http://stanford.edu/group/mmds/registration.html

Finally, there is an ONR workshop on Compressive Sensing starting tomorrow at Georgia Tech, here is the page, here are the abstracts (lots of good stuff). Hopefully, we'll be able to see videos or the presentations at some point in the future:

Stan Oscher

The unreasonable effectiveness of Bregman iteration for L1 based optimization, with some new applications

Bregman distance was invented in 1967 and has been used in various guises for optimization since then, without remarkable success. It turns out to be a very effective tool for L1 type optimization for reasons involving error forgiving and forgetting. I'll discus this and give some relatively new applications involving hyperpectral data and inverse problems, some involving source separation. This is joint with Wotao Yin and others.

Don Goldfarb

Fast First-Order Algorithms for Compressed Sensing and Related Problems

We propose several new first-order augmented Lagrangian methods for miniminzing the sum of several functions subject to linear constraints.

In the first half of the talk the functions are assumed to be smooth (or have been appropriately smoothed) and both Gauss-Seidel-like and Jacobi-like algorithms are presented that compute an epsilon-optimal solution in O(1/epsilon) iterations. Nesterov-like accelerated versions that have an O(1/sqrt(epsilon)) iteration complexity are also given.

In the second half of the talk we present an algorithm that applies directly to functions that are norms without requiring them to be smoothed, without any degredation of theoretical performance (i.e., complexity).

In addition to recovery problems in compressed sensing, the problems that can be solved by our algorithms include matrix completion, robust PCA, sparse PCA, sparse inverse covariance for graphical model selection and optimal acquisition basis selection (e.g., for radar). Numerical results on video surveillance problems involving 30M variables will be presented.

Wotao Yin

Some practical compressive sensing algorithms and their applications

The talk will cover a series of fast algorithms for compressive sensing and imaging using Fourier, circulant/Toeplitz, and multiple-channel samples. They run in seconds on a laptop for reconstructing million-pixel images. We show how to port some of these algorithms to GPUs for even faster computation. Various recent applications in imaging and in wireless communication are demonstrated.

Arkadi Nemirovski

Efficiently Computable Compressed Sensing -- Progress Report

In the talk, we overview the results obtained by the GaTech team during the second year of the project, with emphasis on:

1) Applications of verifiable sufficient conditions for a sensing matrix to be ``s-good'' (to allow for exact ℓ1-recovery of signals with at most s nonzero entries via noiseless observations) in design and analysis of Non-Euclidean Matching Pursuit recovery algorithms and error bounds for ℓ1 recovery in the presence of Gaussian observation noise,

2) Developing new deterministic and randomized algorithms for large-scale ℓ1 minimization, and

3) Low rank matrix approximations, with applications to synthesis problem in compressed sensing.

Robert Calderbank

Why Leave it to Chance?

Larry Carin

Nonparametric Bayesian recovery of highly incomplete & noisy image measurements

In most previous compressive sensing research it is assumed that the signal of interest may be sparsely represented in a known basis. In this work we learn over-complete dictionaries for imagery, with the dictionary learning performed in situ on highly incomplete and noisy imagery (no training data required). We show how this extends matrix completion to the problem of data completion, where the data live on a low-dimensional union of subspaces (matrix completion is a special case, of a single linear subspace). The nonparametric techniques build upon the beta process and the Indian buffet process, with several example results presented for natural imagery, with comparisons made to competing approaches.

Rama Chellappa

In this talk, I will discuss the effectiveness of compressive sensing techniques for several still and video-based computer vision problems. Specifically, we will demonstrate the role of compressive sensing methods for 3D modeling from gradients, background subtraction and tracking in a camera network, acquisition of BRDFs and in efficient acquisition of scenes modeled by dynamic texture models.

Compressive Sensing for Computer Vision

Volkan Cevher

Progress on Model-based Compressive Sensing

Karim Sabra

Compressive Matched Field Processing

Sound source localization in shallow water environment is commonly doneusing Matched Field Processing (MFP). MFP is usually implemented by systematically placing a test point source at each point of a search grid, computing the acoustic field (replicas) at all the elements of the array and then correlating this modeled field with the data from the real point source whose localization is unknown to determine the best-fit location. However, a direct implementation of MFP (i.e. brute force search) over a large grid space-or search area- is computationally demanding especially in the presence of complex propagation environments. We formulated instead the localization problem of a few acoustic sources as the sparse approximation of the measured signals in a specific dictionary of atoms obtained from discretization of this sparse search space. Spatial random projections are performed to efficiently span the search space. This Compressive MFP approach allows for significant computation time savings with a computational cost increasing with the number of random projections instead of the number of search grid points. The performance of this approach will be illustrated using numerical and experimental data in a shallow water waveguide.

Justin Romberg

Compressed sensing and multiple channel estimation

We will start by showing how the theory of compressed sensing can be applied to two problems in MIMO channel estimation. In the first, we show how the computations required to simulate an acoustic environment can be "compressed" through simultaneous source activation. In the second, we show how the problem of communicating reliably through an unknown (but sparse) channel can be recast as sparse recovery problem, and discuss how data can be ``protected'' against multipath interference using a random embedding. We will also discuss some preliminary theoretical results we have for the amount of redundancy in the embedding versus the number of taps we can protect against in the multipath channel.

In the second half of the talk, we will discuss matched filtering in the compressed domain (the so called ``smashed filter''). Using tools from the theory of empirical processes, we show that very few measurements are needed to reliably perform a matched filtering in the compressed domain, and give precise bounds on the variance of the noise that such a process can tolerate.

Joel Tropp

Finding structure with randomness: Stochastic algorithms for constructing low-rank matrix decompositions

Computer scientists have long known that randomness can be used to improve the performance of algorithms. A familiar application is the process of dimension reduction, in which a random map transports data from a high-dimensional space to a lower-dimensional space while approximately preserving some geometric properties. By operating with the compact representation of the data, it is theoretically possible to produce approximate solutions to certain large problems very efficiently.

Recently, it has been observed that dimension reduction has powerful applications in numerical linear algebra and numerical analysis. This talk provides a high-level introduction to randomized methods for computing standard matrix approximations, and it summarizes a new analysis that offers (nearly) optimal bounds on the performance of these methods. In practice, the techniques are so effective that they compete with---or even outperform---classical algorithms. Since matrix approximations play a ubiquitous role in areas ranging from information processing to scientific computing, it seems certain that randomized algorithms will eventually supplant the standard methods in some application domains.