CS: Sparse solution of underdetermined linear systems, CS and Random Sensor Arrays, Finite range scalar quantization for CS

Today we have three new papers, a review, another on random arrays and CS and how this can impact inverse problems in sonar and radar applications, and finally another one on a surprising quantization in A/D processes in CS that should impact future CS architectures. Enjoy:

On sparse solution of underdetermined linear systems by Ming Jun Lai. The abstract reads:

We first explain the research problem of finding the sparse solution of underdetermined linear systems with some applications. Then we explain three different approaches how to solve the sparse solution: the ℓ1 approach, the orthogonal greedy approach, and the ℓq approach with 0 \lt q \le 1. We mainly survey recent results and present some new or simplified proofs. In particular, we give a good reason why the orthogonal greedy algorithm converges and why it can be used to find the sparse solution. About the restricted isometry property (RIP) of matrices, we provide an elementary proof to a known result that the probability that the random matrix with iid Gaussian variables possesses the PIP is strictly positive.

Lawrence Carin, On the Relationship Between Compressive Sensing and Random Sensor Arrays
the abstract reads:

Random sensor arrays are examined from a compressive sensing (CS) perspective. It is demonstrated that the natural random-array projections manifested by the media Green’s function are consistent with the projection-type measurements associated with CS. This linkage allows the use of existing CS theory to quantify the performance of random arrays, of interest for array design. The analysis demonstrates that the CS theory is applicable to arrays in vacuum as well as in the presence of a surrounding media; further, the presence of a surrounding media with known properties may be used to improve array performance.

There is also new entry in the Rice Compressed Sensing repository:

Finite range scalar quantization for compressive sensing by Jason Laska, Petros Boufounos and Richard Baraniuk. The abstract reads:

Analog-to-digital conversion comprises of two fundamental discretization steps: sampling and quantization. Recent results in compressive sensing (CS) have overhauled the conventional wisdom related to the sampling step, by demonstrating that sparse or compressible signals can be sampled at rates much closer to their sparsity rate, rather than their bandwidth. This work further overhauls the conventional wisdom related to the quantization step by demonstrating that quantizer overflow can be treated differently in CS and by exploiting the tradeoff between quantization error and overflow. We demonstrate that contrary to classical approaches that avoid quantizer overflow, a better finite-range scalar quantization strategy for CS is to amplify the signal such that the finite range quantizer overflows at a pre-determined rate, and subsequently reject the overflowed measurements from the reconstruction. Our results further suggest a simple and effective automatic gain control strategy which uses feedback from the saturation rate to control the signal gain.


Image Credit: NASA/JPL/Space Science Institute, Saturn view from Cassini on June 28, 2009.

CS: L1 Homotopy, Capturing Functions in Infinite Dimensions, ABCS: Approximate Bayesian Compressed Sensing

Muhammad Salman Asif and Justin Romberg just released the code implementing their recent preprint previously mentioned here:

L1 Homotopy: A MATLAB toolbox for homotopy algorithms in L1 norm minimization problems
The page reads:

Introduction:

In this package we have implemented some homotopy algorithms to recover sparse signals from linear measurements.

The convex optimization problems we solve are:

· Basis pursuit denoising (BPDN) \ LASSO
· Dantzig selector
· L1 decoding
· Robust L1 decoding

In addition to solving these problems from scratch, we provide dynamic algorithms to update the solution as

· New measurements are sequentially added to the system
· Signal varies over time

The preprint is: Dynamic updating for L1 minimization by Muhammad Salman Asif and Justin Romberg. I'll add the code shortly to the reconstruction section of the Compressive Sensing Big Picture page.

Albert Cohen just released the 4th course notes of Ron DeVore's 4th lecture in Paris entitled Capturing Functions in Infinite Dimensions ( the third lecture is here, and the first and second are here), The abstract reads:

The following are notes on stochastic and parametric PDEs of the short course in Paris. Lecture 4: Capturing Functions in Infinite Dimensions
Finally, we want to give an example where the problem is to recover a function of infinitely many variables. We will first show how such problems occur in the context of stochastic partial differential equations.

Following last entry on CSBP, here is yet another Bayesian approach:

ABCS: Approximate Bayesian Compressed Sensing by Avishy Carmi, Pini Gurfil, Dimitri Kanevsky, Bhuvana Ramabhadran.The abstract reads:

In this work we present a new approximate Bayesian compressed sensing scheme. The new method is based on a unique type of sparseness-promoting prior, termed here semi-Gaussian owing to its Gaussian-like formulation. The semi-Gaussian prior facilitates the derivation of a closed-formrecursion for solving the noisy compressed sensing problem. As part of this, the discrepancy between the exact and the approximate posterior pdf is shown to be of the order of a quantity that is computed online by the new scheme. In the second part of this work, a random field-based classifier utilizing the approximate Bayesian CS scheme is shown to attain a zero error rate when applied to fMRI classification.

At some point we probably need to have a way to compare all these Bayesian approaches.

CS: CSBP, CoSAMP, Freedom through Imperfection: Exploiting the flexibility offered by redundancy in signal processing, Lossy Speech Compression Via CS

In yesterday's post I mentioned Bayesian Compressive Sensing via Belief Propagation by Dror Baron, Shriram Sarvotham, and Richard Baraniuk. Here are the Matlab files used to simulate the CS-BP algorithm. The code was rewritten by Danny Bickson in March 2009 and his implementation appears here. I note the interesting timing of this bayesian algorithm with other reconstruction codes like CoSAMP or IHT. Even though it is slower compared to IHT, I am not sure that other bayesian approaches can compare quite nicely to the other algorithm. This test also undermines the need for an all-out benchmarking exercise.

While we are on the subject of CoSAMP, Tomoya Sakai corrected an algorithm presented in this blog. His new algorithm now takes care of signals without the need for this signal to be positive. The code is available here. Thanks Tomoya ! I'll update the local CS code page for this item.

Today, we also have Rachel Ward's thesis entitled Freedom through Imperfection: Exploiting the flexibility offered by redundancy in signal processing. The abstract reads:

This thesis consists of four chapters. The first two chapters pertain to the design of stable quantization methods for analog to digital conversion, while the third and fourth chapters concern problems related to compressive sensing. In the first chapter, we study the -encoder and golden ratio encoder, and show that these quantization schemes are robust with respect to uncertainty in the multiplication element of their implementation, whereby x - \beta x. In particular, we use a result from analytic number theory to show that the possibly unknown value of \beta can be reconstructed as the unique root of a power series with coefficients in (-1; 0; 1) obtained from the quantization output of test input x and its negative, x. The focus of our attention in Chapter 2 is Sigma Delta (\Sigma \Delta) modulation, a course quantization method in analog to digital conversion that is widely used for its simplicity of implementation and robustness to component imperfections. A persistent problem in \Sigma \Delta quantization of audio signals is the occurrence of undesirable tones arising from periodicities in the bit output; these tones are particularly intolerable in the space between successive audio tracks. As one of the contributions of this thesis, we show that the standard second order 1-bit \Sigma \Delta scheme can be modified so as to eliminate such periodicities, and this modification can be achieved without sacrificing accuracy or introducing significant complexity. The emerging area of compressed sensing guarantees that sufficiently sparse signals can be recovered from significantly fewer measurements than their underlying dimension suggests, based on the observation that an N dimensional real-valued vector can be reconstructed eciently to within a factor of its best k-term approximation by taking m = k logN measurements, or inner products. However, the quality of such a reconstruction is not assured if the underlying sparsity level of the signal is unknown. In Chapter 3, we show that sharp bounds on the errors between a signal and p estimates (corresponding to a dierent sparsity hypotheses, say) can be achieved by reserving only O(log p) measurements of the total m measurements for this purpose. The proposed technique is reminiscent of cross validation in statistics and learning theory, and theoretical justication in the context of compressed sensing is provided by the Johnson Lindenstrauss lemma. In Chapter 4, we study the relation between nonconvex minimization problems arising in compressed sensing and those known as free-discontinuity problems, which are often encountered in the areas of image segmentation and edge detection. We adapt recent thresholding techniques in the area of sparse recovery to a class of nonconvex functionals that contains both compressed sensing and free-discontinuity-type problems. Along the way, we establish a connection between these two types of problems, using the notion of gamma convergence, and gain new insights into the minimizing solutions of such functionals.

Finally, I just found this on the interwebs: Lossy Speech Compression Via Compressed Sensing-Based Kalman Filtering by Avishy Carmi, Dimitri Kanevsky, Bhuvana Ramabhadran.The abstract reads:

We present a new algorithm for lossy speech compression. The new algorithm is based on a simple technique for embedding a compressed sensing mechanism within a conventional Kalman filter. As such, it is capable of constructing compressed representations using significantly less samples than what is usually considered necessary.

CS: Bayesian CS via Belief Propagation, Iterative Decoding of High-Rate LDPC, DeVore's third lecture, Convex Sparse Matrix Factorizations

Two improved versions have appeared on Arxiv. Both papers have now been submitted for publication:

• Dror let me know about Bayesian Compressive Sensing via Belief Propagation by Dror Baron, Shriram Sarvotham, and Richard Baraniuk.
• On the Iterative Decoding of High-Rate LDPC Codes With Applications in Compressed Sensing by Fan Zhang, Henry Pfister

The Course Notes of the third lecture given by Ron DeVore in Paris has been released on Albert Cohen's page. It features "Capturing Functions in High Dimensions" and seems to aim at giving bounds for nonlinear compressed sensing and should have an impact in manifold signal processing. Interesting. The first two lectures were mentioned here. The beginning of the lecture starts with

1.1 Classifying High Dimensional Functions:

Our last two lectures will study the problem of approximating (or capturing through queries) a function f defined on ⊂ R^N with N very large. The usual way of classifying functions is by smoothness. The more derivatives a function has the nicer it is and the more efficiently it can be numerically approximated. However, as we move into high space dimension, this type of classification will suffer from the so-called curse of dimensionality which we shall now quantify

In other news, in the direction of dictionary learning we have: Convex Sparse Matrix Factorizations by Francis Bach, Julien Mairal, Jean Ponce. The abstract reads:

We present a convex formulation of dictionary learning for sparse signal decomposition. Convexity is obtained by replacing the usual explicit upper bound on the dictionary size by a convex rank-reducing term similar to the trace norm. In particular, our formulation introduces an explicit trade-off between size and sparsity of the decomposition of rectangular matrices. Using a large set of synthetic examples, we compare the estimation abilities of the convex and nonconvex approaches, showing that while the convex formulation has a single local minimum, this may lead in some cases to performance which is inferior to the local minima of the non-convex formulation.

Credit: JAXA, the movie taken by the Kaguya probe as it crashes on the Moon on June 11th, 2009.

CS: Testing the Non-Negative Nullspace Property for the Linear Transport Equation ?

The linear transport equation or the Linear Boltzmann Equation is hard to solve even in the linear case. You may recall my mention of a presentation by Hongkai Zhao on A fast solver for radiative transport equation and applications in optical imaging where I was not sure that the RIP was such a good benchmark. Ever since I have wondered how other conditions recently presented might be a little more appropriate to show that solving the transport equation can be performed using Linear Programming. Here is the idea. Let us say we are trying to solve the following problem:

H f = S (1)

where H is a linear transport operator, S is the known source function and the unknown is function f. The reason this type of problem is not readily solved is that the dimension of the problem is large and therefore any type of sampling/discretization yield very large matrices. In production codes, when one solves the real problem, one never produces the discretized version of H, rather the element of the matrix are computed on the fly. Back to our problem, one of the first thing to solve for is the attendant homogenous equation

H f = 0

There have been a number of publications on the subject yielding families of functions \psi with index i (see [1]) such that:

H \psi_i = 0

\psi_i represents elements of the nullspace of operator H or simply the solution of the homogenous equation (1).

The physics of the problem requires the solution f to (1) to be sparsely decomposed in a new basis \phi_i made up of positive functions such as splines. One can also expect the solution for (1) to involve a set of positive coefficients when projected on the new basis \phi_i (this also probably require the use of a multiscale set of splines not unlike the ones studied by Thierry Blu and Michael Unser)

Sparsity and Positivity, mmhhh...we have seen these elements before. More precisely, in a presentation on the nullspace property for positive signals entitled Sparse Recovery of Positive Signals with Minimal Expansion presented by Alex Dimakis, a joint work with M. Amin Khajehnejad , Weiyu Xu, Babak Hassibi (the attendant paper is Sparse Recovery of Positive Signals with Minimal Expansion ).

So with f = \Sigma w_i \phi_i = [...phi...] [x], and x sparse, we are now trying to solve for:

H [...phi...] [x] = S (2)

or

min||x||_0 s.t H[...phi...][x] = S

This expression is equivalent to

min||x||_0 s.t H[...phi...][x] = S

iff

w in the nullspace of H[...phi...], w has at least k negative elements.

The nullspace condition can therefore be found when one finds the w's. They can be found to be as follows:

[...phi...][w]=[...psi...][I]

or

[...psi...]^T [...phi...][w] = I

or

[w] = ([...psi...]^T [...phi...])^(-1)

([...psi...]^T [...phi...]) is the matrix with element equal to \int(phi_i * psi_j).

Every column of that w matrix should then be inspected and one should set the smaller number of elements of every column as negative elements and put the larger number of elements as positive (since both \psi_i and \psi_i are elements of the nullspace of H) then one should check that "...the sum of every n − k nonnegative elements should be greater than the absolute sum of the rest...". It looks easy :-)




Reference:
[1] Linear Transport Theory by Kenneth M. Case and Paul F. Zweifel

Credit: NASA, Sarychev Peak Eruption, Kuril Islands as taken by the astronauts from the International Space Station 12 days ago.

Have you ever crashed under a pale moonlight ?

LRO has made it into Lunar Orbit. LCROSS is positioning itself and you can watch it live here.


Both spacecrafts lifted off three days ago and the video of the launch from the rocket can be seen here.



LCROSS is designed to hit the Moon at high speed. Kaguya, the japanese probe that was crashed on the moon 12 days ago had time to send several images as it was crashing. wow.



Congratulations to both NASA and JAXA!

Credit: NASA, JAXA.

The title of this entry comes from a line in the movie Batman that came out 20 years ago. This movie was the first movie changing the whole game in the show biz industry. The actual quote "Have you ever danced with the devil under the pale moonlight"

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

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

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

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

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

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

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

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

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

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

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


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

CS: First Image of Herschel/PACS and Probability in Asymptotic Geometry workshop

Badabim badaboom, ever since it launched, the suspense was whether or not the PACS camera was working.

The photos above are the first images from that camera and it looks like it is working! Woohoo. Let us now wait until the Compressed Sensing encoding mechanism is tried.

On a totally different note, Rafal Latala, Assaf Naor, and Grigoris Paouris are organizing a Concentration Week on "Probability in Asymptotic Geometry" for the week of July 20-24 at Texas A&M University. For more information on this concentration week please visit,

http://www.math.tamu.edu/~grigoris/ConcentrationWeekHome.html

This Concentration Week will focus on high dimensional phenomena concerning convex bodies, random polytopes, and random matrices. These topics lie in the intersection of probability, analysis, geometry, and combinatorics. The goal is to expose the huge variety of techniques used in the study of these objects and to explore the connections between them.

CS: TVAL3 TV minimization by Augmented Lagrangian and ALternating direction ALgorithms, and YALL1

Chengbo Li, Wotao Yin, and Yin Zhang just released

TVAL3: TV minimization by Augmented Lagrangian and ALternating direction ALgorithms


From the page:

This solver can currently be applied to the following TV-minimization problems:


(Isotropic/Anisotropic TV) min TV(u) s.t. Au = b

(Isotropic/Anisotropic TV+) min TV(u) s.t. Au = b and u \gt 0

(Isotropic/Anisotropic TVL2) min TV(u) + (μ/2)||Au - b||22

(Isotropic/Anisotropic TVL2+) min TV(u) + (μ/2)||Au - b||22 s.t. u \gt 0

where A is m by n with m less than n representing the measurement matrix, b is a dense vector representing the observation, and the solution u is supposed to be (approximately) sparse or piecewise linear. The data (A,b) can be real or complex, and the signal u can also be complex in cases of no nonnegativity constraint. Besides, A*A'=I is not required.

You can download the code here.

In related news, YALL1 version beta-5 was released yesterday with improved robustness for A*A' =\= I.

Both reconstruction softwares will be added to the reconstruction section of the Compressive Sensing Big Picture page.

Credit: NASA, LRO/LCROSS on the launch pad via Damaris' blog.

CS: Foundations of CS, Data Stream Algorithms, Isometry-enforcing Data Transformations,The Best Bits, Homomorphic Encryption

Albert Cohen just released Ron Devore's lecture notes he is presenting in Paris entitled: Foundations of Compressed Sensing.

The lecture notes on Data Stream Algorithms by Muthu Muthukrishnan in Barabados are here. Here is an excerpt:

Motivation
The algorithms we are going to describe act on massive data that arrive rapidly and cannot be stored. These algorithms work in few passes over the data and use limited space (less than linear in the input size). We start with three real life scenarios motivating the use of such algorithms.

Example 1: Telephone call. Every time a cell-phone makes a call to another phone, several calls between switches are being made until the connection can be established. Every switch writes a record for the call over approx. 1000 Bytes. Since a switch can receive up to 500 million calls a day, this adds up to something like 1 Terabyte per month information. This is a massive amount of information but has to be analyzed for different purposes. An example is searching for drop calls trying to find out under what circumstances such drop calls happen. It is clear that for dealing with this problem we do not want to work with all the data, but just want to filter with a few passes the useful information.

Example 2: The Internet. The Internet is made of a network of routers connected to each other, receiving and sending IP packets. Each IP packet contains a packet log including its source and destination addresses as well as other information that is used by the router to decide which link to take for sending it. The packet headers have to be processed at the rate at which they flow through the router. Each package takes about 8 nanoseconds to go through a router and modern routers can handle a few million packets per second. Keeping the whole information would need more than
one Terabyte information per day and router. Statistical analysis of the traffic through the router can be done, but this has to be performed on line at nearly real time.

Example 3: Web Search. Consider a company for placing publicity in the Web. Such a
company has to analyze different possibilities trying to maximize for example the number of clicks they would get by placing an add for a certain price. For this they would have to analyze large amounts of data including information on web pages, numbers of page visitors, add prices and so on. Even if the company keeps a copy of the whole net, the analysis has to be done very rapidly since this information is continuously changing.

Also found on the interwebs: Isometry-enforcing Data Transformations for Improving Sparse Model Learning by Avishy Carmi, Irina Rish, Guillermo Cecchi, Dimitri Kanevsky, Bhuvana Ramabhadran. The abstract reads:

Imposing sparsity constraints (such as l1-regularization) on the model parameters is a practical and efficient way of handling very high-dimensional data, which also yields interpretable models due to embedded feature-selection. Compressed sensing (CS) theory provides guarantees on the quality of sparse signal (in our case, model) reconstruction that relies on the so-called restricted isometry property (RIP) of the sensing (design) matrices. This, however, cannot be guaranteed as these matrices form a subset of the underlying data set. Nevertheless, as we show, one can find a distance-preserving linear transformation of the data such that any transformed subspace of the data satisfied the RIP at some level. We demonstrate the effects of such RIP-enforcing data transformation on sparse learning methods such as sparse and compressed Random Fields, as well as sparse regression (LASSO), in the context of classifying mental states based on fMRI data.

On Thursday 25 June 2009 at 15:15, there will be a presentation entitled Sparse recovery using sparse matrices by Prof. Piotr Indyk at EPFL/Summer Research Institute in room BC 01. The abstract reads:

Over the recent years, a new *linear* method for compressing high-dimensional data has been discovered. For any high-dimensional vector x, its *sketch* is equal to Ax, where A is a carefully designed m x n matrix (possibly chosen at random). Although typically the sketch length m is much smaller than the number of dimensions n, the sketch often contains enough information to recover a *sparse approximation* to x. At the same time, the linearity of the sketching method is very convenient for many applications, such as data stream computing and compressed sensing. The major sketching approaches can be classified as either combinatorial (using sparse sketching matrices) or geometric (using dense sketching matrices). Traditionally they have achieved different trade-offs, notably between the compression rate and the running time. In this talk we show that, in a sense, the combinatorial and geometric approaches are based on different manifestations of the same phenomenon. This connection will enable us to obtain several novel algorithms and constructions, including the first known algorithm that provably achieves the optimal measurement bound and near-linear recovery time.

There is also an article in the American Scientist on Compressive sensing entitled: The Best Bits by Brian Hayes.

I don't read Polish but Radek Adamczak’s weblog points to a lecture series by Alice Guionnet entitled Large Random Matrices: Lectures on Macroscopic Asymptotics.

Finally, I was reading Michael Nielsen blog and noticed a framework that looks similar to the one being used in manifold signal processing. Michael mentions the following:

Fully homomorphic encryption

• Very interesting paper about a cryptographic scheme that allows computation directly on the encoded data, without requiring decryption.

The paper is : Fully homomorphic encryption using ideal lattices by Graig Gentry. The abstract reads:

We propose a fully homomorphic encryption scheme -- i.e., a scheme that allows one to evaluate circuits over encrypted data without being able to decrypt. Our solution comes in three steps. First, we provide a general result -- that, to construct an encryption scheme that permits evaluation of arbitrary circuits, it suffices to construct an encryption scheme that can evaluate (slightly augmented versions of) its own decryption circuit; we call a scheme that can evaluate its (augmented) decryption circuit bootstrappable.

Next, we describe a public key encryption scheme using ideal lattices that is almost bootstrappable.

Lattice-based cryptosystems typically have decryption algorithms with low circuit complexity, often dominated by an inner product computation that is in NC1. Also, ideal lattices provide both additive and multiplicative homomorphisms (modulo a public-key ideal in a polynomial ring that is represented as a lattice), as needed to evaluate general circuits.

Unfortunately, our initial scheme is not quite bootstrappable -- i.e., the depth that the scheme can correctly evaluate can be logarithmic in the lattice dimension, just like the depth of the decryption circuit, but the latter is greater than the former. In the final step, we show how to modify the scheme to reduce the depth of the decryption circuit, and thereby obtain a bootstrappable encryption scheme, without reducing the depth that the scheme can evaluate. Abstractly, we accomplish this by enabling the encrypter to start the decryption process, leaving less work for the decrypter, much like the server leaves less work for the decrypter in a server-aided cryptosystem.

Graig Gentry made a presentation on this at the intractability Center at Princeton. The video is here. Other presentations made at the
Complexity and Cryptography: Status of Impagliazzo’s Worlds workshop on June 3-5 are here.



Credit: NASA, The LCROSS mission will launch today and will crash on the moon in 4 months.

CS: Cramér–Rao bound, 3-D Upper Airway MRI Using CS, unveiling patterns in networks, Audio Source Separation, Concatenate and Boost

I hope you have all recovered from the mesmerizing paper featured the day before yesterday. You also know that part of the paper was featured in this video presentation at SMLS 09. At the same workshop Mark Plumbley and Marco Bevilacqua presented "Stagewise Polytope Faces Pursuit for Recovery of Sparse Representations". It is in this video at the 27 minutes mark. I also liked the pitch for the next poster ( Subspectral Algorithms for Sparse Learning by Baback Moghaddam, Yair Weiss, Shai Avidan ). All the videos of the SMLS 09 workshop are here.

Today, we also have three papers from the Rice Compressive Sensing resource that I have not covered yet and one papers from Arxiv and another from the interwebs:


The Cramér–Rao bound for sparse estimation by Zvika Ben-Haim, Yonina Eldar. The abstract reads:

The goal of this paper is to characterize the best achievable performance for the problem of estimating an unknown parameter having a sparse representation. Specifically, we consider the setting in which a sparsely representable deterministic parameter vector is to be estimated from measurements corrupted by Gaussian noise, and derive a lower bound on the mean-squared error (MSE) achievable in this setting. To this end, an appropriate definition of bias in the sparse setting is developed, and the constrained Cramer-Rao bound (CRB) is obtained. This bound is shown to equal the CRB of an estimator with knowledge of the support set, for almost all feasible parameter values. Consequently, in the unbiased case, our bound is identical to the MSE of the oracle estimator. Combined with the fact that the CRB is achieved at high signal-to-noise ratios by the maximum likelihood technique, our result provides a new interpretation for the common practice of using the oracle estimator as a gold standard against which practical approaches are compared.

Accelerated Three-Dimensional Upper Airway MRI Using Compressed Sensing by Yoon-Chul Kim, Shrikanth S. Narayanan, Krishna Nayak. The abstract reads:

In speech-production research, three-dimensional (3D) MRI of the upper airway has provided insights into vocal tract shaping and data for its modeling. Small movements of articulators can lead to large changes in the produced sound, therefore improving the resolution of these data sets, within the constraints of a sustained speech sound (6–12 s), is an important area for investigation. The purpose of the study is to provide a first application of compressed sensing (CS) to high-resolution 3D upper airway MRI using spatial finite difference as the sparsifying transform, and to experimentally determine the benefit of applying constraints on image phase. Estimates of image phase are incorporated into the CS reconstruction to improve the sparsity of the finite difference of the solution. In a retrospective subsampling experiment with no sound production, 5
and 4
were the highest acceleration factors that produced acceptable image quality when using a phase constraint and when not using a phase constraint, respectively. The prospective use of a 5
undersampled acquisition and phase constrained CS reconstruction enabled 3D vocal tract MRI during sustained sound production of English consonants /s/, /
/, /l/, and /r/ with 1.5 x 1.5 x 2.0 mm3 spatial resolution and 7 s of scan time.

A fast and compact method for unveiling significant patterns in high speed networks by T Bu, J Cao, A Chen, PPC Lee. The summary reads:

Identification of significant patterns in network traffic, such as IPs or flows that contribute large volume (heavy hitters) or introduce large changes (heavy changers), has many applications in accounting and network anomaly detection. As network speed and the number of flows grow rapidly, tracking per-IP or per-flow statistics becomes infeasible due to both the computational overhead and memory requirements. In this paper, we propose a novel sequential hashing scheme that requires only O(H log N) both in memory and computational overhead that are close to being optimal, where N is the the number of all possible keys (e.g., flows, IPs) and H is the maximum number of heavy keys. Moreover, the generalized sequential hashing scheme makes it possible to trade off among memory, update cost, and detection cost in a large range that can be utilized by different computer architectures for optimizing the overall performance. In addition, we also propose statistically efficient algorithms for estimating the values of heavy hitters and heavy changers. Using both theoretical analysis and experimental studies of Internet traces, we demonstrate that our approach can achieve the same accuracy as the existing methods do but using much less memory and computational overhead.

Matrix Completion from Noisy Entries by Raghunandan Keshavan, Andrea Montanari, and Sewoong Oh. The abstract reads:

Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the `Netflix problem') to structure-from-motion and positioning. We study a low complexity algorithm introduced by Keshavan et al.(2009), based on a combination of spectral techniques and manifold optimization, that we call here OptSpace. We prove performance guarantees that are order-optimal in a number of circumstances.

As mentioned earlier, the OptSpace algorithm implementation is here.


Benchmarking Flexible Adaptive Time-Frequency Transforms for Underdetermined Audio Source Separation by Andrew Nesbit, Emmanuel Vincent and Mark Plumbley. The abstract reads:

We have implemented several fast and flexible adaptive lapped orthogonal transform (LOT) schemes for underdetermined audio source separation. This is generally addressed by time-frequency masking, requiring the sources to be disjoint in the time-frequency domain.
We have already shown that disjointness can be increased via adaptive dyadic LOTs. By taking inspiration from the windowing schemes used in many audio coding frameworks, we improve on earlier results in two ways. Firstly, we consider non-dyadic LOTs which match the time-varying signal structures better. Secondly, we allow for a greater range of overlapping window profiles to decrease window boundary artifacts. This new scheme is benchmarked through oracle evaluations, and is shown to decrease computation time by over an order of magnitude compared to using very general schemes, whilst maintaining high separation performance and flexible signal adaptivity. As the results demonstrate, this work may find practical applications in high fidelity audio source separation.

Concatenate and Boost for Multiple Measurement Vector Problems by Ok Kyun Lee, Jong Chul Ye. The abstract reads:

Multiple measurement vector (MMV) problem addresses the recovery of a set of sparse signal vectors that share common non-zero support, and has emerged an important topics in compressed sensing. Even though the fundamental performance limit of recoverable sparsity level has been formally derived, conventional algorithms still exhibit significant performance gaps from the theoretical bound. The main contribution of this paper is a novel concatenate MMV and boost (CoMBo) algorithm that achieves the theoretical bound. More specifically, the algorithm concatenates MMV to a larger dimensional SMV problem and boosts it by multiplying random orthonormal matrices. Extensive simulation results demonstrate that CoMBo outperforms all existing methods and achieves the theoretical bound as the number of measurement vector increases.

CS: Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing

It's of interest to folks in dimensionality reduction, compressive sensing, group testing ... it's 47 pages long. Enjoy:

Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing by Jared Tanner and David Donoho. The abstract reads:

We review connections between phase transitions in high-dimensional combinatorial geometry and phase transitions occurring in modern high-dimensional data analysis and signal processing. In data analysis, such transitions arise as abrupt breakdown of linear model selection, robust data fitting or compressed sensing reconstructions, when the complexity of the model or the number of outliers increases beyond a threshold. In combinatorial geometry these transitions appear as abrupt changes in the properties of face counts of convex polytopes when the dimensions are varied. The thresholds in these very different problems appear in the same critical locations after appropriate calibration of variables.
These thresholds are important in each subject area: for linear modelling, they place hard limits on the degree to which the now-ubiquitous high-throughput data analysis can be successful; for robustness, they place hard limits on the degree to which standard robust fitting methods can tolerate outliers before breaking down; for compressed sensing, they define the sharp boundary of the undersampling/sparsity tradeoff curve in undersampling theorems. Existing derivations of phase transitions in combinatorial geometry assume the underlying matrices have independent and identically distributed (iid) Gaussian elements. In applications, however, it often seems that Gaussianity is not required. We conducted an extensive computational experiment and formal inferential analysis to test the hypothesis that these phase transitions are universal across a range of underlying matrix ensembles. We ran millions of linear programs using random matrices spanning several matrix ensembles and problem sizes; to the naked eye, the empirical phase transitions do not depend on the ensemble, and they agree extremely well with the asymptotic theory assuming Gaussianity. Careful statistical analysis reveals discrepancies which can be explained as transient terms, decaying with problem size. The experimental results are thus consistent with an asymptotic large-n universality across matrix ensembles; finite-sample universality can be rejected.

CS: Quantization for Compressed Sensing Reconstruction, Optimal Quantization of Random Measurements in CS, Journal of Computational Geometry

Today we have two papers and a call for a new journal that includes CS as a subject of interest:

The two papers talk about quantization in CS an issue that is beginning to gain some coverage in the community:

Quantization for Compressed Sensing Reconstruction by John Z. Sun and Vivek K Goyal. The abstract reads:

Quantization is an important but often ignored consideration in discussions about compressed sensing. This paper studies the design of quantizers for random measurements of sparse signals that are optimal with respect to mean-squared error of the lasso reconstruction. We utilize recent results in high-resolution functional scalar quantization and homotopy continuation to approximate the optimal quantizer. Experimental results compare this quantizer to other practical designs and show a noticeable improvement in the operational distortion-rate performance.

Optimal Quantization of Random Measurements in Compressed Sensing by John Z. Sun and Vivek K Goyal. The abstract reads:

Quantization is an important but often ignored consideration in discussions about compressed sensing. This paper studies the design of quantizers for random measurements of sparse signals that are optimal with respect to mean-squared error of the lasso reconstruction. We utilize recent results in high-resolution functional scalar quantization and homotopy continuation to approximate the optimal quantizer. Experimental results compare this quantizer to other practical designs and show a noticeable improvement in the operational distortion-rate performance.

From the Dense outliers blog, here is a new announcement for a journal:

The Journal of Computational Geometry (jocg.org) is now accepting submissions.

Scope and Focus

The Journal of Computational Geometry (JoCG) is an international open access electronic journal devoted to original research of the highest quality in all aspects of computational geometry. JoCG publishes papers on the design and analysis of geometric algorithms, the complexity of geometric problems, experimental work on geometric algorithms, applications of computational geometry, and topics at the intersection of geometry and algorithms. Topics include metric space embeddings, graph drawing, computational topology, topological learning, meshing, compressed sensing, manifold learning, computer-aided design, discrete geometry, and combinatorial geometry. Outstanding survey papers in the area are also considered.

Credit photo: University of New South Wales/Anglo-Australian Observatory (J. Bailey and S. Lee). Jeremy Bailey (University of New South Wales) and Steve Lee (Anglo-Australian Observatory) with the Anglo-Australian Observatory took this series of shots were taken just before and right after the japanese Kaguya spacecraft impacted the moon. If you recall Kaguya produced the magnificient video in this entry.

CS: The Two Stage $l_1$ Approach to the Compressed Sensing Problem, with code, Sparse Sampling

Stephane Chretien who just released on arxiv his paper on his Two stage L1 method, also let me know that he released a webpage for the software as well. The paper is The Two Stage $l_1$ Approach to the Compressed Sensing Problem by Stephane Chretien. The abstract reads:

This paper gives new results on the recovery of sparse signals using $l_1$-norm minimization. We introduce a two-stage $l_1$ algorithm. The first step consists of the standard $\ell_1$ relaxation. The second step consists of optimizing the $\ell_1$ norm of a subvector whose components are indexed by the $\rho m$ largest components in the first stage. If $\rho$ is set to $\frac14$, an intuitive choice motivated by the fact that $\frac{m}4$ is an empirical breakdown point for the plain $\ell_1$ exact recovery probability curve, Monte Carlo simulations show that the two-stage $\ell_1$ method outperforms the plain $\ell_1$.

as presented in the page where the code is featured:

This method is a special case of the Alternating l1 algorithm.

The main advantage is that only two l1-type relaxations are performed thus enjoying low computational cost compared to the original Alternating l1 algorithm and the Reweighted l1 algorithm of Candès, Wakin and Boyd. Moreover, the simulations show that the percentage of exact recovery is almost as high as the highest one given by the Reweighted l1 without needing to tune any unknown parameter.

The paper was presented at SPARS'09 but I had not mentioned it before. It is included in the algorithms performing reconstruction section of the big picture. The code is located in this page. Stephane tells me that it will soon be translated in Matlab. It is currently written in Python.


Finally, here is a 172 pages tutorial to be shown at ICASSP 2009 entitled Sparse Sampling: Theory, Algorithms and Applications by Thierry Blu, Pier-Luigi Dragotti, Pina Marziliano, Martin Vetterli that features the Finite Rate of Innovation concept. If you are interested in trying it out, you may want to check Vincent Y. F. Tan and and Vivek Goyal's paper entitled Estimating signals with finite rate of innovation from noisy samples: A stochastic algorithm whose attendant matlab code is now available here.

CS: Adaptive Compressed Sensing, Gradient Based Recovery Algos, Modified Frame Reconstruction Algo, On Sparse Channel Estimation, a presentation, CVX

Today we have four new papers on arxiv that I have not covered yet:

Echoing some of the babbling written here, here is a serious attempt at mapping cortical information and compressed sensing. As I have written before, the robustness of compressed sensing enabled by random sampling is just too nice of a property to not think about mapping it to a biological system. This is great.

Adaptive compressed sensing - a new class of self-organizing coding models for neuroscience by William Coulter, Christopher Hillar, Friedrich Sommer. The abstract reads:

Sparse coding networks, which utilize unsupervised learning to maximize coding efficiency, have successfully reproduced response properties found in primary visual cortex \cite{AN:OlshausenField96}. However, conventional sparse coding models require that the coding circuit can fully sample the sensory data in a one-to-one fashion, a requirement not supported by experimental data from the thalamo-cortical projection. To relieve these strict wiring requirements, we propose a sparse coding network constructed by introducing synaptic learning in the framework of compressed sensing. We demonstrate that the new model evolves biologically realistic spatially smooth receptive fields despite the fact that the feedforward connectivity subsamples the input and thus the learning has to rely on an impoverished and distorted account of the original visual data. Further, we demonstrate that the model could form a general scheme of cortical communication: it can form meaningful representations in a secondary sensory area, which receives input from the primary sensory area through a "compressing" cortico-cortical projection. Finally, we prove that our model belongs to a new class of sparse coding algorithms in which recurrent connections are essential in forming the spatial receptive fields.

And here are the three remaining ones (by the way I could not find the webpages of any of the authors, can somebody help ?)

The Physics of Compressive Sensing and the Gradient-Based Recovery Algorithms by Qi Dai, Wei Sha. The abstract reads:

The physics of compressive sensing (CS) and the gradient-based recovery algorithms are presented. First, the different forms for CS are summarized. Second, the physical meanings of coherence and measurement are given. Third, the gradient-based recovery algorithms and their geometry explanations are provided. Finally, we conclude the report and give some suggestion for future work.

Modified Frame Reconstruction Algorithm for Compressive Sensing by Graeme Pope. The abstract reads:

Compressive sensing is a technique to sample signals well below the Nyquist rate using linear measurement operators. In this paper we present an algorithm for signal reconstruction given such a set of measurements. This algorithm generalises and extends previous iterative hard thresholding algorithms and we give sufficient conditions for successful reconstruction of the original data signal. In addition we show that by underestimating the sparsity of the data signal we can increase the success rate of the algorithm.
We also present a number of modifications to this algorithm: the incorporation of a least squares step, polynomial acceleration and an adaptive method for choosing the step-length. These modified algorithms converge to the correct solution under similar conditions to the original un-modified algorithm. Empirical evidence show that these modifications dramatically increase both the success rate and the rate of convergence, and can outperform other algorithms previously used for signal reconstruction in compressive sensing.

and finally, On Sparse Channel Estimation by Brian Carroll. The abstract reads:

The abstract reads:

Channel Estimation is an essential component in applications such as radar and data communication. In multi path time varying environments, it is necessary to estimate time-shifts, scale-shifts (the wideband equivalent of Doppler-shifts), and the gains/phases of each of the multiple paths. With recent advances in sparse estimation (or "compressive sensing"), new estimation techniques have emerged which yield more accurate estimates of these channel parameters than traditional strategies. These estimation strategies, however, restrict potential estimates of time-shifts and scale-shifts to a finite set of values separated by a choice of grid spacing. A small grid spacing increases the number of potential estimates, thus lowering the quantization error, but also increases complexity and estimation time. Conversely, a large grid spacing lowers the number of potential estimates, thus lowering the complexity and estimation time, but increases the quantization error. In this thesis, we derive an expression which relates the choice of grid spacing to the mean-squared quantization error. Furthermore, we consider the case when scale-shifts are approximated by Doppler-shifts, and derive a similar expression relating the choice of the grid spacing and the quantization error. Using insights gained from these expressions, we further explore the effects of the choice and grid spacing, and examine when a wideband model can be well approximated by a narrowband model.

We also have a presentation on Minimum Sum of Distances Estimator: Robustness and Stability by Yariv Sharon, John Wright and Yi Ma. I talked about this here.

In a different direction, Michael Grant and Stephen Boyd let us know that CVX (Matlab Software for Disciplined Convex Programming) has problems:

Reports of problems with 64-bit Windows and Matlab R2009a

Apparently, the MEX files that ship with CVX do not work with the latest and greatest version of the 64-bit Windows version of Matlab. I do not recommend upgrading to R2009a if this is your operating system of choice and you rely on CVX for your work.

Fuller support for 64-bit platforms

Image Credit: NASA/JPL/Space Science Institut, Titan as seen by Cassini three days ago.

CSJob: Advanced Sampling Techniques for Next Generation Ultrasound

Yonina Eldar is looking for a highly motivated post-doctorate fellow, to work on a joint project with General Electrics. The project involves advanced sampling techniques for next generation ultrasound. The position provides a unique opportunity to conduct research on topics that are in the frontier of signal processing and sampling theory, while at the same time have direct impact on industrial applications. A very senior staff member at GE will be closely involved in the project and serve as a mentor. Upon successful completion, the results will be integrated into GEs systems. She is particularly interested in candidates with a strong signal processing background. Knowledge of sampling theory will be helpful. There is no need for a background in ultrasound as we will be working closely with GE staff. Interested candidates are invited to send their CV with names of 2 references to: yonina@ee.technion.ac.il .The position is available immediately. An initial contract of 1 year duration will be offered to the successful candidate, with a possibility of extension.

I have added this ad to the CS jobs page. In the meantime, you may also want to check the HD video of the Japanese Kayuga probe over the moon. Kayuga is slated to impact the moon in the coming weeks. Be sure to check the HD version of it.

Another flyover that has gotten some publicity is the one featured on "Home" this time over earth.

CS: The Junta problem, NESTA, Non-Iterative Superresolution Phase Retrieval of Sparse Images , NAS postdoc

Dick Lipton has a blog entry on the potential connection between the Junta Problem and Compressive Sensing.

Ever since this entry, we have been waiting for it, here it is: the NESTA code is out. Get it here. From the site:

Introduction

NESTA is a fast and robust first-order method than solves basis-pursuit problems and a large number of extensions (including tv-denoising). It is described in the paper NESTA: A Fast and Accurate First-order Method for Sparse Recovery (technical report, April 2009, California Institute of Technology) by Jérôme Bobin, Stephen Becker, and Emmanuel Candès,

The algorithm uses two ideas due to Yurii Nesterov. The first idea is an accelerated convergence scheme for first-order methods, giving the optimal convergence rate for this class of problems. The second idea is a smoothing technique that replaces the non-smooth l1 norm with a smooth version.

The basic algorithm solves the following equation, often known as basis pursuit denoising, or simply as l1-minimization:

The parameter epsilon is typically small and proportional to an estimate of the standard deviation of any noise in the measurements. If epsilon is 0, the problem is known as just basis pursuit. Basis pursuit and basis pursuit denoising are often used in statistics, image-processing, and compressed sensing.

NESTA is capable of solving many other problems; some popular extensions are discussed on this website.

The current version of code for NESTA requires that the measurement matrix A is an orthogonal projection. It is possible to extend NESTA to allow general matrices A, though this is not implemented in the code.

Analysis

For real-world signals, the signal is not sparse, but it may be sparse (or be approximately-sparse, i.e. most energy is concentrated in only a few coefficients) in a dictionary W. For example, W may be a discrete cosine basis, a Gabor frame, a curvelet frame, a wavelet basis, etc. In this case, it may be desirable to solve the analysis-based problem:

An alternative is the synthesis-based problem:

Unless the dictionary is a basis, the two problems are not equivalent. Traditionally, the synthesis-based approach has been used because it requires no modification to basis pursuit solvers: simply treat (AW) as a single operator.

NESTA is one of few algorithms that can solve the analysis problem (in addition to the synthesis problem). The code accepts W as in input.

Note that this allows NESTA to solve the reweighted l1 problem; for this case, W is a diagonal matrix. Demos showing the use of analysis and reweighting are included in the code.

You may recall a reconstruction scheme that was not iterative ? Andy Yagle goes further on that path with the following three papers (matlab codes are included in the papers):

Location of Non-Zeros in Sparse Solutions of Underdetermined Linear Systems of Equations by Andrew Yagle. The abstract reads:

The problem of computing sparse (mostly zero) or sparsifiable (by linear transformation) solutions to greatly underdetermined linear systems of equations has applications in compressed sensing. The locations of the nonzero elements in the solution is a much smaller set of variables than the solution itself. We present explicit equations for the relatively few variables that determine these nonzero locations and also propose an iterative algorithm for their solution.

Non-Iterative Superresolution Phase Retrieval of Sparse Images without Support Constraints by Andrew Yagle. The abstract reads:

We propose a new non-iterative algorithm for phase retrieval of a sparse image from low wavenumber values of its Fourier transform magnitude. No image support constraint is needed. The algorithm uses the sparsity of the image autocorrelation to reconstruct it exactly from low-wavenumber Fourier magnitude data (superresolution) using a variation of MUSIC. The sparsity of the image is then used to reconstruct it recursively from its autocorrelation. Applications include X-ray crystallography and astronomy. Two numerical examples illustrate the algorithm.

Coordinate Descent for Sparse Solutions of Underdetermined Linear Systems of Equations by Andrew Yagle. The abstract reads:

The problem of computing sparse (mostly zero) or sparsifiable (by linear transformation) solutions to greatly underdetermined linear systems of equations has applications in compressed sensing and reduced-exposure imaging. We show that coordinate descent, in which a single variable is varied while all others are held constant, is applicable to a wide variety of such problems. The method is useful for very large problems having dense system matrices.

There is a NAS associateship offered at Kirtland Air Force Base entitled: "Concurrent, Agility, and Distributed Decision Architecture for Compressive Sensing and Complexity Management". Please note the restriction on citizenship. I'll add it to the Compressive Sensing job site.


Image Credit: NASA/JPL/Space Science Institute , view of Rhea from Cassini taken on June 3,

CS: Question about CS and MPI and RFIDs, Matrix Completion, CS in Traffic, Generalizations of the Linearized Bregman Method

On the LinkedIn Compressive Sensing Group discussion, two members asked questions on the potential use of CS in their fields, if you have any ideas you may want to share your knowledge with them. Just for kicks, the group now has 167 members. While we are on te subject of stats, if you check on the right hand side of this site, you'll notice that 517 people are receiving this entry either through their feedreaders or by e-mail, this number doesn't include the people coming to the site directly! But let us come back to the two discussions on the LinkedIn group:

David Skinner asked the interesting question:

Looking for compressive sensing applications to parallel computing

I am interested in the application of new techniques in compressive sensing to produce synopses of communication traces in parallel computing codes. If you know of software or existing research that could aid in generating compact summaries of traces and profiles of MPI based applications I would be glad to hear about them and discuss their use. I have found work on trace compression using these techniques, but they treat each information stream serially. There is an opportunity to compress information across MPI tasks as well (many tasks have similar traces) but have not found prior work in this area.

For what it's worth, David is behind the Integrated Performance Monitoring utility from which the graph above is extracted. The discussion is here. It looks to me that the work in heavy hitters/sketching might seem relevant.

Leon Palafox has this other question :

Compressive Sensing in Accelerometer and RFID Network

I am looking into Compressive Sensing for a solution of a sensor network in order to reduce the sampling rate input of each sensor that by this moment is too high.

The discussion is here. Clearly this is an issue that comes back often, we talked about this in this entry and a recent paper also tried to paint a clear picture of the issues in Sparse Event Detection in Wireless Sensor Networks using Compressive Sensing by Jia Meng, Husheng Li, and Zhu Han,

In the comment section of this entry, Andrea Montanari mentioned that:

...we [Raghunandan Keshavan, Andrea Montanari, and Sewoong Oh ] made available a C version of the matrix completion algorithm, at the same URL: http://www.stanford.edu/~raghuram/recon/index.html

It is pretty fast...

Rahul Garg also let me know that he and Rohit Khandekar will soon post an implementation of GraDes featured in Gradient Descent with Sparsification: An iterative algorithm for sparse recovery with restricted isometry property.

The ever interesting blog on compressed sensing (in Chinese) by Lianlin Li featured the following interesting application of Compressive Sensing:

Traffic Monitoring by David Johnson (entry is here on Lianlin Li's blog)

Lilian Li also noted this interesting paper (translation of his post is here) :

Optimal PSF modeling for weak lensing : complexity and sparsity by Stephane Paulin-Henriksson, A. Refregier, Adam Amara. The abstract reads:

Context. We address the issue of controling the systematic errors in shape measurements for weak gravitational lensing. Aims. We make a step to quantify the impact of systematic errors in modeling the point spread function (PSF) of observations, on the determination of cosmological parameters from cosmic shear. Methods. We explore the impact of PSF fitting errors on cosmic shear measurements using the concepts of complexity and sparsity. Complexity, introduced in a previous paper, characterizes the number of degrees of freedom of the PSF. For instance, fitting an underlying PSF with a model of low complexity produces small statistical errors on the model parameters, although these parameters could be affected by large biases. Alternatively, fitting a large number of parameters (i.e. a high complexity) tends to reduce biases at the expense of increasing the statistical errors. We attempt to find a trade-off between scatters and biases by studying the mean squared error of a PSF model. We also characterize the model sparsity, which describes how efficiently the model is able to represent the underlying PSF using a limited number of free parameters. We present the general case and give an illustration for a realistic example of a PSF modeled by a shapelet basis set. Results. We derive a relation between the complexity and the sparsity of the PSF model, the signal-to-noise ratio of stars and the systematic errors in the cosmological parameters. By insisting that the systematic errors are below the statistical uncertainties, we derive a relation between the number of stars required to calibrate the PSF and the sparsity of the PSF model. We discuss the impact of our results for current and future cosmic shear surveys. In the typical case where the sparsity can be represented by a power-law function of the complexity, we demonstrate that current ground-based surveys can calibrate the PSF with few stars, while future surveys will require hard constraints on the sparsity in order to calibrate the PSF with 50 stars.

We seem to come back often to this issue of calibrating PSFs with few images/targetd :-). Let us hope the blog doesn't go down for maintenance today.

And finally, we have : Analysis and Generalizations of the Linearized Bregman Method by Wotao Yin. The abstract reads:

This paper reviews the Bregman methods, analyzes the linearized Bregman method, and proposes fast generalization of the latter for solving the basis pursuit and related problems. The analysis shows that the linearized Bregman method has the exact penalty property, namely, it converges to an exact solution of the basis pursuit problem if and only if its regularization parameter $\alpha$ is greater than a certain value. The analysis is based on showing that the linearized Bregman algorithm is equivalent to gradient descent applied to a certain dual formulation. This result motivates generalizations of the algorithm enabling the use of gradient-based optimization techniques such as line search, Barzilai-Borwein steps, L-BFGS, and nonlinear conjugate gradient steps. In addition, the paper discusses the selection and update of $\alpha$. The analysis and discussions are limited to the l1-norm but can be extended to other l1-like functions.