CS: Transform the Compressive Sensing Hardware page into a review on arxiv ?

There are several long articles or chapters being written by some of you on compressive sensing (such is the case of Compressive sensing and structured random matrices by Holger Rauhut) . The focus of these efforts is mostly on the mathematical aspect of compressed sensing and there is generally a cursory note of current applications (mainly because this is not the focus of these manuscripts). I am wondering the following: Would a review of the current compressive sensing hardware as currently listed in the Compressive Sensing Hardware page be something that could be easily referenceable for these manuscripts as opposed to just having a web address ?

If there is an enterprising person or two (or more) who would want to make a name for themselves in this area I welcome any type of effort that would make this page a living document/review of hardware implementing compressive sensing. The first order of business would be to go through each of these links and collect the actual reference of each of these instruments. We could submit this to arxiv in the first place and update it as needed over time. If it's good enough, we can submit it for publication somewhere. Anybody interested ?

CS: MIA, More SpaRSA, Kalman Filter-CS, Compressed sensing and sparse recovery in exploration seismology, Solving Helmholtz

Next week will start with the Mathematics and Image Analysis 2009 (MIA'09) meeting. I may see some of you there. In the meantime, here are a series of paper found on the interwebs, enjoy:

Gradient-based methods for sparse recovery by William Hager, Dzung Phan, Hongchao Zhang. The abstract reads:

The convergence rate is analyzed for the SpaRSA algorithm (Sparse Reconstruction by Separable Approximation) for minimizing a sum $f (\m{x}) + \psi (\m{x})$ where $f$ is smooth and $\psi$ is convex, but possibly nonsmooth. It is shown that if $f$ is convex, then the error in the objective function at iteration $k$, for $k$ sufficiently large, is bounded by $a/(b+k)$ for suitable choices of $a$ and $b$. Moreover, if the objective function is strongly convex, then the convergence is $R$-linear. An improved version of the algorithm based on a cycle version of the BB iteration and an adaptive line search is given. The performance of the algorithm is investigated using applications in the areas of signal processing and image reconstruction.

KF-CS: Compressive Sensing on Kalman Filtered Residual by Namrata Vaswani. The abstract reads:

We consider the problem of recursively reconstructing time sequences of sparse signals (with unknown and time-varying sparsity patterns) from a limited number of linear incoherent measurements with additive noise. The signals are sparse in some transform domain referred to as the sparsity basis and the sparsity pattern is assumed to change slowly with time. The idea of our proposed solution, KF CS-residual (KF-CS) is to replace compressed sensing (CS) on the observation by CS on the Kalman filtered (KF) observation residual computed using the previous estimate of the support. We obtain the conditions under which the KF-CS estimate stabilizes to within a small error of the genie-aided KF (the KF that knows the support at each time), with high probability. Simulations comparing KF-CS to simple CS and least squares CS-residual (LS-CS) are shown.

Angshul Majumdar let me know of this paper: On compressive sensing applied to radar by Joachim H.G. Ender.The abstract reads:

References and further reading may be available for this article. To view references and further reading you must purchase this article.

Compressive sensing (CS) techniques offer a framework for the detection and allocation of sparse signals with a reduced number of samples. Today, modern radar systems operate with high bandwidths - demanding high sample rates according to the Shannon-Nyquist theorem - and a huge number of single elements for phased array antennas. Often only a small amount of target parameters is the final output, arising the question, if CS could not be a good mean to reduce data size, complexity, weight, power consumption and costs of radar systems. There is only a small number of publications addressing the application of CS to radar, leaving several open questions. This paper addresses some aspects as a further step to CS-radar by presenting generic system architectures and implementation considerations. It is not the aim of this paper to investigate numerically efficient algorithms but to point to promising applications as well as arising problems. Three possible applications are considered: pulse compression, radar imaging, and air space surveillance with array antennas. Some simulation results are presented and enriched by the evaluation of real data acquired by an experimental radar system of Fraunhofer FHR.

No investigation of efficient algorithms ? Hey, maybe I should be publishing papers from the "These technologies Do Not Exist" series ? :) Thanks Angshul !

The lectures on Compressed sensing and sparse recovery in exploration seismology are listed below. The abstract for the three lectures reads:

In this course, I will present how recent results from compressed sensing and sparse recovery apply to exploration seismology. During the first lecture, I will present the basic principles of compressive sensing; the importance of random jitter sampling and sparsifying transforms; and large-scale one-norm solvers. I will discuss the application of these techniques to missing trace interpolation. The second lecture will be devoted to coherent signal separation based on curvelet domain matched filtering and Bayesian separation with sparsity promotion. Applications of these techniques to the primary-multiple wavefield-separation problem on real data will be discussed as well. The third lecture will be devoted towards sparse recovery in seismic modeling and imaging and includes the problem of preconditioning the imaging operators, and the recovery from simultaneous source-acquired data.

• Lecture 1
• Lecture 2
• Lecture 3.

Additional presentations on how to solve the Helmholtz equation can be found below:

Unified compressive sensing framework for simultaneous acquisition with primary estimation, by Tim Lin and Felix Herrmann. The abstract reads:

The central promise of simultaneous acquisition is a vastly improved crew efficiency during acquisition at the cost of additional post-processing to obtain conventional source-separated data volumes. Using recent theories from the field of compressive sensing, we present a way to systematically model the effects of simultaneous acquisition. Our formulation form a new framework in the study of acquisition design and naturally leads to an inversion-based approach for the separation of shot records. Furthermore, we show how other inversion-based methods, such as a recently proposed method from van Groenestijn and Verschuur (2009) for primary estimation, can be processed together with the demultiplexing problem to achieve a better result compared to a separate treatment of these problems.

Compressive simultaneous full-waveform simulation by Felix Herrmann, Tim Lin and Yogi A. Erlangga. The abstract:

The fact that the computational complexity of wavefield simulation is proportional to the size of the discretized model and acquisition geometry, and not to the complexity of the simulated wavefield, is a major impediment within seismic imaging. By turning simulation into a compressive sensing problem--where simulated data is recovered from a relatively small number of independent simultaneous sources--we remove this impediment by showing that compressively sampling a simulation is equivalent to compressively sampling the sources, followed by solving a reduced system. As in compressive sensing, this allows for a reduction in sampling rate and hence in simulation costs. We demonstrate this principle for the time-harmonic Helmholtz solver. The solution is computed by inverting the reduced system, followed by a recovery of the full wavefield with a sparsity promoting program. Depending on the wavefield's sparsity, this approach can lead to a significant cost reduction, in particular when combined with the implicit preconditioned Helmholtz solver, which is known to converge even for decreasing mesh sizes and increasing angular frequencies. These properties make our scheme a viable alternative to explicit time-domain finite-difference.

Compressive imaging by wavefield inversion with group sparsity by Felix Herrmann. The abstract:

Migration relies on multi-dimensional correlations between source- and residual wavefields. These multi-dimensional correlations are computationally expensive because they involve operations with explicit and full matrices that contain both wavefields. By leveraging recent insights from compressive sampling, we present an alternative method where linear correlation-based imaging is replaced by imaging via multidimensional deconvolutions of compressibly sampled wavefields. Even though this approach goes at the expense of having to solve a sparsity-promotion recovery program for the image, our wavefield inversion approach has the advantage of reducing the system size in accordance to transform-domain sparsity of the image. Because seismic images also exhibit a focusing of the energy towards zero offset, the compressive-wavefield inversion itself is carried out using a recent extension of one-norm solver technology towards matrix-valued problems. These so-called hybrid $(1,\,2)$-norm solvers allow us to penalize pre-stack energy away from zero offset while exploiting joint sparsity amongst near-offset images. Contrary to earlier work to reduce modeling and imaging costs through random phase-encoded sources, our method compressively samples wavefields in model space. This approach has several advantages amongst which improved system-size reduction, and more flexibility during subsequent inversions for subsurface properties.

Sub-Nyquist sampling and sparsity: getting more information from fewer samples by Felix Herrmann. The abstract reads:

Seismic exploration relies on the collection of massive data volumes that are subsequently mined for information during seismic processing. While this approach has been extremely successful in the past, the current trend of incessantly pushing for higher quality images in increasingly complicated regions of the Earth continues to reveal fundamental shortcomings in our workflows to handle massive high-dimensional data volumes. Two causes can be identified as the main culprits responsible for this barrier. First, there is the so-called ``curse of dimensionality'' exemplified by Nyquist's sampling criterion, which puts disproportionate strain on current acquisition and processing systems as the size and desired resolution of our survey areas continues to increase. Secondly, there is the recent ``departure from Moore's law'' that forces us to lower our expectations to compute ourselves out of this curse of dimensionality. In this paper, we offer a way out of this situation by a deliberate \emph{randomized} subsampling combined with structure-exploiting transform-domain sparsity promotion. Our approach is successful because it reduces the size of seismic data volumes without loss of information. Because of this size reduction both impediments are removed and we end up with a new technology where the costs of acquisition and processing are no longer dictated by the \emph{size of the acquisition} but by the transform-domain \emph{sparsity} of the end-product after processing.

Credit: NASA, Atlantis during STS-129.

CS: Quantum Compressed Sensing

I just found the following online presentation entitled: Learning Much from Little: Compressed Sensing Approach to Quantum State Tomography and Other Ideas of Systems Identification presented by Jens Eisert. I'll shortly add it to the online video Compressive Sensing page.

Still on the subject of Quantum issues the paper mentioned yesterday that uses a quantum chip (or equivalent) to perform an l_0 regularization is:

NIPS 2009 Demonstration: Binary Classification using Hardware Implementation of Quantum Annealing by Hartmut Neven, Vasil S. Denchev, Marshall Drew-Brook, Jiayong Zhang, William G. Macready, Geordie Rose. The abstract reads:

Previous work [NDRM08, NDRM09] has sought the development of binary classifiers that exploit the ability to better solve certain discrete optimization problems with quantum annealing. The resultant training algorithm was shown to offer benefits over competing binary classifiers even when the discrete optimization problems were solved with software heuristics. In this progress update we provide first results on training using a physical implementation of quantum annealing for black-box optimization of Ising objectives. We successfully build a classifier for the detection of cars in digital images using quantum annealing in hardware. We describe the learning algorithm and motivate the particular regularization we employ. We provide results on the efficacy of hardware-realized quantum annealing, and compare the final classifier to software trained variants, and a highly tuned version of AdaBoost.

Hartmut Neven, one of the author, made a presentation on this subject at NIPS'08 entitled: Training a Binary Classifier with the Quantum Adiabatic Algorithm. The D-Wave folks who are making this quantum chip have a blog. The company website is here.

As I said yesterday, if this chip sees the light of the day and performs this l_0 regularization, then I believe compressive sensing studies could focus uniquely on the acquisition/sampling stage and go beyond the issue of sparsity.

Laneo

As a marathon runner, Andrew Paterson, a friend, has been pretty disgusted by how rapidly nature turns into landfill. As a result he has set up a company that provides money for cleanup projects. One of the ways he can be convincing when looking for sponsors (that enable these cleanup projects) is by raising the number of fans his company, Laneo, has on Facebook or its his Twitter feed. For every 5000 fans he can get 5 wilderness cleanup projects in 2010. I'll let him explain this better in the following video:

The Laneo Challenge: Part 1 from Andrew Paterson on Vimeo.

If you are interested, you can become a fan of Laneo, has on Facebook or follow the Laneo Twitter feed.

CS: Eureqa: a solution, PSF determination, L_0 quantum chip?, Greedy dictionary, CS for MRI, CS MIMO radar , low rank matrix.

Andrew Gelman has finally found a solution but he had to provide some help to Eureqa.

If you recall, one of the big issue of compressive sensing imaging system is the need to go through a lengthy calibration process to find the system's PSF. This is not just a problem in Compressive Sensing as witnessed in this latest paper entitled: Accurate photometry with adaptive optics in the presence of anisoplanatic effects with a sparsely sampled PSF by Rainer Schodel.

Olivier Grisel mentioned an Efficient L0-norm regularization with Adiabatic Quantum Computing by some of the folks at Google. From their entry:

The theory paper on which the demonstration is based can be found on the arXiv and a report describing the details of the implementation is here.

I'd have to look at it deeper. If the chip can actually perform l_0 search, then Compressive Sensing becomes even more relevant as we could now focus on how to acquire data incoherently without having to care too much about the reconstruction solvers.


Volkan Cevher let me know about his recent paper entitled: Greedy Dictionary Selection for Sparse Representation by himself and Andreas Krause. The abstract reads:

We discuss how to construct a dictionary by selecting its columns from multiple candidate bases to allow sparse representation of signals. By sparse representation, we mean that only a few dictionary elements, compared to the ambient signal dimension, can be used to well-approximate the signals. We formulate both the selection of the dictionary columns and the sparse representation of signals as a joint combinatorial optimization problem. The proposed combinatorial objective maximizes variance reduction over the set of signals by constraining the size of the dictionary as well as the number of dictionary columns that can be used to represent each signal. We show that if the columns of the candidate bases are incoherent, our objective function satisfies approximate submodularity. We exploit this property to develop efficient greedy algorithms with well-characterized theoretical performance. Applications of dictionary selection include denoising, inpainting, and compressive sensing. We evaluate our approach to reconstruct dictionaries from sparse samples, and also apply it to an image inpainting problem.

I found the following on the interwebs and arxiv, enjoy:

Spread spectrum for compressed sensing techniques in magnetic resonance imaging by Yves Wiaux, Gilles Puy, R. Gruetter, J-P. Thiran , D. Van De Ville, and Pierre Vandergheynst.

We advocate the use of a chirp modulation for magnetic resonance imaging (MRI) in the perspective of defining the best possible imaging techniques for sparse or compressible signals in the context of the recent theory of compressed sensing. We analyze the related spread spectrum phenomenon and we prove its effectiveness in enhancing the overall quality of image reconstruction. We also study its impact at each scale of decomposition in a wavelet sparsity basis. Our preliminary results rely both on theoretical considerations related to the mutual coherence between the sparsity and sensing bases, as well as on numerical simulations from synthetic signals.

Reduced Complexity Angle-Doppler-Range Estimation for MIMO Radar That Employs Compressive Sensing by Yao Yu, Athina Petropulu, H. Vincent Poor, H. Vincent Poor. The abstract reads:

The authors recently proposed a MIMO radar system that is implemented by a small wireless network. By applying compressive sensing (CS) at the receive nodes, the MIMO radar super-resolution can be achieved with far fewer observations than conventional approaches. This previous work considered the estimation of direction of arrival and Doppler. Since the targets are sparse in the angle-velocity space, target information can be extracted by solving an l1 minimization problem. In this paper, the range information is exploited by introducing step frequency to MIMO radar with CS. The proposed approach is able to achieve high range resolution and also improve the ambiguous velocity. However, joint angle-Doppler-range estimation requires discretization of the angle-Doppler-range space which causes a sharp rise in the computational burden of the l1 minimization problem. To maintain an acceptable complexity, a technique is proposed to successively estimate angle, Doppler and range in a decoupled fashion. The proposed approach can significantly reduce the complexity without sacrificing performance.

Sparse and Low-Rank Matrix Decomposition Via Alternating Direction Methods by Xiaoming Yuan, Junfeng Yang. The abstract reads:

The problem of recovering the sparse and low-rank components of a matrix captures a broad spectrum of applications. Authors in [4] proposed the concept of "rank-sparsity incoherence" to characterize the fundamental identifiability of the recovery, and derived practical sufficient conditions to ensure the high possibility of recovery. This exact recovery is achieved via solving a convex relaxation problem where the L1 norm and the nuclear norm are utilized for being surrogates of the sparsity and low-rank. Numerically, this convex relaxation problem was reformulated into a semi-definite programming (SDP) problem whose dimension is considerably enlarged, and this SDP reformulation was proposed to be solved by generic interior-point solvers in [4]. This paper focuses on the algorithmic improvement for the sparse and low-rank recovery. In particular, we observe that the convex relaxation problem generated by the approach of [4] is actually well-structured in both the objective function and constraint, and it fits perfectly the applicable range of the classical alternating direction method (ADM). Hence, we propose the ADM approach for accomplishing the sparse and low-rank recovery, by taking full exploitation to the high-level separable structure of the convex relaxation problem. Preliminary numerical results are reported to verify the attractive efficiency of the ADM approach for recovering sparse and low-rank components of matrices.

Finally, Stephane Mallat is giving a course entitled: A Sparse Wavelet Tour of Signal Processing. The slides are as follows:

• 1. Sparse Representations in Signal and Image Processing.
• 2. Redundant Dictionaries and Pursuit Algorithms.
• 3. Super-Resolution for Inverse Problems with Sparsity.
• 4. Compressed Sensing.
• 5. Dictionary Learning and Source Separation.

Of note, one can also read Super-resolution Bandlet Upconversion for HDTV.

CS: YALL1, fitness function Eureqa, Data Driven CS, Matlab, Python, NIPS 2009 papers, Bayesian statistics in AI and Social Sciences

Junfeng Yang, now at Nanjing University, let me know of the newly released paper on the algorithm underlying the YALL1 package, it is: Alternating Direction Algorithms for L_1 Problems in Compressive Sensing by Junfeng Yang and Yin Zhang. The abstract reads:

In this paper, we propose and study the use of alternating direction algorithms for several L_1-norm minimization problems arising from sparse solution recovery in compressive sensing, including the basis pursuit problem, the basis-pursuit denoising problems of both unconstrained and constrained forms, as well as others. We present and investigate two classes of algorithms derived from either the primal or the dual forms of the L_1-problems. The construction of the algorithms consists of two main steps: (1) to reformulate an L_1-problem into one having partially separable objective functions by adding new variables and constraints; and (2) to apply an exact or inexact alternating direction method to the resulting problem. The derived alternating direction algorithms can be regarded as rst-order primal-dual algorithms because both primal and dual variables are updated at each and every iteration. Convergence properties of these algorithms are established or restated when they already exist. Extensive numerical results in comparison with several state-of-the-art algorithms are given to demonstrate that the proposed algorithms are efficient, stable and robust. Moreover, we present numerical results to emphasize two practically important but perhaps overlooked points. One point is that algorithm speed should always be evaluated relative to appropriate solution accuracy; another is that whenever erroneous measurements possibly exist, the L_1-norm fidelity should be the fidelity of choice in compressive sensing.

YALL1 is available in Matlab. As most of you may already know, MATLAB 2009b has a potential serious bug. You can find a description here, but since this a serious problem relating to the use of the transpose sign which is very much used in compressive sensing solvers, let me copy the message here:

There seems to be a serious bug in the current Matlab release R2009b that
occurs when solving a linear system of equations with the transpose. Here
is a small example:

A=[ 0 2 ; 1 0 ];
b=[ 2 ; 0 ];
A'\b

ans =

0
1

whereas the correct solution is [ 0 ; 2 ]. The answer [ 0 ; 1 ] is the
solution of A\b, so it appears that the transpose sign ' is ignored.
However, the correct solution is returned when using

transpose(A)\b, A.'\b

instead of A'\b.

Interestingly, this bug does not occur for all matrices, for instance

A = [1 2 ; 1 1]
A'\b

returns the correct result [ -2 ; 4 ].

The bug seems to be new in release R2009b and applies to Linux and Windows
32 and 64 bit versions. A bug report has been filed.

The Mathworks folks responded here:

Following up to the message in the Nov 30, 2009 NA Digest:

Thanks to all the MATLAB Community members who have reported this bug
and forwarded this information along.

We have posted this Bug (583443) in our Bug Report system:

http://www.mathworks.com/support/bugreports/

Look under MATLAB, in the Mathematics Category, Exists In R2009b.

MATLAB customers should feel free to Watch this Bug for any updates,
or Subscribe to an RSS feed of a group of Bugs of interest.

This Bug Report details the circumstances required to trigger the bug.

The summary is that A must be the permutation of a full, square, non-scalar
triangular matrix (but not exactly triangular) and must be used as A’\b in
the solve.

The Bug Report does not yet reflect this, but the bug will be fixed in our
next release of MATLAB.

But in order to see their bug report, you have to create an account with them. I am not quite sure this sends the right message. I am not an open source fanatic but this little story is a short reminder that little attempts at implementing algorithms in a free language has some potential to survive the test of time. Which brings us to Ben Moran who implemented the solving of a Sudoku puzzle with an L1 minimization approach in Python (as mentioned here) . Ben, pretty please, after that python meeting, please release that code :-)

Georgos Tzagkarakis kindly let me know that, in a previous entry, I confused him with his brother Christos Tzagkarakis who also happen to publish in compressive sensing. This is fixed. As it turns out Georgos has submitted the following to ICASSP '10:

Bayesian Compressed Sensing Imaging using a Gaussian Scale Mixture by Georgos Tzagkarakis and Panagiotis Tsakalides. The abstract reads:

The ease of image storage and transmission in modern applications would be unfeasible without compression, which converts high-resolution images into a relatively small set of significant transform coefficients. Due to the specific content of many real-world images they are highly sparse in an appropriate orthonormal basis. The inherent property of compressed sensing (CS) theory working simultaneously as a sensing and compression protocol, using a small subset of random incoherent projection coefficients, enables a potentially significant reduction in the sampling and computation costs of images favoring its use in real-time applications which do not require an excellent reconstruction performance. In this paper, we develop a Bayesian CS (BCS) approach for obtaining highly sparse representations of images based on a set of noisy CS measurements, where the prior belief that the vector of projection coefficients should be sparse is enforced by fitting directly its prior probability distribution by means of a Gaussian Scale Mixture (GSM). The experimental results show that our proposed method, when compared with norm-based constrained optimization algorithms, maintains the reconstruction performance, in terms of the reconstruction error and the PSNR, while achieving an increased sparsity using much less basis functions.

Thanks Georgos !

In the Sparsity in Everything series, a series of post that highlights sparsity and power laws in odd places for the purpose of shamelessly linking them back to compressive sensing, I mentioned the work of Michael Schmidt and Hod Lipson entitled Distilling Free-Form Natural Laws from Experimental Data that seemed to amount to a solving some sort of l_0 problem ( i.e. fitting the data/phenomena at hand with a combinatorial search using genetic algorithms.) Well they just came out with a GUI that allows anyone to try that experiment for themselves. It's called Eureqa. In Equation search part 1, Andrew Gelman just wrote in a string a data he sent and he's waiting for an answer. He might be waiting for a long time.... In the meantime, I am surprised to see that there is no response to the criticism made on the fitness function of the original article and now thisprogram. The criticism was brought forth here:

On the Article "Distilling Free-Form Natural Laws From Experimental Data" by Christopher Hillar and Friedrich Sommer. The paper starts as:

A recent paper [1] introduced the fascinating idea that natural symbolic laws (such as
Lagrangians and Hamiltonians) could be learned from experimental measurements in a physical system (such as a pendulum). The learning is based on a genetic algorithm that employs a fitness function involving the pair-wise partial derivatives of the time-series measurements of state-space data coming from the system. While the general approach is original and convincing, we feel that the particular algorithm described in the paper cannot accomplish these goals. We present theoretical and experimental arguments for this belief and also explain some mathematically rigorous ideas that can be used within the authors’ framework to find symbolic laws.
We first recapitulate the main steps in the methodology

And while you are waiting for Eureqa to converge (to the wrong solution ?), you might as well do two things:

1. Enjoy reading papers from NIPS 2009. They're out. Andrew Mcgregor points to some streaming papers. While reading some of them and being off-line, I was wondering aloud if, in some exploratory instance, we should not go about the following process to do compressive sensing:

• Find out the Power Laws at play in your data.
• Taylor an iterative re-weighted sparse signal recovery algorithms that outperform the standard l_1-norm minimization.
• Choose the right encoding scheme that fits a specific physical sensor system

and you now have a compressive sensing scheme tailored to your area of interest.

2. Enjoy this discussion between two bayesian people: an AI person and a social science person namely Eliezer Yudkowsky and Andrew Gelman respectively

Finally, don't expect Eureqa to help in your formula for happiness, it's just a fit whereas the cure seems to be to just watch faces in the morning.

Credit photo: Sam Derbyshire, roots of polynomials as shown in John Baez's "The beauty of roots" http://math.ucr.edu/home/baez/roots/. Poster from NIPS 2009, Multilabel Prediction via Compressed Sensing.

CS:This week's long post.

My webcrawler grabbed several articles this week-end and make up this large post. First, the Lecture Notes: Compressive sensing and structured random matrices are still under construction. If you have comments of any sort, Holger Rauhut would be happy to receive them.

While not expressly related to compressive sensing, I noted the following: Real-time convex optimization in signal processing by Jacob Mattingley and Stephen Boyd. The abstract reads:

Convex optimization has been used in signal processing for a long time, to choose coefficients for use in fast (linear) algorithms, such as in filter or array design; more recently, it has been used to carry out (nonlinear) processing on the signal itself. Examples of the latter case include total variation de-noising, compressed sensing, fault detection, and image classification. In both scenarios, the optimization is carried out on time scales of seconds or minutes, and without strict time constraints. Convex optimization has traditionally been considered computationally expensive, so its use has been limited to applications where plenty of time is available. Such restrictions are no longer justified. The combination of dramatically increased computational power, modern algorithms, and new coding approaches has delivered an enormous speed increase, which makes it possible to solve modest-sized convex optimization problems on microsecond or millisecond time scales, and with strict deadlines. This enables real-time convex optimization in signal processing.

specifically from the paper, the authors write:

....As a result, convex optimization problems that 20 years ago might have taken minutes to solve can now be solved in microseconds. This opens up several new possibilities. In the design context, algorithm weights can be re-designed or updated on fast time scales (say, kHz). Perhaps more exciting is the possibility that convex optimization can be emdedded directly in signal processing algorithms that run on-line, with strict real-time deadlines, even at rates of tens of kHz. We will see that solving 10 000 modest sized convex optimization problems per second is entirely possible on a generic processor. This is quite remarkable, since solving an optimization problem is generally considered a computationally challenging task, and few engineers would consider an on-line algorithm, that requires the solution of an optimization problem at each step, to be feasible for signal rates measured in kHz....

Still not exactly compressive sensing: A Fast and Efficient Heuristic Nuclear Norm Algorithm for Rank Minimization by Thong T. Do, Yi Chen, Nam Nguyen, Lu Gan and Trac D. Tran. The abstract reads:

The problem of affine rank minimization seeks to find the minimum rank matrix that satisfies a set of linear equality constraints. Generally, since affine rank minimization is NP-hard, a popular heuristic method is to minimize the nuclear norm that is a sum of singular values of the matrix variable [1]. A recent intriguing paper [2] shows that if the linear transform that defines the set of equality constraints is nearly isometrically distributed and the number of constraints is at least O(r(m + n) logmn), where r and m £ n are the rank and size of the minimum rank matrix, minimizing the nuclear norm yields exactly the minimum rank matrix solution. Unfortunately, it takes a large amount of computational complexity and memory buffering to solve the nuclear norm minimization problem with known nearly isometric transforms. This paper presents a fast and efficient algorithm for nuclear norm minimization that employs structurally random matrices [3] for its linear transform and a projected subgradient method that exploits the unique features of structurally random matrices to substantially speed up the optimization process. Theoretically, we show that nuclear norm minimization using structurally random linear constraints guarantees the minimum rank matrix solution if the number of linear constraints is at least O(r(m+n) log3 mn). Extensive simulations verify that structurally random transforms still retain optimal performance while their implementation complexity is just a fraction of that of completely random transforms, making them promising candidates for large scale applications.

Ok, now we can dive into the subject: Fast and Efficient Dimensionality Reduction using Structurally Random Matrices by Thong T. Do, Lu Gan, Yi Chen, Nam Nguyen and Trac D. Tran. The abstract reads:

Structurally Random Matrices (SRM) were first proposed in [1] as fast and highly efficient measurement operators for large scale compressed sensing applications. Motivated by the bridge between compressed sensing and the Johnson-Lindenstrauss lemma [2] , this paper introduces a related application of SRM regarding to realizing a fast and highly efficient embedding. In particular, it shows that a SRM is also a promising dimensionality reduction transform that preserves all pairwise distances of high dimensional vectors within an arbitrarily small factor ², provided the projection dimension is on the order of O(²¡2 log3 N), where N denotes the number of d-dimensional vectors. In other words, the SRM can be viewed as the suboptimal Johnson-Lindenstrauss embedding that, however, owns very low computational complexity O(d log d) and highly efficient implementation that uses only O(d) random bits, making it a promising candidate for practical, large scale applications where efficiency and speed of computation is highly critical.

Compressed Sensing and Routing in Multi-Hop Networks by Sungwon Lee, Sundeep Pattem, Maheswaran Sathiamoorthy, Bhaskar Krishnamachari, and Antonio Ortega. The abstract reads:

We study how compressed sensing can be combined with routing design for energy efficient data gathering in sensor networks. We first obtain some bounds on the performance of compressed sensing with simple routing schemes. We then formulate a new problem relating routing paths to data projections, and present a centralized, greedy algorithm for obtaining low coherence projections while simultaneously reducing reconstruction error and communication cost. Simulation results show that the effectiveness of standard compressed sensing techniques is limited when routing costs are considered. A naive, randomized downsampling is shown to outperform the standard techniques in terms of achievable SNR for a given energy budget. While our algorithm has better performance than standard compression sensing, it does not improve significantly over downsampling in terms of the cost. Thus we believe that further investigation is needed to determine if novel routing strategies exist that i) provide a sufficient spatial coverage to enable good coherence properties for compressed sensing along those routes, and ii) have transport costs that do not deviate significantly from those of efficient routing techniques.

Inflating Compressed Samples: A Joint-Channel Coding Approach for Noise-Resistant Compressed Sensing by A. Hesam Mohseni, Massoud Babaie-Zadeh and Christian Jutten. The abstract reads:

Recently, a lot of research has been done on compressed sensing, capturing compressible signals using random linear projections to a space of radically lower dimension than the ambient dimension of the signal. The main impetus of this is that the radically dimension lowering linear projection step can be done totally in analog hardware, in some cases even in constant time, to avoid the bottleneck in sensing and quantization steps where a large number of samples need to be sensed and quantized in short order, mandating the use of a large number of fast expensive sensors and A/D converters. Reconstruction algorithms from these projections have been found that come within distortion levels comparable to the state of the art in lossy compression algorithms. This paper considers a variation on compressed sensing that makes it resistant to spiky noise. This is achieved by an analog real-field error-correction coding step. It results in a small asymptotic overhead in the number of samples, but makes exact reconstruction under spiky measurement noise, one type of which is the salt and pepper noise in imaging devices, possible. Simulations are performed that corroborate our claim and infact substantially improve reconstruction under unreliable sensing characteristics and are stable even under small perturbations with Gaussian noise.

Efficiently Decodable Non-adaptive Group Testing by Piotr Indyk, Hung Q. Ngo, 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.

Sparse Estimation Using General Likelihoods and Non-Factorial Priors by David Wipf and Srikantan Nagarajan. The abstract reads:

Finding maximally sparse representations from overcomplete feature dictionaries frequently involves minimizing a cost function composed of a likelihood (or data fit) term and a prior (or penalty function) that favors sparsity. While typically the prior is factorial, here we examine non-factorial alternatives that have a number of desirable properties relevant to sparse estimation and are easily implemented using an efficient and globally-convergent, reweighted `1-norm minimization procedure. The first method under consideration arises from the sparse Bayesian learning (SBL) framework. Although based on a highly non-convex underlying cost function, in the context of canonical sparse estimation problems, we prove uniform superiority of this method over the Lasso in that, (i) it can never do worse, and (ii) for any dictionary and sparsity profile, there will always exist cases where it does better. These results challenge the prevailing reliance on strictly convex penalty functions for finding sparse solutions. We then derive a new non-factorial variant with similar properties that exhibits further performance improvements in some empirical tests. For both of these methods, as well as traditional factorial analogs, we demonstrate the effectiveness of reweighted `1-norm algorithms in handling more general sparse estimation problems involving classification, group feature selection, and non-negativity constraints. As a byproduct of this development, a rigorous reformulation of sparse Bayesian classification (e.g., the relevance vector machine) is derived that, unlike the original, involves no approximation steps and descends a well-defined objective function.

Compressive Distilled Sensing: Sparse Recovery Using Adaptivity in Compressive Measurements by Jarvis Haupt, Richard Baraniuk, Rui Castro and Rovert Nowak. The abstract reads:

The recently-proposed theory of distilled sensing establishes that adaptivity in sampling can dramatically improve the performance of sparse recovery in noisy settings. In particular, it is now known that adaptive point sampling enables the detection and/or support recovery of sparse signals that are otherwise too weak to be recovered using any method based on non-adaptive point sampling. In this paper the theory of distilled sensing is extended to highly-undersampled regimes, as in compressive sensing. A simple adaptive sampling-and-refinement procedure called compressive distilled sensing is proposed, where each step of the procedure utilizes information from previous observations to focus subsequent measurements into the proper signal subspace, resulting in a significant improvement in effective measurement SNR on the signal subspace. As a result, for the same budget of sensing resources, compressive distilled sensing can result in significantly improved error bounds compared to those for traditional compressive sensing.

A Note on Optimal Support Recovery in Compressed Sensing by Galen Reeves and Michael Gastpar. The abstract reads:

Recovery of the support set (or sparsity pattern) of a sparse vector from a small number of noisy linear projections (or samples) is a “compressed sensing” problem that arises in signal processing and statistics. Although many computationally efficient recovery algorithms have been studied, the optimality (or gap from optimality) of these algorithms is, in general, not well understood. In this note, approximate support recovery under a Gaussian prior is considered, and it is shown that optimal estimation depends on the recovery metric in general. By contrast, it is shown that in the SNR limits, there exist uniformly near-optimal estimators, namely, the ML estimate in the high SNR case, and a computationally trivial thresholding algorithm in the low SNR case.

Sublinear-Time Fourier Algorithms with Recovery Guarantees and Uniformly Bounded Sampling Requirements by Mark Iwen. The abstract reads:

We study the problem of quickly estimating the best k term Fourier representation for a given frequency-sparse signal (i.e., vector or array) A of length N  k. In essence, we investigate how to identify k of the largest magnitude frequencies of ˆ A, and estimate their coefficients, in k2 · polylog(kˆ Ak1,N) time. Randomized sublinear-time Monte Carlo algorithms, which have a small probability of failing to output accurate answers for each input signal, exist for solving this problem [15, 16, 18]. In this paper we develop the first known Las Vegas sparse Fourier Transform methods which are guaranteed to produce accurate results, and run in sublinear-time on each input signal A 2 CN with high probability. The Las Vegas results developed herein improve on recent deterministic Fourier methods [19, 18, 1] by guaranteeing accurate answers while having both (i) substantially smaller (i.e., near-optimal) guaranteed sampling requirements, and (ii) better runtime complexity on each input signal with high probability.

Group Sparse Coding by Samy Bengio, Fernando Pereira, Yoram Singer, Dennis Strelow. The abstract reads:

Bag-of-words document representations are often used in text, image and video processing. While it is relatively easy to determine a suitable word dictionary for text documents, there is no simple mapping from raw images or videos to dictionary terms. The classical approach builds a dictionary using vector quantization over a large set of useful visual descriptors extracted from a training set, and uses a nearest-neighbor algorithm to count the number of occurrences of each dictionary word in documents to be encoded. More robust approaches have been proposed recently that represent each visual descriptor as a sparse weighted combination of dictionary words. While favoring a sparse representation at the level of visual descriptors, those methods however do not ensure that images have sparse representation. In this work, we use mixed-norm regularization to achieve sparsity at the image level as well as a small overall dictionary. This approach can also be used to encourage using the same dictionary words for all the images in a class, providing a discriminative signal in the construction of image representations. Experimental results on a benchmark image classification dataset show that when compact image or dictionary representations are needed for computational efficiency, the proposed approach yields better mean average precision in classification.

and finally a poster:Ear-Phone-Assessment of Noise Pollution with Mobile Phones by Rajib Kumar Rana, Chun Tung Chou, Salil Kanhere, Nirupama Bulusu, Wen Hu. The abstract reads:

Noisemap can provide useful information to control noise pollution. We propose a people-centric noise collection system called the Ear-Phone. Due to the voluntary participation of people, the number and location of samples cannot be guaranteed. We propose and study two methods, based on compressive sensing, to reconstruct the missing samples.

Image Credit: NASA/JPL/Space Science Institute, W00061912.jpg was taken on December 04, 2009 and received on Earth December 05, 2009. The camera was pointing toward SATURN at approximately 2,157,548 kilometers away, and the image was taken using the CB2 and CL2 filters.

CS: Sparsity, Randomness and Compressed Sensing, Spatio‐Temporal Compressive Sensing

I just highjacked the last picture in Petros Boufounos' presentation entitled Sparsity, Randomness and Compressed Sensing. Thanks Petros for mentioning Nuit Blanche!

and here is another presentation entitled: Spatio‐Temporal Compressive Sensing by Yin Zhang, Matthew Roughan, Walter Willinger, Lili Qiu and presented by Wei Dong and Chen Qian.

CS: Exact Optimization for the l1-Compressive Sensing problem using a Modified Dantzig-Wolfe method and two presentations

I just added a sentence by Howard Aiken at the end of the These Technologies Do Not Exist page, it's: “Don’t worry about people stealing your ideas. If it’s original, you’ll have to ram it down their throats.”.... and then when you have done that, you may have to fight the FCC (UWB radar for wall see through) and/or the lawyers (isn't the title of this patent summarizing what reconstruction solvers do in compressive sensing ?). Anyway, to conclude these eventful two weeks, I just found one paper and two presentations:

Exact Optimization for the l1-Compressive Sensing problem using a Modified Dantzig-Wolfe method by Alexandre Borghi, Jerome Darbon, Sylvain Peyronnet. The abstract reads:

This paper considers the l1-Compressive Sensing problem and presents an efficient algorithm that computes an exact solution. The idea consists in reformulating the problem such that it yields a modified Dantzig-Wolfe decomposition that allows to efficiently apply all standard simplex pivoting rules. Experimental results show the superiority of our approach compared to standard linear programming methods.

I am looking forward to an implementation of this algorithm. And the presentations:

• In-Jae Kim, Compressed Sensing and Matrix Problems
• Roummel Marcia, Compressive Sensing Matrices and Coded Aperture Imaging

Today is also the PhD Final Oral Defense of Nishant Mohan at Boston University. From the University Calendar:

Summary

BME PhD Final Oral Defense of Nishant Mohan
Description

"Photon-Counting Optical Coherence-Domain Imaging" ABSTRACT: Coherence-domain imaging (CDI) systems can be operated in a single-photon counting mode, offering low detector noise; this in turn leads to increased sensitivity for weak light sources and weakly reflecting samples. In this thesis, I demonstrate that excellent axial resolution can be obtained in a photon-counting coherence-domain imaging (PC-CDI) system that uses light generated via spontaneous parametric down-conversion (SPDC) in a chirped periodically poled stoichiometric lithium tantalate (chirped-PPSLT) structure, in conjunction with a niobium nitride superconducting single-photon detector (SSPD). The bandwidth of the light generated via SPDC, as well as the bandwidth over which the SSPD is sensitive, can extend over a wavelength region that stretches from 700 to 1500 nm. This ultra-broad wavelength band offers a near-ideal combination of deep penetration and ultra-high axial resolution for the imaging of biological tissue. The generation of SPDC light of adjustable bandwidth in the vicinity of 1064 nm, via the use of chirped-PPSLT structures, is novel. To demonstrate the usefulness of PC-CDI, I have constructed images for a hierarchy of samples of increasing complexity: a mirror, a nitrocellulose membrane, and a biological sample comprising onion-skin cells. The potential usefulness of this technique in a standard configuration is limited, however, by the presence of 1/f-type noise in the source of illumination. I have therefore investigated this noise for various sources of light that are useful in optical imaging. Finally, I consider another CDI configuration, spectral-domain imaging, and show that the notion of compressed sensing can be useful for simplifying the experimental configuration.
Starts

10:00am on Friday, December 4th 2009
Location

Photonics Center, 8 St. Mary's Street (PHO 404)
Topics

Seminars and Lectures, Biomedical Engineering

Credit photo: NAS, STS-129 ascent as viewed by a camera on-board one of the solid rocket boosters.

CS: Commercial CT scanners, Nonstationary Spectral Estimation, Approximate Sparse Recovery, THz Reflectance Tomography

If you recall, I was looking for a tablet-like device so I could read most of the pdfs mentioned here off-line. See, I dread having to sit in front of a computer to read something when I could be out on the beach reading the same paper while drinking a margarita. After having gone for a netbook, I was still not too happy with the ergonomics of it as the keyboard meant using the netbook in the same way I would use a laptop. Furthermore, the sand would get stuck in the keyboard rather fast, so using it at the beach was out of the question. Not being an Apple fanboi, I reluctantly went for an iPod Touch and besides a 1604 error on the very first day, I have not looked back. It looks like I am not the only one enjoying the two columns articles anymore. Being off-line is good, I can connect only when there is free wifi ( a now rare occurence), and I don't need to pay any monies on a monthly basis such as would be the case for an iPhone. I certainly don't have to care about outrageous international roaming fees as a result. For what it's worth, I use Instapaper to read web articles off-line and use a pdf viewer app in order to read the papers I download from the blog. Why do I say this ? No, I am not subsidized by Apple but rather I say this because it has changed some of my habits. I now spend some more time reading a paper after it has been mentioned on the blog. This may explain why I sometimes provide some comments on an article after it's been cited here rather than at the time it came out. I value a timely release of a paper on the blog rather having it be on my reading queue which, after two days, is a euphemism for never-gonna-read-it list. For instance, I am bound to write more about Low-Dimensional Models for Dimensionality Reduction and Signal Recovery: A Geometric Perspective by Richard Baraniuk, Volkan Cevher, Michael Wakin.

On a different subject, I am stunned! I looked at the recent stats of These Technologies Do Not Exist page I set up last week and found the following distribution:

I really was not expecting that many countries represented in the first week (25). This is truly a good representation of the long tail argument for ArXiv or blogs focused on specialized technical content. Could technical journals truly reach out to individuals who are interested on a specific subject area on such global scale so rapidily ? I doubt it.

On a different note, some entries like These Technologies Do Not Exist or Imaging With Nature posts are a direct result of my being off-line ( and one wonders if this a good thing!). What is true, though, is that while compressive sensing investigations could be in the 10% improvement business, others also seem to think it is blue-sky development worth investing in. For this movement to be more transformational we need, for instance, to have more review articles like the following one (see below). I had a discussion with Emil Sidky one of the author and will write about it later but in the meantime, the review is available for free for the next 30 days: Why do commercial CT scanners still employ traditional, filtered back-projection for image reconstruction? by Xiaochuan Pan, Emil Sidky and Michael Vannier. The abstract reads:

Despite major advances in x-ray sources, detector arrays, gantry mechanical design and especially computer performance, one component of computed tomography (CT) scanners has remained virtually constant for the past 25 years—the reconstruction algorithm. Fundamental advances have been made in the solution of inverse problems, especially tomographic reconstruction, but these works have not been translated into clinical and related practice. The reasons are not obvious and seldom discussed. This review seeks to examine the reasons for this discrepancy and provides recommendations on how it can be resolved. We take the example of field of compressive sensing (CS), summarizing this new area of research from the eyes of practical medical physicists and explaining the disconnection between theoretical and application-oriented research. Using a few issues specific to CT, which engineers have addressed in very specific ways, we try to distill the mathematical problem underlying each of these issues with the hope of demonstrating that there are interesting mathematical problems of general importance that can result from in depth analysis of specific issues. We then sketch some unconventional CT-imaging designs that have the potential to impact on CT applications, if the link between applied mathematicians and engineers/physicists were stronger. Finally, we close with some observations on how the link could be strengthened. There is, we believe, an important opportunity to rapidly improve the performance of CT and related tomographic imaging techniques by addressing these issues.

This is good piece when one wants to think about how compressive sensing has the ability to be a real disruptive technology.

In a different direction, I just found the following on the interwebs and on arxiv:

Compressive Nonstationary Spectral Estimation Using ParsimoniousRandom Sampling of the Ambiguity Function by Alexander Jung, Georg Taubock, and Franz Hlawatsch. The abstract reads:

We propose a compressive estimator for the discrete Rihaczek spectrum (RS) of a time-frequency sparse, underspread, nonstationary random process. The new estimator uses a compressed sensing technique to achieve a reduction of the number of measurements. The measurements are randomly located samples of the ambiguity function of the observed signal. We provide a bound on the mean-square estimation error and demonstrate the performance of the estimator by means of simulation results. The proposed RS estimator can also be used for estimating the Wigner-Ville spectrum (WVS) since for an underspread process the RS and WVS are almost equal.

Compressed Sensing Pulse-Echo Mode THz Reflectance Tomography by Kyung Hwan Jin, Youngchan Kim, Dae-Su Yee, Ok Kyun Lee and Jong Chul Ye. The abstract reads:

We demonstrate a pulse-echo mode terahertz (THz) reflectance tomography, where scattered THz waveforms are measured using a high resolution asynchronous-optical-sampling THz time domain spectroscopy (AOS THz-TDS) technique, and 3-D tomographic reconstruction is accomplished using a compressed sensing approach. One of the main advantages of the proposed system is a significant reduction of acquisition time without sacrificing the reconstruction quality thanks to the sufficient incoherency in the pulse-echo mode sensing matrix and the fast sampling scheme in AOS THz-TDS.

Approximate Sparse Recovery: Optimizing Time and Measurements by Anna Gilbert, Yi Li, Ely Porat, Martin Strauss. The abstract reads:

An approximate sparse recovery system consists of parameters $k,N$, an $m$-by-$N$ measurement matrix, $\Phi$, and a decoding algorithm, $\mathcal{D}$. Given a vector, $x$, the system approximates $x$ by $\widehat x =\mathcal{D}(\Phi x)$, which must satisfy $\| \widehat x - x\|_2\le C \|x - x_k\|_2$, where $x_k$ denotes the optimal $k$-term approximation to $x$. For each vector $x$, the system must succeed with probability at least 3/4. Among the goals in designing such systems are minimizing the number $m$ of measurements and the runtime of the decoding algorithm, $\mathcal{D}$.
In this paper, we give a system with $m=O(k \log(N/k))$ measurements--matching a lower bound, up to a constant factor--and decoding time $O(k\log^c N)$, matching a lower bound up to $\log(N)$ factors.
We also consider the encode time (i.e., the time to multiply $\Phi$ by $x$), the time to update measurements (i.e., the time to multiply $\Phi$ by a 1-sparse $x$), and the robustness and stability of the algorithm (adding noise before and after the measurements). Our encode and update times are optimal up to $\log(N)$ factors.