CS: New Bounds for RICs, Stable Recovery of Sparse Signals, Shifting Inequality and Recovery of Sparse Signals, Super-Resolution, OPTSPACE, PARNES

Recently, the NESTA reconstruction solver was updated to version 1.0. Today, we are presented with a reconstruction solver that aims at merging the good parts of both SPGL1 and NESTA in a potentially more rapid and robust solver called PARNES and introduced in PARNES: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals by Ming Gu, Lek-Heng Lim, Cinna Julie Wu. The abstract reads:

In this article we propose an algorithm, PARNES, for the basis pursuit denoise problem which approximately finds a minimum one-norm solution to an underdetermined least squares problem. PARNES, (1) combines what we think are the best features of currently available methods SPGL1 and NESTA, and (2) incorporates a new improvement that exhibits linear convergence under the assumption of the restricted isometry property (RIP). As with SPGL1, our approach 'probes the Pareto frontier' and determines a solution to the BPDN problem by exploiting its relation between the LASSO problem as given by their Pareto curve. As with NESTA we rely on the accelerated proximal gradient method proposed by Yu. Nesterov that takes a remarkable O((L/e)^1/2) iterations to come within e > 0 of the optimal value, where L is the Lipschitz constant of the gradient of the objective function. Furthermore we introduce an 'outer loop' that regularly updates the prox center. Nesterov's accelerated proximal gradient method then becomes the 'inner loop'. The restricted isometry property together with the Lipschitz differentiability of our objective function permits us to derive a condition for switching between the inner and outer loop in a provably optimal manner. A by-product of our approach is a new algorithm for the LASSO problem that also exhibits linear convergence under RIP.

The paper shows a comparison with some of the fastest code available (all of them, except for FISTA can be found on the reconstruction section of the Big Picture in Compressive Sensing). Lek-Heng tells me that an implementation of the code will be released as soon as the code is cleaned up and some improvements are made.

Also found on the internets: New Bounds for Restricted Isometry Constants by T. Tony Cai, Lie Wang, Guangwu Xu. The abstract reads:

In this paper we show that if the restricted isometry constant \delta k of the compressed sensing matrix satisfies \delta_k < deltak ="(">

and Stable Recovery of Sparse Signals and an Oracle Inequality by T. Tony Cai, Lie Wang, Guangwu Xu. The abstract reads:

This article considers sparse signal recovery in the presence of noise. A mutual incoherence condition which was previously used for exact recovery in the noiseless case is shown to be sufficient for stable recovery in the noisy case. Both bounded noise and Gaussian noise settings are considered. Furthermore, the condition is shown to be sharp. In addition, an oracle inequality is given under the mutual incoherence condition.

and finally the same authors have found a weaker condition than the traditional RIP in Shifting Inequality and Recovery of Sparse Signals by T. Tony Cai, Lie Wang, Guangwu Xu. The abstract reads:

In this paper we present a concise and coherent analysis of the constrained l1 minimization method for stable recovering of high-dimensional sparse signals both in the noiseless case and noisy case. The analysis is surprisingly simple and elementary, while leads to strong results. In particular, it is shown that the sparse recovery problem can be solved via l1 minimization under weaker conditions than what is known in the literature. A key technical tool is an elementary inequality, called Shifting Inequality, which, for a given nonnegative decreasing sequence, bounds the l2 norm of a subsequence in terms of the l1 norm of another subsequence by shifting the elements to the upper end.

In a different direction, we have: Super-Resolution and Reconstruction of Sparse Sub-Wavelength Images by Snir Gazit, Alexander Szameit, Yonina Eldar, Mordechai Segev. The abstract reads:

We use compressed sensing to demonstrate theoretically the reconstruction of sub-wavelength features from measured far-field, and provide experimental proof-of-concept. The methods can be applied to non-optical microscopes, provided the information is sparse.

and in the matrix completion area: OPTSPACE: A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion by by Raghunandan Keshavan, Andrea Montanari and Sewoong Oh. The abstract reads:

We consider the problem of reconstructing a low-rank matrix from a small subset of its entries. In this paper, we describe the implementation of an efficient algorithm called OptSpace, based on singular value decomposition followed by local manifold optimization, for solving the low-rank matrix completion problem. It has been shown that if the number of revealed entries is large enough, the output of singular value decomposition gives a good estimate for the original matrix, so that local optimization reconstructs the correct matrix with high probability. We present numerical results which show that this algorithm can reconstruct the low rank matrix exactly from a very small subset of its entries. We further study the robustness of the algorithm with respect to noise, and its performance on actual collaborative filtering datasets.

As mentioned earlier, the OPTSPACE code can be found here.

CS: Separable imagers, Compressed Imaging with a Separable Sensing Operator, Calibration issues of CS systems, Expander-based Compressed Sensing

As you probably recall (see here), one of the main issue with the Random Lens Imager, a system I consider to be a truly innovative Compressive Sensing system, is the amount of time spent in the calibration process. For what it's worth, I note that it's been nearly three years now since the report has been out but has, to my limited knowledge, not been published. Which makes me wonder sometimes about how truly innovative approaches have real difficulty making it into the literature.

In a presentation by Yair Rivenson and Adrian Stern on An Efficient Method for Multi-Dimensional Compressive Imaging, one can see the problem being expressed in plain words:

and how their approach (using separable sensing systems) can reduce that burden. The price to pay for not spending years in the calibration process seems to be more than a fair one:

The authors also want to use that type of approaches for r-dimensional signals where r is above 2.

A more in-depth explanation of the presentation's results can be found in Compressed Imaging with a Separable Sensing Operator by Yair Rivenson and Adrian Stern. The abstract reads:

Compressive imaging (CI) is a natural branch of compressed sensing (CS). Although a number of CI implementations have started to appear, the design of efficient CI system still remains a challenging problem. One of the main difficulties in implementing CI is that it involves huge amounts of data, which has far-reaching implications for the complexity of the optical design, calibration, data storage and computational burden. In this paper, we solve these problems by using a twodimensional separable sensing operator. By so doing, we reduce the complexity by factor of 10^6 for megapixel images. We show that applying this method requires only a reasonable amount of additional samples.

Let us recall that we have already seen this approach before ( see the work of Yin Zhang and others like Thong Do and John Sidles (see comments)) but it certainly is a good thing to now see the minimal price to be paid in exchange of this Kronecker product approach to imaging and other systems.

There are really two other ways to reduce that calibration burden of finding what the point spread function (or transfer function for higher dimensional problems) is: One could make the assumption that the measurement matrix is sparse and evaluate this issue as a compressed sensing problem called Blind Deconvolution or use a physical system that implements a sparse measurement system (RIP-1 matrices) such as in the new paper: Expander-based Compressed Sensing in the presence of Poisson Noise by Sina Jafarpour, Rebecca Willett, Maxim Raginsky, Robert Calderbank. The abstract reads:

This paper provides performance bounds for compressed sensing in the presence of Poisson noise using expander graphs. The Poisson noise model is appropriate for a variety of applications, including low-light imaging and digital streaming, where the signal-independent and/or bounded noise models used in the compressed sensing literature are no longer applicable. In this paper, we develop a novel sensing paradigm based on expander graphs and propose a MAP algorithm for recovering sparse or compressible signals from Poisson observations. The geometry of the expander graphs and the positivity of the corresponding sensing matrices play a crucial role in establishing the bounds on the signal reconstruction error of the proposed algorithm. The geometry of the expander graphs makes them provably superior to random dense sensing matrices, such as Gaussian or partial Fourier ensembles, for the Poisson noise model. We support our results with experimental demonstrations.

CS: Xampling, Compressive Wide-Band Spectrum Sensing, An unconstrained lq minimization, Random matrices are democratic

http://www.technion.ac.il/~elron/

From the folks who brought us the Modulated Wideband Converter hardware, here is the design methodology underneath it called Xampling which in effect deals with Compressive Sensing for Analog signals: Xampling -- Part I: Practice by Moshe Mishali, Yonina Eldar and Asaf Elron . The abstract reads:

We introduce Xampling, a design methodology for sub-Nyquist sampling of continuous-time analog signals. The main principles underlying this framework are the ability to capture a broad signal model, low sampling rate, efficient analog and digital implementation and lowrate baseband processing. The main hypothesis of Xampling is that in order to break through the Nyquist barrier, one has to combine classic methods and results from sampling theory together with recent developments from the literature of compressed sensing. In this paper, we present the Xampling framework and examine several sub-Nyquist approaches in light of the four Xampling principles. It is shown that previous methods suffer from analog implementation issues, large computational loads in the digital domain, and have no baseband processing capabilities. An exception is the recently proposed modulated wideband converter (MWC) which satisfies the model, rate and implementation criteria, though lacking the baseband processing capability. Here, we extend the MWC by proposing a digital algorithm which extracts each band of the signal from the compressed measurements, thus enabling lowrate (baseband) processing. The converter with the proposed algorithm conforms with the Xampling desiderata. In addition, we describe two configurations of the converter for efficient spectrum sensing in wideband cognitive radio receivers. In the second part of this work we study theoretical aspects of rate and stability of sub-Nyquist systems, following the pragmatic theme of the Xampling methodology.

At the end of the paper, the author uses the example of the cognitive Radio which eventually led me to the following two papers and thesis: Distributed Compressive Wide-Band Spectrum Sensing by Ying Wang, Ashish Pandharipande, Yvan Lamelas Polo and Geert Leusy. The abstract reads:

—We consider a compressive wide-band spectrum sensing scheme for cognitive radio networks. Each cognitive radio (CR) sensing receiver transforms the received analog signal from the licensed system in to a digital signal using an analog-to-information converter. The autocorrelation of the compressed signal is then collected from each CR at a fusion center. A compressive sampling recovery algorithm that exploits joint sparsity is then employed to reconstruct an estimate of the signal spectrum and used to make a decision on signal occupancy. We compare the performance of this distributed compressive spectrum sensing scheme with a compressive spectrum sensing scheme at a single CR and show the performance gains obtained from spatial diversity.

and Compressive Wide-Band Spectrum Sensing by Ying Wang, Ashish Pandharipande, Yvan Lamelas Polo and Geert Leusy. The abstract reads:

We present a compressive wide-band spectrum sensing scheme for cognitive radios. The received analog signal at the cognitive radio sensing receiver is transformed in to a digital signal using an analog-to-information converter. The autocorrelation of this compressed signal is then used to reconstruct an estimate of the signal spectrum. We evaluate the performance of this scheme in terms of the mean squared error of the power spectrum density estimate and the probability of detecting signal occupancy.

And finally, to Yvan Lamelas Polo's thesis entitled: Compressive Wideband Spectrum Sensing for Cognitive Radio Applications with the following abstract:

It has been widely recognized that utilization of radio spectrum by licensed wireless systems, e.g., TV broadcasting, aeronautical telemetry, is quite low. In particular, at any given time and spatial region, there are frequency bands where there is no signal occupancy. There has been recent interest in improving spectrum utilization by permitting secondary usage using cognitive radios. Cognitive radios use spectrum sensing to determine frequency bands that are vacant of licensed signal transmissions and transmit on such portions to meet regulatory constraints of avoiding harmful interference to licensed systems. Future cognitive radios will be capable of scanning a wide band of frequencies, in the order of a few GHz, and employ adaptive waveforms for transmission depending on the estimated spectrum of licensed systems. In this thesis, we address the problem of estimating the spectrum of the wide-band signal received at the cognitive radio sensing receiver using compressive sampling coupled with a multiband spectrum detector to determine the spectrum occupancy of the licensed system. Since individual cognitive radios might not be able to reliably detect weak primary signals due to channel fading/shadowing, we also propose a distributed compressive scheme based on joint recovery of the license occupancy for application scenarios involving geographically distributed radios. In such a distributed approach, the spectrum occupancy is determined by the joint work of cognitive radios (exploiting spatial diversity), as opposed to being determined individually by each cognitive radio.

In a different direction, here is another intriguing paper on a reweighted algorithm dealing with l_q problems: An unconstrained lq minimization for sparse solution of under determined linear systems by Ming-Jun Lai and Jingyue Wang. The abstract reads:

We study an unconstrained version of the ℓq minimization for the sparse solution of under-determined linear systems for 0 \lt q \le 1. Although the minimization is nonconvex, we introduce a regularization and develop an iterative algorithm. We show that the iterative solutions converge to the sparse solution. Numerical experiments will be demonstrated to show that our approach works very well.

I note the following from their paper:

According to our theory, we can completely determine a sparse solution without any conditions, e.g., the restricted isometry property (RIP) on matrix A. This is an another advantage of the ℓq minimization for 0 \lt q \lt 1 over the classic ℓ1 minimization approach.

Their algorithm looks like a reweighted scheme and as one can read from the paper, it takes a long time to converge, much like the IRLS scheme. Finally, let us note the success of this algorithm with uniform random matrices.

And finally from the Rice Compressive Sensing Repository we have:

A simple proof that random matrices are democratic by Mark Davenport, Jason Laska, Petros Boufounos, and Richard Baraniuk. The abstract reads:

The recently introduced theory of compressive sensing (CS) enables the reconstruction of sparse or compressible signals from a small set of nonadaptive, linear measurements. If properly chosen, the number of measurements can be significantly smaller than the ambient dimension of the signal and yet preserve the significant signal information. Interestingly, it can be shown that random measurement schemes provide a near-optimal encoding in terms of the required number of measurements. In this report, we explore another relatively unexplored, though often alluded to, advantage of using random matrices to acquire CS measurements. Specifically, we show that random matrices are democractic, meaning that each measurement carries roughly the same amount of signal information. We demonstrate that by slightly increasing the number of measurements, the system is robust to the loss of a small number of arbitrary measurements. In addition, we draw connections to oversampling and demonstrate stability from the loss of significantly more measurements.

CS: Compressive Confocal Microscope, Compressive Matched Subspace Detection, Music Classification, Matrix Completion, Metric Learning

Before we get to the meat of today's entry, let me invite y'all to use the customized search engine on the right hand side of this blog to search for entries relevant to your area of interest. The search feature on the top left corner of this blog is buggy at best and does not do a good job of finding relevant entries when you are using only one word. Also, of related interest, I am seeking a Google Wave invite as I am interested to see if one could develop some compressive sensing hardware with some folks of the open hardware community. Irrespective to your ability to send me an Google Wave invite, you are welcome to join that experiment. [Hint to those of you working at Google, I just made a request for an invite]

It seems that I overlooked the work being done by the group of Gonzalo Arce at University of Delaware. I hope to remedy this today. From his group, we have a new compressive sensing hardware, a music classifier, and other relevant studies in between. The hardware first as exposed in : Compressive Confocal Microscopy by Peng Ye, Jose Paredes, Gonzalo Arce, Yichuan Hu , C. Chen, and Dennis Prather.The abstract reads:

In this paper, a new framework for confocal microscopy based on the novel theory of compressive sensing is proposed. Unlike wide field microscopy or conventional parallel beam confocal imaging systems that use charge-coupled devices (CCD) as acquisition devices in addition to complex mechanical scanning system, the proposed compressive confocal microscopy is a kind of parallel beam confocal imaging system which exploits the rich theory of compressive sensing by using a single pixel detector and a digital micromirror device (DMD) to capture linear projections of the in-focus image. With the proposed system, confocal imaging of high optical sectioning ability can be achieved at sub-Nyquist sampling rates. Theoretical analysis, simulations and experimental results are shown to demonstrate the characteristics and potential of the proposed approach.

and the attendant reconstruction paper: Compressive Confocal Microscopy: 3D reconstruction algorithms by Peng Ye, Jose Paredes, Yichuan Hu , C. Chen, Gonzalo Arce and Dennis Prather. The abstract reads:

In this paper, a new approach for Confocal Microscopy (CM) based on the framework of compressive sensing is developed. In the proposed approach, a point illumination and a random set of pinholes are used to eliminate out-of-focus information at the detector. Furthermore, a Digital Micromirror Device (DMD) is used to efficiently scan the 2D or 3D specimen but, unlike the conventional CM that uses CCD detectors, the measured data in the proposed compressive confocal microscopy (CCM) emerge from random sets of pinhole illuminated pixels in the specimen that are linearly combined (projected) and measured by a single photon detector. Compared to conventional CM or programmable array microscopy (PAM), the number of measurements needed for nearly perfect reconstruction in CCM is significantly reduced. Our experimental results are based on a testbed that uses a Texas Instruments DMD (an array of 1024£768; 13:68£13:68 ¹m2 mirrors) for computing the linear projections of illuminated pixels and a single photon detector is used to obtain the compressive sensing measurement. The position of each element in the DMD is defined by the compressed sensing measurement matrices. Three dimensional image reconstruction algorithms are developed that exploit the inter-slice spatial image correlation as well as the correlation between different 2D slices. A comprehensive performance comparison between several binary projection patterns is shown. Experimental and simulation results are provided to illustrate the features of the proposed systems.

I'll add it to the Compressive Sensing Hardware page.

From the same group, we also have: Non-Linear Coding for Improved Performance in Compressive Sensing by Yichuan Hu, Zhongmin Wang, Javier Garcia-Frias, and Gonzalo Arce. The abstract reads:

We propose a system based on the combination of compressive sensing and non-linear processing that shows excellent robustness against noise. The key idea is the use of nonlinear mappings that act as analog joint source-channel encoders, processing the compressive sensing measurements proceeding from an analog source and producing continuous amplitude samples that are transmitted directly through the noisy channel. As we will show in our simulation results, the proposed framework is readily applicable in practical systems such as imaging, and clearly outperforms systems based on stand-alone compressive sensing.

and the next two papers focus in the adaptive detection of signals of interest while in the compressed measurement world: Compressive Matched Subspace Detection by Jose Paredes, Zhongmin Wang, Gonzalo Arce and Brian M. Sadler. The abstract reads:

In this paper, matched subspace detectors based on the framework of Compressive Sensing (CS) are developed. The proposed approach, called compressive matched subspace detectors, exploits the sparsity model of the signal-of-interest in the design of the random projection operator. By tailoring the CS measurement matrix (projection operator) to the subspace where the signal-of-interest is known to lie, the compressive matched subspace detectors can effectively capture the signal energy while the interference and noise effects are mitigated at sub-Nyquist rate. The proposed detection approach is particularly suitable for detection of wideband signals that emerge in modern communication systems that demand high-speed ADCs. The performance of the subspace compressive detectors are studied by analytically deriving closed-form expressions for the detection probability and through extensive simulations.

Variable Density Compressive Image Sampling by Zhongmin Wang, Gonzalo Arce and Jose Paredes. The abstract reads:

Compressed sensing (CS) provides an efficient way to acquire and reconstruct natural images from a reduced number of linear projection measurements at sub-Nyquist sampling rates. A key to the success of CS is the design of the measurement ensemble. This paper addresses the design of a novel variable density sampling strategy, where the “a priori” information about the statistical distributions that natural images exhibit in the wavelet domain is exploited. Compared to the current sampling schemes for compressed image sampling, the proposed variable density sampling has the following advantages: 1) The number of necessary measurements for image reconstruction is reduced; 2) The proposed sampling approach can be applied to several transform domains leading to simple implementations. In particular, the proposed method is applied to the compressed sampling in the 2D ordered discrete Hadamard transform (DHT) domain for spatial domain imaging. Furthermore, to evaluate the incoherence of different sampling schemes, a new metric that incorporates the “a priori” information is also introduced. Extensive simulations show the effectiveness of the proposed sampling methods.

Finally, a continuation of the concepts developed in the classification on faces, shows that music is not the same as faces: Music Genre Classification via Sparse Representation of Auditory Temporal Modulations by Yannis Panagakis, Constantine Kotropoulos, Gonzalo Arce. The abstract reads:

A robust music genre classification framework is proposed that combines the rich, psycho-physiologically grounded properties of slow temporal modulations of music recordings and the power of sparse representation-based classifiers. Linear subspace dimensionality reduction techniques are shown to play a crucial role within the framework under study. The proposed method yields a music genre classification accuracy of 91% and 93.56% on the GTZAN and ISMIR2004 Genre dataset, respectively. Both accuracies outperform any reported accuracy ever obtained by state of the art music genre classification algorithms in the aforementioned datasets.

Finally, in a totally unrelated field, we have: Matrix Completion from Power-Law Distributed Samples by Raghu Meka, Prateek Jain, and Inderjit Dhillon. The abstract reads:

The low-rank matrix completion problem is a fundamental problem with many important applications. Recently, [4],[13] and [5] obtained the first non-trivial theoretical results for the problem assuming that the observed entries are sampled uniformly at random. Unfortunately, most real-world datasets do not satisfy this assumption, but instead exhibit power-law distributed samples. In this paper, we propose a graph theoretic approach to matrix completion that solves the problem

for more realistic sampling models. Our method is simpler to analyze than previous methods with the analysis reducing to computing the threshold for complete cascades in random graphs, a problem of independent interest. By analyzing the graph theoretic problem, we show that our method achieves exact recovery when the observed entries are sampled from the Chung-Lu-Vu model, which can generate power-law distributed graphs. We also hypothesize that our algorithm solves the matrix completion problem from an optimal number of entries for the popular preferential attachment model and provide strong empirical evidence for the claim. Furthermore, our method is easy to implement and is substantially faster than existing methods. We demonstrate the effectiveness of our method on random instances where the low-rank matrix is sampled according to the prevalent random graph models for complex networks and present promising preliminary results on the Netflix challenge dataset.

and from the same group, the important: Metric and Kernel Learning using a Linear Transformation by Prateek Jain, Brian Kulis, Jason Davis and Inderjit Dhillon. The abstract reads:

Metric and kernel learning are important in several machine learning applications. However, most existing metric learning algorithms are limited to learning metrics over low-dimensional data, while existing kernel learning algorithms are often limited to the transductive setting and do not generalize to new data points. In this paper, we study metric learning as a problem of learning a linear transformation of the input data. We show that for high-dimensional data, a particular framework for learning a linear transformation of the data based on the LogDet divergence can be efficiently kernelized to learn a metric (or equivalently, a kernel function) over an arbitrarily high dimensional space. We further demonstrate that a wide class of convex loss functions for learning linear transformations can similarly be kernelized, thereby considerably expanding the potential applications of metric learning. We demonstrate our learning approach by applying it to large-scale real world problems in computer vision and text mining.

CS: New version of ISD and attendant video tutorials

You probably recall the concept of ISD, a reconstruction solver that uses all measurements available to compute a solution. Well, Wotao Yin just sent me the following:

I put a very clean and simple ISD code at http://www.caam.rice.edu/~optimization/L1/ISD/. It comes with two video tutorials.

Here is extract of what's new in the package:

Version 1.1 (November 3, 2009). [download]

• This version is much simpler and clearer than ver 1.0 below.
• Video tutorials: Demo [online] or [download]; Main code [online] or [download].
• To adapter the code to your data and sparse/compressible signal and for best results, please (i) tune the thresholding methods and parameters, and (ii) consider replacing YALL1 by one designed for your data. The technical report [pdf] describes ideas of effective thresholding.
• Despite the small problems given in the demos, the code is capable of solving large-scale, multi-dimensional problems. Ver 1.0 below includes large-scale tests. The allowed size of the problem is merely subject to the limit posted by the subproblem solver used.
• The main code can be extended to deal with multi-dimensional signals in a straightforward way.

Enjoy !

The Nuit Blanche Effect

When was the last time you knew for a fact that more than 120 people had read the abstract of your paper within a week of releasing it ?





Back in May 2008 at the Nonlinear L1 meeting at Texas A&M University, we were having lunch with Adam Oberman, Anna Gilbert and Simon Foucart. During the conversation, I suddenly realized the power of the blog when, out of the blue, Adam mentioned to me that he knew of the blog (first big surprise, we are in College Station, Texas and somebody has heard of the blog :-)) through a friend who had seen a spike of downloads for his paper after being mentioned here (second surprise!). Ever since that moment I have been trying to quantify this effect which, it seems, has grown over time. If you have stories about this or any other stories connected to the blog (you can stay anonymous), I would be very happy to hear them. Let us note that this number is a conservative one as it does not include the people being directly mailed the blog entries (237 as we speak), nor the people coming directly to the website nor people using another feed than the one listed above (412).

One more note, the first technincal blog entry after that meeting pointed out the need to understand better the RIP (Restricted Isometry Property: What is it good for ?), a subject of continuing interest.

CS: UWB Through-Wall Imaging Based on Compressive Sensing

I picked this up from Lianlin Li's blog ( translation is here): another UWB radar that can detect moving things through walls: UWB Through-Wall Imaging Based on Compressive Sensing by Qiong Huang, Lele Qu, Bingheng Wu, and Guangyou Fang. The abstract reads:

To achieve high-resolution 2-D images, through-wall imaging (TWI) radar with ultra-wideband and long antenna arrays faces considerable technical challenges such as a prolonged data collection time, a huge amount of data, and a high hardware complexity. This paper presents a novel data acquisition scheme and an imaging algorithm for TWI radar based on compressive sensing (CS), which states that a signal having a sparse representation can be reconstructed from a small number of nonadaptive randomized projections by solving a tractable convex program. Instead of measuring all spatial-frequency data, a few samples, by employing an overcomplete dictionary, are sufficient to obtain reliable target space images even at high noise levels. Preliminary simulated and experimental results show that the proposed algorithm outperforms the conventional delay-and-sum beamforming method even though many fewer CS measurements are used.

I am adding this the Compressive Sensing Hardware page.

CS: A Matrix Completion Entry

After Friday's entry on the subject, here some more matrix completion cods and papers:Yi Ma just sent me the following:

You may want to check out our new website dedicated for low-rank matrix recovery and completion at:

http://perception.csl.illinois.edu/matrix-rank/home.html

Matrix recovery (also known as robust PCA) is arguably a more difficult problem that matrix completion and it reveals some nice tradeoff between rank and sparsity. On the website we gather all up to date work on theory, algorithms, and applications (soon). We also provide the code for the fastest algorithms know todate for both matrix recovery and completion.

I note that they list the other matrix completion approaches here.

and then we have: A Simpler Approach to Matrix Completion by Benjamin Recht. The abstract reads:

This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low rank matrix. These results improve on prior work by Candes and Recht, Candes and Tao, and Keshavan, Montanari, and Oh. The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular values, of the hidden matrix subject to agreement with the provided entries. If the underlying matrix satisfies a certain incoherence condition, then the number of entries required is equal to a quadratic logarithmic factor times the number of parameters in the singular value decomposition. The proof of this assertion is short, self contained, and uses very elementary analysis. The novel techniques herein are based on recent work in quantum information theory.

and Compressed Quantum Process Tomography by Alireza Shabani, R. L. Kosut, Herschel Rabitz. The abstract reads:

The characterization of a decoherence process is among the central challenges in quantum physics. A major difficulty with current quantum process tomography methods is the enormous number of experiments needed to accomplish a tomography task. Here we present a highly efficient method for tomography of a quantum process that has a small number of significant elements. Our method is based on the compressed sensing techniques being used in information theory. In this new method, for a system with Hilbert space dimension n and a process matrix of dimension n^2 x n^2 with sparsity s, the required number of experimental configurations is O(s log n^4). This heralds a logarithmic advantage in contrast to other methods of quantum process tomography. More specifically, for q-qubits with n=2^q, the scaling of resources is O(sq) linear in the product of sparsity and number of qubits.

CS: Real vs. complex null space properties, Non-Parametric Bayesian Dictionary Learning, Coordinate Descent Optimization code

Today, we have two papers and two codes:

Real vs. complex null space properties for sparse vector recovery by Simon Foucart, Remi Gribonval. The abstract reads:

We identify and solve an overlooked problem about the characterization of underdetermined systems of linear equations for which sparse solutions have minimal `1-norm. This characterization is known as the null space property. When the system has real coefficients, sparse solutions can be considered either as real or complex vectors, leading to two seemingly distinct null space properties. We prove that the two properties actually coincide by establishing a link with a problem about convex polygons in the real plane. Incidentally, we also show the equivalence between stable null space properties which account for the stable reconstruction by `1-minimization of vectors that are not exactly sparse.

Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations by Mingyuan Zhou, Haojun Chen, John Paisley, Lu Ren, Guillermo Sapiro and Lawrence Carin. The abstract reads:

Non-parametric Bayesian techniques are considered for learning dictionaries for sparse image representations, with applications in denoising, inpainting and compressive sensing (CS). The beta process is employed as a prior for learning the dictionary, and this non-parametric method naturally infers an appropriate dictionary size. The Dirichlet process and a probit stick-breaking process are also considered to exploit structure within an image. The proposed method can learn a sparse dictionary in situ; training images may be exploited if available, but they are not required. Further, the noise variance need not be known, and can be nonstationary. Another virtue of the proposed method is that sequential inference can be readily employed, thereby allowing scaling to large images. Several example results are presented, using both Gibbs and variational Bayesian inference, with comparisons to other state-of-the-art approaches.

From the BCS webpage:

BPFA image denoising and inpainting: The package includes the inference update equations and Matlab codes for image denoising and inpainting via the non-parametric Bayesian dictionary learning approach.

Download: BPFA.zip (Last Updated: Oct. 30, 2009)

Back in March I mentioned the following paper Coordinate Descent Optimization for $\ell^1$ Minimization with Application to Compressed Sensing; a Greedy Algorithm by Yingying Li and Stanley Osher. The code is now available on Matlab Central.


Credit: OnOrbit, X-prize, Unreasonable rocket.

CS: Recovering low-rank matrices from few coefficients in any basis, Probability of Unique Integer Solution to a System of Linear Equations

Two items first. In yesterday's entry on the Sudoku paper ( Linear Systems, Sparse Solutions, and Sudoku by Prabhu Babu, Kristiaan Pelckmans, Petre Stoica, and Jian Li) it is interesting to find out that a re-weighted scheme seems to be doing better than some game specific greedy algorithm. Furthermore, at the end of the paper, we can read the following:

The presently known sufficient conditions on A for checking the equivalence of P0 and P1, like the restricted isometry property (RIP) [5] and Kashin, Garnaev, Gluskin (KGG) inequality [6], do not hold for Sudoku. So analyzing the equivalence of l0 and l1 norm solutions in the context of Sudoku requires novel conditions for sparse recovery.

I am not sure that RIP of [5] is the condition to check for here, (RIP-2) more likely the sparsity of the measurement matrix implies some type of RIP-1 condition. I also thought KGG was a necessary and sufficient condition albeit an NP-Hard at that. Other conditions can be found on the Compressive Sensing Big Picture page.

In the super-resolution paper mentioned earlier this week, entitled Super-resolution ghost imaging via compressive sampling reconstruction by Wenlin Gong and Shensheng Han, Wenlin confirms to me that only l1_magic was used not GPSR as the reference would tend to indicate. I am sure we are going to see some improvement in the near future. Other reconstruction solvers can be found in the Compressive Sensing Big Picture page too.

David Gross just sent me the following:

...I'm a physicist and new to the field. Originally, some colleagues and me got interested in compressed sensing and matrix completion in the context of quantum state tomography (meaning the experimental characterization of a quantum system). Our paper arXiv:0909.3304 was mentioned on your blog.

The methods we needed to develop in order to translate known results on matrix completion by Candes, Recht, Tao and others to quantum mechanics proved far more general than anticipated. We can now show that a low-rank (n x n)-matrix may be recovered from basically O(n r log^2 n) randomly selected expansion coefficients with respect to any matrix basis. The matrix completion problem is just a special case.

Most importantly, though, the complexity of the proofs was reduced substantially. The spectacular argument by Candes and Tao in arXiv:0903.1476 covered about 40 pages. The new paper implies these results, but is much simpler to digest.

The first version of the paper went onto the arxiv two weeks ago: arXiv:0910.1879. However, it significantly evolved since then. In some cases the bounds are now down to O(n r log n), which -- I'm happy to say -- is tight up to multiplicative factors.

There is an obvious challenge to be met. The O(n r log n)-bounds do not currently extend to the original matrix completion problem. They come tantalizingly close, though, with only one single lemma obstructing a more general result. The precise problem is pointed out at the end of Section III B.

Before submitting the paper, I plan to add a final note. The statements all continue to be true if instead of a matrix basis a "tight frame" (a.k.a. "overcomplete basis") is used.

I should also point out Benjamin Recht's recent and strongly related pre-print arXiv:0910.0651 to you. He independently translated some of the results in our earlier paper on quantum tomography to the matrix completion problem (apparently overlooking our announcement of exactly the same result in the physics paper).

Let us note that the last preprint of Benjamin Recht was recently updated. But first, here is the new revision entitled: Recovering low-rank matrices from few coefficients in any basis by David Gross

We establish novel techniques for analyzing the problem of low-rank matrix recovery. The methods are both considerably simpler, and more general than previous approaches. It is shown that an unknown n × n matrix of rank r can be efficiently reconstructed given knowledge of only O(nr \nu log2 n) randomly sampled expansion coefficients with respect to any given matrix basis. The number \nu quantifies the “degree of incoherence” between the unknown matrix and the basis. Existing work concentrated mostly on the problem of “matrix completion”, where one aims to recover a low-rank matrix from randomly selected matrix elements. Our result covers this situation as a special case. The proof consists of a series of relatively elementary steps, which stands in contrast to the highly involved methods previously employed to obtain comparable results. In cases where bounds had been known before, our estimates are slightly tighter. We discuss operator bases which are incoherent to all low-rank matrices simultaneously. For these bases, we show that O(nr \nu log n) randomly sampled expansion coefficients suffice to recover any low-rank matrix with high probability. The latter bound is tight up to multiplicative factors. This seems to be the first time the optimal order of the log-factor has been proved to be achievable for a matrix reconstruction problem where neither the basis nor the unknown matrix is randomized. This work is an expanded presentation of the recent pre-print [D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert, arxiv:0909.3304] which was aimed at researches working in quantum information theory.

Thanks David !

I also found the following: Probability of Unique Integer Solution to a System of Linear Equations by Olvi Mangasarian and Benjamin Recht. The abstract reads:

We consider a system of m linear equations in n variables Ax = d and give necessary and sufficient conditions for the existence of a unique solution to the system that is integer: x element of {−1,1}^n. We achieve this by reformulating the problem as a linear program and deriving necessary and sufficient conditions for the integer solution to be the unique primal optimal solution. We show that as long as m is larger than n/2, then the linear programming heuristic succeeds for most instances, but if m is less than n/2, the heuristic fails on most instances. We also demonstrate that these predictions match the empirical performance of the linear programming formulation to very high accuracy.

Enjoy!

Credit: NASA / GSFC / ASU, Via The Planetary Society Blog: Apollo 17 lander and flag! An image of the Apollo 17 lander, Challenger, captured by the Lunar Reconnaissance Orbiter Camera on October 1, 2009, includes not only the lander and astronaut tracks but also a fuzzy dark pixel at the location of the American flag erected there by astronauts Jack Schmitt and Gene Cernan.