CS: Streaming, One pixel Color Camera, CS and RTE, a request, Multi-Label Prediction via CS, Blind reconstruction,

First off Congrats to Ramesh Raskar for his Sloan Fellowship (he is still looking for some folks to join his group). Second, it looks like the compressive sensing workshop is a success but it looks like the coffee person messed with thee tea pot.

Piotr Indyk has a series of lecture he is giving at Rice this spring on the relationship between streaming and compressive sensing. The lectures are here.

From the Rice Compressive Sensing resource site, here is a new paper:


Compressive Imaging of Color Images by Pradeep Nagesh and Baoxin Li. The abstract reads:

In this paper, we propose a novel compressive imaging framework for color images. We first introduce an imaging architecture based on combining the existing single-pixel Compressive Sensing (CS) camera with a Bayer color filter, thereby enabling acquisition of compressive color measurements. Then we propose a novel CS reconstruction algorithm that employs joint sparsity models in simultaneously recovering the R, G, B channels from the compressive measurements. Experiments simulating the imaging and reconstruction procedures demonstrate the feasibility of the proposed idea and the superior quality in reconstruction.

It looks like the RGB encoding could also be useful for smell encoding as well. When are we going to see a compressive sensing nose ? The bayer pattern reminds me of a previous post on retinal cells.

On Friday, March 13, 2009, Hongkai Zhao will give a talk at Stanford on "A fast solver for radiative transport equation and applications in optical imaging". The Abstract reads:

I will present an efficient forward solver for steady-state or frequency-domain radiative transfer equation (RTE) on 2D and 3D structured and unstructured meshes with vacuum boundary condition or reflection boundary condition. Due to high dimensionality the key issue is to construct an efficient iterative scheme that can deal with various behaviors of the solution in different regimes, such as transport, diffusion, optical thick, and forward peaking . In our algorithm we use a direct angular discretization and upwind type of spatial discretization that preserves properties of both scattering and differential operators of RTE. To solve the large linear system after discretization, we construct an efficient iterative scheme based on Gauss-Seidel and proper angular dependent ordering. With this iterative scheme as the relaxation we implement various multigrid methods in both angular and physical space. Our algorithm can deal with different scattering regimes efficiently. Efficiency and accuracy of our algorithm is demonstrated by comparison with both analytical solutions and Monte Carlo solutions, and various numerical tests in optical imaging. Based on this algorithm, a multi-level imaging algorithm is developed for optical tomorgraphy. If time permits, I will also talk about recent work on compressive sensing (CS) in bioluminescence tomography (BLT) based on RTE. We show that direct use of Green's function of RTE as the basis and standard measurement data for reconstruction will not satisfy the restricted isometry property (RIP). We propose an algorithm to transform the standard setup into a new system that satisfies the RIP. Hence, with compressive sensing method, we produce much improved results over standard reconstruction method.

Three items of interest of mine collide here. The RTE or linear transfer equation or Boltzmann equation, compressive sensing and finally the usefulness of RIP. Again running the risk of repeating myself, which I do quite often:The RIP is a sufficient condition, if it does not work out for your problem then maybe you should look at a low order model of your problem and see how it fits into another sufficient (expected to be stricter) condition namely the one calculated in On verifiable sufficient conditions for sparse signal recovery via L1 minimization by Anatoli Juditsky and Arkadi Nemirovski. An implementation is available at this site:

http://sites.google.com/site/testsensingmatrices/

or in Testing the Nullspace Property using Semidefinite Programming by Alexandre d'Aspremont and Laurent El Ghaoui where the NSProp implementation is now available at:

http://www.princeton.edu/~aspremon/NSPcode.htm

Both programs check a condition on a constant \alpha_k. The study of the value of \alpha_k with small matrices could allow one to investigate low order models as well as specific dictionaries.... These two programs are prominently listed in the measurement matrix section of the Big Picture.

In math at UAH, there will be a talk on Compressive Sampling by Brian Robinson, Center for Applied Optics, UA Huntsville, February 27, 2009, 219 Shelby Center, 3:00 (Refreshements at 2:30). The abstract of his talk is:

Conventional sampling is ruled by the Whittaker-Shannon Theorem, which states that, in order to faithfully recover a signal from a set of discrete samples, the samples must be taken with a frequency (the Nyquist frequency) which is twice the highest frequency present in the original signal. Under this regime, the sampling function is the classical comb function, consisting of a train of delta functions equally spaced with a period that is the reciprocal of twice the highest frequency in the signal. This principle underlies nearly all signal sampling protocols used in contemporary electronic devices. As it turns out, however, this method of sampling is not optimal. In other words, there are other methods that require far fewer samples than sampling with the canonical "spike" basis of W-S theory. Compressed Sensing (CS) is a novel sensing/sampling paradigm that goes against the common wisdom in data acquisition in that it demonstrates the feasibility of reconstructing data sets to a high degree of fidelity (and even exactly), with far fewer samples than is required by the W-S sampling paradigm. It is important to note that the methods are also robust to noise. CS relies on two related phenomena to make this possible: sparseness and incoherence. The properties of CS were largely discovered by applied mathematicians working in the field of probability theory and it has profound implications for practical systems such as optical imaging systems. In this talk we will illuminate the ideas of CS theory, discuss the roles of sparseness and incoherence, talk about the relationship that randomness plays in constructing a suitable set of sensing waveforms, and talk about the practical applications of this theory to modern sensing systems.

I got a request recently and the reason I am posting it is because I believe that many would be beginners have exactly the same question:

I have problems on how to calculate the coherence of CS, especially on sampling partial fouier coefficients and renconstruct the image in wavelet domain. This problem is specific for sparse MRI.

argmin ||x|| s.t. y=phi*F*psi*x

This equation is for noise-free MRI.

psi is the sparsifying transform,e.g.wavelet, F is the fourier operator, phi is the random sampling mask in MRI. Often, we acquire the raw data in MRI scanner according to phi.*mask.

For a normal MRI image with size 512*512,

My problems are:

1. Dictionary of visible basis of 2D wavelet or 2D fourier are very large, since each basis is equal to the size of image 512*512, which is 262144 as a long column, I do not think it is possible to construct the wavelet basis W and fourier basis F directly. Do you have any comments on this ? I am considering the @operator in matlab.

2. For sparse MRI, A=phi*F*psi, am I right ?

I am puzzled on the questions for a lot time and read related literatures many times.

Could you provide me some help on this? Did you collect the code for caculating the coherence for large data.

To what I responded:

You really need to look at Sparco, in particular the different set of problems solved for guidance:

http://www.cs.ubc.ca/labs/scl/sparco/index.php/Main/Problems

for every examples, there is the attendant code such as problem 503

http://www.cs.ubc.ca/labs/scl/sparco/index.php/Main/problem503.html

In any event, I think that yes, you will need the @operator to implement your wavelet basis unless there is an example in the sparco suite that does better.

From arxiv, John Langford has followed on his thoughts on error correcting codes (see his first comment when I guest blogged on his blog). The paper is Multi-Label Prediction via Compressed Sensing by Daniel Hsu, Sham Kakade, John Langford, Tong Zhang. The abstract reads:

We consider multi-label prediction problems with large output spaces under the assumption of output sparsity -- that the target vectors have small support. We develop a general theory for a variant of the popular ECOC (error correcting output code) scheme, based on ideas from compressed sensing for exploiting this sparsity. The method can be regarded as a simple reduction from multi-label regression problems to binary regression problems. It is shown that the number of subproblems need only be logarithmic in the total number of label values, making this approach radically more efficient than others. We also state and prove performance guarantees for this method, and test it empirically.

In a different direction, not specifically related to CS but hinting on ways to do a better job of calibrating a Random lens Imager here is a paper by Kyle Herrity, Raviv Raich and Alfred Hero, entitled Blind reconstruction of sparse images with unknown point spread function. The abstract reads:

We consider the image reconstruction problem when the original image is assumed to be sparse and when partial knowledge of the point spread function (PSF) is available. In particular, we are interested in recovering the magnetization density given magnetic resonance force microscopy (MRFM) data, and we present an iterative alternating minimization algorithm (AM) to solve this problem. A smoothing penalty is introduced on allowable PSFs to improve the reconstruction. Simulations demonstrate its performance in reconstructing both the image and unknown point spread function. In addition, we develop an optimization transfer approach to solving a total variation (TV) blind deconvolution algorithm presented in a paper by Chan and Wong. We compare the performance of the AM algorithm to the blind TV algorithm as well as to a TV based majorization-minimization algorithm developed by Figueiredo et al.

We don't many non-linear results but this is one: Sparse Regularization with lq Penalty Term by Markus Grasmair, Markus Haltmeier and Otmar Scherzer. The abstract reads:

We consider the stable approximation of sparse solutions to non-linear operator equations by means of Tikhonov regularization with a subquadratic penalty term. Imposing certain assumptions, which for a linear operator are equivalent to the standard range condition, we derive the usual convergence rate O(sqrt(\delta) of the regularized solutions in dependence of the noise level \delta Particular emphasis lies on the case, where the true solution is known to have a sparse representation in a given basis. In this case, if the differential of the operator satisfies a certain injectivity condition, we can show that the actual convergence rate improves up to O(\delta).

Credit photo : me and using affine matching with ASIFT ( http://mw.cmla.ens-cachan.fr/megawave/demo/asift ) to show the correspondance between two pictures translated from one another.

CS: ExCoV: Expansion-Compression Variance-component Based Sparse-signal Reconstruction, CS approach to time-frequency localization

Kun Qiu a reader of this blog, just let me know of the availability of an upcoming conference paper entitled:



ExCoV: Expansion-Compression Variance-component Based Sparse-signal Reconstruction from Noisy Measurements by Aleksandar Dogandžić and Kun Qiu. The abstract reads:

We present an expansion-compression variance component based method (ExCoV) for reconstructing sparse or compressible signals from noisy measurements. The measurements follow an underdetermined linear model, with noise covariance matrix known up to a constant. To impose sparse or compressible signal structure, we define high- and low-signal coefficients, where each high-signal coefficient is assigned its own variance, low-signal coefficients are assigned a common variance, and all the variance components are unknown. Our expansion-compression scheme approximately maximizes a generalized maximum likelihood (GML) criterion, providing an approximate GML estimate of the high-signal coefficient set and an empirical Bayesian estimate of the signal coefficients.We apply the proposed method to reconstruct signals from compressive samples, compare it with existing approaches, and demonstrate its performance via numerical simulations.

The authors have also made a webpage hosting the ExCoV implementation. It is listed in the reconstruction section of the Big Picture.

I recently talked about a seminar by Patrick Flandrin earlier but as Pierre Borgnat mentioned to me it was postponed until March 5th, 2009 at 11 am at the SCAM (Séminaire Cristolien d'Analyse Multifractale, Université de Paris 12--Val-de-Marne, salle : P3-036) . The title of the talk is: Une approche "compressed sensing" pour la localisation temps-fréquence ( or Time-frequency localization from sparsity constraints) The summary in English is:

In the case of multicomponent AM-FM signals, the idealized representation which consists of weighted trajectories on the time-frequency (TF) plane, is intrinsically sparse. Recent advances in optimal recovery from sparsity constraints thus suggest to revisit the issue of TF localization by exploiting sparsity, as adapted to the specific context of (quadratic) TF distributions. Based on classical results in TF analysis, it is argued that the relevant information is mostly concentrated in a restricted subset of Fourier coefficients of the Wigner-Ville distribution neighbouring the origin of the ambiguity plane. Using this incomplete information as the primary constraint, the desired distribution follows as the minimum $\ell_1$-norm solution in the transformed TF domain. Possibilities and limitations of the approach are demonstrated via controlled numerical experiments, its performance is assessed in various configurations and the results are compared with standard techniques. It is shown that improved representations can be obtained, though at a computational cost which is significantly increased.

The initial paper on which this presentation is based on can be found here.

CS: Open coffee talk questions, SpaRSA on the GPU, Dequantizing Compressed Sensing (ct'd)

. Round Trip Flight to Durham, NC: $ 996.57
. Two nights at the Washington Duke Inn and Golf Club: $274.23
. Attending the Compressive Sensing Workshop: $250
. Enjoying like minded folks while reading Nuit Blanche at the coffee breaks: Priceless.

While a lot of you are in the same room, here are a set of questions that might deserve some attention. Some of you may want to talk amongst yourselves on these issues.

In a recent NA-Digest, Jack Dongarra mentioned the following:

From: Jack Dongarra
Date: Mon, 9 Feb 2009 14:05:55 -0500
Subject: Linear algebra software survey request

We are planning to update the survey of freely available software for the solution of linear algebra problems. The September 2006 version of the survey can be found at: http://www.netlib.org/utk/people/JackDongarra/la-sw.html.

The aim is to put in “one place” the source code that is freely available for
solving problems in numerical linear algebra, specifically dense, sparse direct and iterative systems and sparse iterative eigenvalue problems. Please send me updates and corrections. I will post a note on the na-digest when the new list is available.
Thanks,
Jack

It turns out that in CS, linear algebra problems are being solved but it seems to me that we have not collectively connected to the older and successful LAPACK community. Maybe we should or ...maybe not. Jack responded to my request of the inclusion of a list of the current CS solvers by a "a bit too far afield" response. I agree but as in all disruptive technologies, it is just a question of time before we overtake the entire field of linear algebra :) . On the other hand should we also have a similar table such as this one on top of the mere listing given in the big picture ? and if so, what should the columns be ? (your thoughts are welcomed in the comment section that I will synthesize later).

In a different area, I was asked recently about a set of benchmark against which a solver could be confronted to. I mentioned the set of problems listed in the SPARCO suite. Should we have more of these problems in this set ? Could we get some of the hardware folks to provide different series of measurements to this set of benchmark?

With regards to the stats of this blog, every entry is seen through Google reader by 174 people and through Feedburner by about 94 people. The hit count directly to the blog amount to about 300 per day while about 66 people receive every entry directly in their mailboxes. The Compressive Sensing Study Group on Linkedin now has 105 members.

Following up on the entry on sunday, I talked to Arkadi Nemirovski, who updated his site where there are now two versions of the algorithm implemented in On verifiable sufficient conditions for sparse signal recovery via L1 minimization by Anatoli Juditsky and Arkadi Nemirovski. They are available at this site:

http://sites.google.com/site/testsensingmatrices/

It complements well the other paper entitled Testing the Nullspace Property using Semidefinite Programming by Alexandre d'Aspremont and Laurent El Ghaoui where the NSProp implementation is now available at:

http://www.princeton.edu/~aspremon/NSPcode.htm

As I said earlier, these two implementations may be game changers in that they might replace the traditional reliance on the restricted isometry property (RIP). Both programs check a condition on a constant \alpha_k. The study of the value of \alpha_k with small matrices could allow one to investigate low order models as well as specific dictionaries.... These two programs are prominently listed in the measurement matrix section of the Big Picture.

A month ago, I mentioned the release of an implementation of the SpaRSA algorithm. It looks like it can even go faster now thanks to Sangkyun Lee and Stephen Wright who implemented it on the GPU and released the implementation on this site. From that page:

Implementing Algorithms for Signal and Image Reconstruction on Graphical Processing Units, submitted, 2008.


This site contains GPU codes for compressed sensing and image denoising/deblurring:

• In compressed sensing, we implemented a simple version of the SpaRSA algorithm described by Wright, Nowak, and Figueiredo [1], using randomly chosen rows of discrete cosine transform (DCT) matrix as the sensing matrix.
• In image denoising/deblurring, we implemented the PDHG algorithm of Zhu and Chen [2], which solves the Rudin-Osher-Fatemi formulation with total variation regularization.

All GPU codes compile into Matlab mex binaries, so users can process data and pass them to our GPU routines in Matlab. Our GPU codes require CUDA-enabled GPUs from NVIDIA.

I have added this page to the Compressive Sensing Hardware page. Let us also note the SpaRSA matlab implementation is now at version 2.0.

Yesterday, I featured Dequantizing Compressed Sensing with Non-Gaussian Constraints by Laurent Jacques, David Hammond, and M. Jalal Fadili and followed up with one of those usual dumb questions to Laurent:

How does your solver compared to the one studied by Petros Boufounos and Richard Baraniuk in the 1-Bit Compressive Sensing paper ?

The short answer was:

We haven't tested yet BPDQ on this particular extreme coding.

Laurent also provided a somewhat longer answer:

But let me explain what is similar and different with Petros and Rich's method:

Let x be a signal (sparse or compressible) and let Phi be a Gaussian random sensing matrix.

In the 1-bit compressed sensing model of the paper of Petros Boufounos and Richard Baraniuk, only the sign of (Phi x) is known at the decoder. They propose then to reconstruct the signal by altering the common Basis Pursuit program in two aspects. First, they replace the fidelity term by a Quantization Consistency (QC) term, i.e. the fact that the sign of the remeasured signal candidate must provide the same measurement vector. Second, since the amplitude of the signal is lost in the sign operation, they propose to realize the BP minimization on the sphere of unit norm signals to avoid a vanishing solution. This leads however to a non-convex spherical constraint. They finally solve practically the program by first regularizing the problem on a smoothed version of the QC constraint, and second by running a projected gradient minimization to force to problem to stay on the sphere.
This method was the first attempt to really introduce the QC constraint into the Compressed Sensing formalism, while other methods relied on handling the quantization distortion on the measurements as a common noise in the Basis Pursuit DeNoise (BPDN) program. In the end, the experimental results provided by this 1-Bit CS decoder were interesting compared to the common BPDN treatment with a gain of several dBs.

Our research improves this first approach on a couple of points. First, we wanted to bring a solution for any number of bits (from 1 to many), i.e. any quantization bin width for a uniform quantization model. Second, our decoder had to be closer to the Quantization Consistency, i.e. the fact that requantizing the measurement of the reconstructed signal has to reproduce the known quantized measurement vector. Third, we desired convex constraints so that we could solve it by the versatile techniques of proximal methods and monotone operator splitting (the Douglas Rachford splitting for our case). And finally, our decoder had to be controlled by the theory, i.e. we wanted to bound the approximation error committed by the quantization noise and by possible deviation from the exactly sparse signal model, i.e. the signal compressibility, as it was already existing for the BPDN decoder.

This is why we introduced these Basis Pursuit DeQuantizer (BPDQ) of moment p for p\ge 2. In their foundations, they are adapted to signal reconstruction from measurement vector corrupted by any noise of bounded \ell_p norm since this norm replace the \ell_2 norm used in the BPDN fidelity term. Let me insist on the fact that we are not touching to the sparsity term that is still expressed in the \ell_1 norm as before. The programs BPDQ_p are really introduced to answer to one question: what is a good fidelity term adapted to a non-gaussian noise, as it is the case of the uniform quantization noise. I want to avoid any confusion with other (important but unconnected) research where the \ell_1 sparsity term is replaced by the \ell_q non-convex norm (with q \le 1).

Interestingly, if the sensing matrix satisfies a generalized Restricted Isometry Property of moment p, i.e. a RIP variant bounding the \ell_p norm (p \ge 2) of the random projection of sparse signals (a property that is also satisfied by Gaussian random matrices with high probability), the BPDQ decoders have the desired stability behaviour, i.e. the "instance optimality".

In addition, for noise due to uniform quantization of measurements, we observe an interesting effect. When we work in oversampled situation where the number m of measurements is much higher than required to have the RIP_p, the part of the BPDQ approximation error due to the quantization noise is divided by \sqrt{p+1}. Therfore, when allowed, increasing the moment p thus decreases the approximation error! This is for us really the indication that the quantization noise is handled more faithfully.

To come back to the initial comparison with the 1-bit compressed sensing of Petros Boufounos and Richard Baraniuk, their proposed method is very close to our BPDQ when p=infinity. Indeed, 1-bit quantization consists also in taking the bin width equal the sup-norm of Phi x. The fidelity term for p=infinity induces then the previous sign constraint. Notice that we do not have to work on the unit signal sphere since we add the knowledge of alpha in the coding/decoding scenario. I'm quite sure therefore that in the extreme 1-bit regime our BPDQ for p=infinity will produce results comparable to those of the initial 1-bit CS decoder. However, in oversampled situations, i.e. when m is high, the moment p can be chosen large (making the \ell_p constraint very close to the \ell_infinity one), and our decoders provides theoretically and experimentally decreasing approximation error by working closer to the Quantization Consistency.

Thank you Laurent!

Credit photo: me. That day was cold!

CS: Dequantizing Compressed Sensing with Non-Gaussian Constraints, A request for Collaboration.

Laurent Jacques just let me know of a paper and companion technical report on CS and the quantization of measurements. Here they are:

Dequantizing Compressed Sensing with Non-Gaussian Constraints by Laurent Jacques, David Hammond, and M. Jalal Fadili

In this paper, following the Compressed Sensing paradigm, we study the problem of recovering sparse or compressible signals from uniformly quantized measurements. We present a new class of convex optimization programs, or decoders, coined Basis Pursuit DeQuantizer of moment p (BPDQp), that model the quantization distortion more faithfully than the commonly used Basis Pursuit DeNoise (BPDN) program. Our decoders proceed by minimizing the sparsity of the signal to be reconstructed while enforcing a data fidelity term of bounded l_p-norm, for 2 \lt p \le \infty. We show that in oversampled situations the performance of the BPDQp decoders are significantly better than that of BPDN, with reconstruction error due to quantization divided by sqrt(p + 1). This reduction relies on a modified Restricted Isometry Property of the sensing matrix expressed in the l_p-norm (RIP_p); a property satisfied by Gaussian random matrices with high probability. We conclude with numerical experiments comparing BPDQp and BPDN for signal and image reconstruction problems.

and the attendant technical report: Dequantizing Compressed Sensing: When Oversampling and Non-Gaussian Constraints Combine by Laurent Jacques, David Hammond, and M. Jalal Fadili

After inquiring on the subject, David Hammond also let me know that:

We are planning on releasing the BPDQ solver code upon acceptance of a journal paper; so the time is unclear.

In a different direction, Brien Housand sent the following request on both this blog and the linkedin group discussion forum:

Seeking partner from Academic or non-profit research institute for multi-spectral Compressive Sensing project – paper study. Combine your knowledge of Compressive Sensing algorithms with our skills at Electro-Optical sensor design.

Contact: Brien Housand
Email: bhousand@dsci.com

After 6 months since its inception, the Compressive Sensing Study Group on LinkedIn now has 100 members.

Credit photo: me. A view of Geneva and the Mont-Blanc mountain.

CS: Testing the Nullspace Property using Semidefinite Programming and attendant NSProp code.

In a recent entry, I mentioned the utmost importance of this subject: How can one find if a given rectangular measurement or multiplexing matrix has the property of allowing recoverability of sparse signals or unknowns. Most papers are currently using the convenient Restricted Isometry Property but it is thought that this is an unnecessarily tight property. Alexandre d'Aspremont and Laurent El Ghaoui have now updated to version 3 their preprint entitled: Testing the Nullspace Property using Semidefinite Programming. Because it is important work for the whole field, I am pasting the abstract again:

Recent results in compressed sensing show that, under certain conditions, the sparsest solution to an underdetermined set of linear equations can be recovered by solving a linear program. These results rely on nullspace properties of the system matrix. So far, no tractable algorithm is known to test these conditions and most current results rely on asymptotic properties of sparse eigenvalues of random matrices. Given a matrix A, we use semidefinite relaxation techniques to test the nullspace property on A and show on some numerical examples that these relaxation bounds can prove perfect recovery of sparse solutions with relatively high cardinality.

As I had mentioned earlier, the reason for Version 3 is because (as mentioned in the arxiv page):

The J&N code in the last version did not run to full precision. This version thus includes updated (and significantly different) numerical results comparing both LP and SDP relaxations. Numerical results on the randomization lower bound were also added

What is also noteworthy and wasn't available in previous versions of the draft is the attendant code. The NSProp implementation is now available here:

http://www.princeton.edu/~aspremon/NSPcode.htm

Oustanding! Now let me point to the conclusion of the paper:

We have detailed a semidefinite relaxation for the problem of testing if a matrix satisfies the nullspace property defined in Cohen et al. (2006). This relaxation matches the linear programming relaxation in Juditsky and Nemirovski (2008) when k = 1 but is not as tight for larger values of k. On the other hand, it also produces a tractable lower bound on the objective value which does not require solving a (potentially exponentially long) sequence of convex optimization problems as in Juditsky and Nemirovski (2008). In particular, our results prove that both LP and SDP relaxations on α1 are tight for the Gaussian and Bernoulli matrices tested here. We can also remark that the matrix A only appears in the relaxation (9) in “kernel” format A^T A, where the constraints are linear in the kernel matrix A^T A. This means that this relaxation might allow sparse experiment design problems to be solved, while maintaining convexity. Of course, these small scale experiments do not really shed light on the actual performance of both relaxations on larger, more realistic problems. In particular, applications in imaging and signal processing would require solving problems where both n and k are several orders of magnitude larger than the values considered in this paper or in Juditsky and Nemirovski (2008) and the question of finding tractable relaxations or algorithms that can handle such problem sizes remains open. Also, while empirical evidence suggests that our relaxation is quite tight for certain types of random matrices (and that it matches the LP relaxation on α1, which achieves order √k for matrices satisfying the restricted isometry property at order k), we could not, at this point, produce explicit bounds on the recovery threshold of this semidefinite relaxation.

I realize that more realistic problems might be out of reach because of time constraints, but then again, I believe it is just a question of time that we either have a theoretical breakthrough in this area or we have more powerful tricks and machinery to compute this bound in a short amount of time for large rectrangular matrices. For those of you who just find out about this subject, you may to check my previous entry on this issue. On that subject, I am still looking to the re-availability of the J&N code.

CSJob: Compressed sensing theory and algorithms with particular application to dynamic MRI

Mike Davies just let me know of the following at the University of Edinburgh:

We have another job vacancy for a research fellow in compressed sensing!

Research Fellow in "Compressed sensing theory and algorithms with particular application to dynamic MRI"

It has been added to the Compressive Sensing jobs section.

CS: Compressive Light Transport Sensing

Let's take a look at a very noteworthy contribution as it clearly has impact on solving the linear transport equation (an interest of mine).

Here is a new paper entitled Compressive Light Transport Sensing ( a previous technical report can be found on this site) by Pieter Peers, Dhruv Mahajan, Bruce Lamond, Abhijeet Ghosh, Wojciech Matusik and Ravi Ramamoorthi. The abstract reads:

In this article we propose a new framework for capturing light transport data of a real scene, based on the recently developed theory of compressive sensing. Compressive sensing offers a solid mathematical framework to infer a sparse signal from a limited number of nonadaptive measurements. Besides introducing compressive sensing for fast acquisition of light transport to computer graphics, we develop several innovations that address specific challenges for image-based relighting, and which may have broader implications. We develop a novel hierarchical decoding algorithm that improves reconstruction quality by exploiting interpixel coherency relations. Additionally, we design new nonadaptive illumination patterns that minimize measurement noise and further improve reconstruction quality. We illustrate our framework by capturing detailed high-resolution reflectance fields for image-based relighting.

The teaser photo shown above has the following caption:

Three scenes captured using only 1000 non-adaptive compressive measurements, and relit using a novel conditions. The 128x128 reflectance functions of each camera pixel is reconstructed using our hierarhical reconstruction algorithm using 128 Haar wavelet coefficients per function from the observed compressive measurements.

This is outstanding.

CS: Simple Deterministically Constructible RIP Matrices with Sublinear Fourier Sampling Requirements

That is interesting! Simple Deterministically Constructible RIP Matrices with Sublinear Fourier Sampling Requirements by Mark Iwen. The abstract reads:

We present a deterministic number theoretic construction for matrices with the Restricted Isometry Property (RIP). Furthermore, we show that the number theoretic properties of our RIP matrices allow their products with Discrete Fourier Transform (DFT) matrices to be well approximated via a few highly sparse matrix multiplications. Hence, our RIP matrices may be approximately multiplied by the DFT of any input vector in sublinear-time by reading only a small fraction of its entries. As a consequence, we obtain small deterministic sample sets which are guaranteed to allow the recovery of near-optimal sparse Fourier representations for all periodic functions having an integrable second derivative over a single period. Explicit bounds are provided for the sizes of our RIP matrices, the sizes of their associated sublinear Fourier sampling sets, and the errors incurred by quickly approximating their products with DFT matrices. The Fourier sampling requirements obtained herein improve on previous deterministic Fourier sampling results in [1], [2].

CS: Rice Compressive Sensing website facelift, Change in addresses links on the Rice Site.

Mark Davenport just let me know that the Rice Compressive Sensing page has gotten a facelift and they are now using a Content Management System that allows them to boost their ability to make available the different preprints in the field. This is great. I can certainly empathize with a more systematic way to do this. A minor side effect of this migration affects the Nuit Blanche links to preprints hosted on their site. If you surf on their site, you will notice nothing,. However, if you click on a link listed here on this blog with a preprint hosted at the Rice site, then you will likely get an error. No biggie, you just need to change a little bit the address. As Mark points out:

However, the one unfortunate byproduct is that the URL for all of the papers that were actually hosted on our site has changed from

http://dsp.rice.edu/cs/papername.pdf

to

http://dsp.rice.edu/files/cs/papername.pdf

I realize this is a huge annoyance - but I just thought that I would let you know since you probably have linked to papers hosted on our site in the past, and hence those links will now go dead. I tried to keep the papers where they were, but there was just no way to get our CMS to let us both put a directory of files at the url "cs" and keep our page located at the same spot.

Thanks Mark!. I don't think the blog will be affected that much. For one, I generally link to preprints listed on the authors' pages. I also link to the other known authors so that eventually the preprints are also likely to be found on the other authors' site. This is one of the reason I keep on insisting that students (yes even undergraduates) should have their own site independent of their universities. For those of you considering this, please check the Sherpa/Romeo, Publisher copyright policies & self-archiving database to make sure of the documents you can archive on your site. To finish this note, (via this blog) and borrowing from John Baez-comment, ending a thread on the n-category cafe’s popularity starting here.

“Anyway, it’s clear we have masses of followers. Now it’s time to take over the world.”

CS:Unified Approach to Sparse Signal Processing, Using the IHT Algo, Optimal CS Algo,CfP Signal Processing, Stephen's Boyd Class on Youtube, SODA

I'll be in a place where The Google and the Interwebs have trouble reaching people. So this may look like a long post but I have not written any more post to be published later this week.

From Arxiv we have: A Unified Approach to Sparse Signal Processing by Farokh Marvasti, A. Amini, F. Haddadi, Mahdi Soltanolkotabi, Babak Khalaj, Akram Aldroubi, Sverre Holm, Saeid Sanei, Jonathon Chambers. The abstract reads:

A unified view of sparse signal processing is presented in tutorial form by bringing together various fields. For each of these fields, various algorithms and techniques, which have been developed to leverage sparsity, are described succinctly. The common benefits of significant reduction in sampling rate and processing manipulations are revealed. The key applications of sparse signal processing are sampling, coding, spectral estimation, array processing, component analysis, and multipath channel estimation. In terms of reconstruction algorithms, linkages are made with random sampling, compressed sensing and rate of innovation. The redundancy introduced by channel coding in finite/real Galois fields is then related to sampling with similar reconstruction algorithms. The methods of Prony, Pisarenko, and MUSIC are next discussed for sparse frequency domain representations. Specifically, the relations of the approach of Prony to an annihilating filter and Error Locator Polynomials in coding are emphasized; the Pisarenko and MUSIC methods are further improvements of the Prony method. Such spectral estimation methods is then related to multi-source location and DOA estimation in array processing. The notions of sparse array beamforming and sparse sensor networks are also introduced. Sparsity in unobservable source signals is also shown to facilitate source separation in SCA; the algorithms developed in this area are also widely used in compressed sensing. Finally, the multipath channel estimation problem is shown to have a sparse formulation; algorithms similar to sampling and coding are used to estimate OFDM channels.

Supporting the Sparsify recent Version 0.4, here are two papers:

How To Use The Iterated Hard Thresholding Algorithm by Thomas Blumensath and Mike Davies. The abstract reads:

Several computationally efficient algorithms have been shown to offer near optimal recovery of sparse signals from a small number of linear measurements. However, whilst many of the methods have similar guarantees whenever the measurements satisfy the so called restricted isometry property, empirical performance of the methods can vary significantly in a regime in which this condition is not satisfied. We here modify the Iterative Hard Thresholding algorithm by including an automatic step-size calculation. This makes the method independent from an arbitrary scaling of the measurement system and leads to a method that shows state of the art empirical performance. What is more, theoretical guarantees derived for the unmodified algorithm carry over to the new method with only minor changes.

A Simple, Efficient and Near Optimal Algorithm for Compressed Sensing by Thomas Blumensath and Mike Davies. The abstract reads:

When sampling signals below the Nyquist rate, efficient and accurate reconstruction is nevertheless possible, whenever the sampling system is well behaved and the signal is well approximated by a sparse vector. This statement has been formalised in the recently developed theory of compressed sensing, which developed conditions on the sampling system and proved the performance of several efficient algorithms for signal reconstruction under these conditions. In this paper, we prove that a very simple and efficient algorithm, known as Iterative Hard Thresholding, has near optimal performance guarantees rivalling those derived for other state of the art approaches.

Laurent Duval just let me know of a new Call for Papers:

Call for papers Special issue on Advances in Multirate Filter Bank Structures and Multiscale Representations
Scope
A century after the first outbreak of wavelets in Alfred Haar’s thesis in 1909, and twenty years after the advent of Multiresolution Analysis, filter banks and wavelet transforms lie at the heart of many digital signal processing and communication systems. During the last thirty years, they have been the focus of tremendous theoretical advances and practical applications in a growing digital world. They are for instance present, as local linear expansions, at the core of many existing or forthcoming audio, image or video compression algorithms. Beyond standards, many exciting developments have emerged in filter banks and wavelets from the confrontation between scientists from different fields (including signal and image processing, computer science, harmonic analysis, approximation theory, statistics, bioengineering, physics). At their confluence, multiscale representations of data, associated with their efficient processing in a multirate manner, have unveiled tools or refreshed methods impacting the whole data management process, from acquisition to interpretation, through communications, recovery and visualization. Multirate structures naturally shelter key concepts such as the duality between redundancy and sparsity, as well as means for extracting low dimensional structures from higher ones. In image processing in particular, various extensions of wavelets provide smart linear tools for building insightful geometrical representations of natural images. The purpose of this special issue is to report on recent progresses performed and emerging trends in the domain of multirate filter banks and multiscale representations of signals and images. Answers to the challenge of handling an increasing demand of information extraction and processing from large data sets will be explored.
Topics (not exclusive)

• Sampling theory, compressive sensing
  
• Sparse representations
  
• Multiscale models
• Multiscale processing: interpolation, inpainting, restoration,
• Wavelet shrinkage and denoising
• Oversampled filter banks, discrete frames
• Rational and non-uniform multirate systems
• Directional, steerable filter banks and wavelets
• Nonlinear filter banks
• (Multidimensional) filter bank design and optimization
• Hybrid analog/digital filter banks
• Fast and low-power schemes (lifting, integer design)
• Multiscale and multirate applications to source and channel coding, equalization, adaptive filtering, ....

Important dates:

• Deadline for submission: 15 December 2009
  
• First round of reviews/decisions: 1 April 2010
  
• Resubmission of revised papers: 1 July 2010
  

Submission
Guidelines for authors can be found at http://www.elsevier.com/locate/sigpro. Authors should submit their manuscripts before the submission deadline via http://ees.elsevier.com/sigpro/ selecting ‘‘Special Issue: Multirate/Multiscale’’ as Article Type.

I already knew of the Stephen Boyd's class on Youtube such as this one:

What I did not realize was that somebody had gone through the pain of transcribing these videos. Wow, just Wow. For instance the text of the video above is found here. The rest of Stephen Boyd's excellent class can be found here and here with the attendant text.

The Papers presented at SODA are now available. Among the ones, I am surely going to be reading (after some advice from Frank Nielsen that I should know about Coresets)

• The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite by William B. Johnson and Assaf Naor.
• Constructing Laplace Operator from Point Clouds in Rd by Mikhail Belkin, Jian Sun, Yusu Wang.
• Coresets and Approximate Clustering for Bregman Divergences by Marcel R. Ackermann and Johannes Blomer.
• Overcoming the l_1 Non-Embeddability Barrier:Algorithms for Product Metrics by Alexandr Andoni, Piotr Indyk, Robert Krauthgamer.

Over at the CAVE lab at Columbia, they just released the title of an intriguing technical report entitled "Generalized Assorted Pixel Camera: Post-Capture Control of Resolution, Dynamic Range and Spectrum," by F. Yasuma, T. Mitsunaga, D. Iso, and S.K. Nayar. Yet the pdf link does not seem to work for the moment.

Also of interest is theASPLOS 2008 Tutorial : CUDA: A Heterogeneous Parallel Programming Model for Manycore Computing blog entry.

In a different area, Shenzou VII passed by the International Space Station, here is a simulation by the folks at AGI. In a different area, I look forward to seeing how the recent collision between an Iridium satellite and a Russian satellite will disturb that low earth orbit environment with space debris. To see how bad this collision is, you need to check out the calculations on the Bad Astronomy blog. Have you ever been rearsided by something at 17,000 mph ? Let us recall that we are really close to a prompt critical situation in this area and this is worrisome as most of our daily lives depends on Satellites these days.