You keep using that word. I do not think it means what you think it means.

Tomorrow's photos reminded me of yet another entry on the same subject.

Credit for the title of this entry: Imdb, script of the Princess Bride.

CS: The Restricted Isometry Property and l_q-Regularization: Phase transition for Sparse Approximation, Decay Properties of RIC

Here are two much expected analyses,I am sure I'll come back to these later:

The Restricted Isometry Property and l_q-Regularization: Phase transition for Sparse Approximation by Jeffery Blanchard, Coralia Cartis, and Jared Tanner. The abstract reads:

Consider a measurement matrix A of size n×N, with n less than N, y a signal in R^N, and b = Ay the observed measurement of the vector y. From knowledge of (b,A), compressed sensing seeks to recover the k-sparse x, k less than n, which minimizes ||b − Ax||. Using various methods of analysis — convex polytopes, geometric functional analysis, and the restricted isometry property (RIP) — it has been proven that x can be reconstructed via l_q-regularization (q element of (0, 1]) provided A satisfies conditions dictated by the method of analysis. This article focuses on the RIP approach and A with entries drawn i.i.d. from the Gaussian distribution N(0, 1/sqrt(n)), developing more precise bounds on the restricted isometry constants, and using these bounds in an asymmetric RIP formulation to quantify the region of ( n/N , k/n ) in which RIP implies that l_q-regularization will typically recover all k-sparse signals. Letting n/N go to \delta and k/n go to \rho as n go to \infinity, the aforementioned recoverability region is characterized by all \rho lss than < (1 − \epsilon)rho^RIP_S (\delta; q) for any epsilon above 0, where rho^RIP_S (\delta; q) is a lower bound of the true phase transition below which l_q-regularization will typically recover all k-sparse signals. This phase transition framework, proposed in this context by Donoho (2005), is applied to compressed sensing results obtained by the analysis techniques of centro-symmetric polytope theory (Donoho), geometric functional analysis (Rudelson and Vershynin), and the RIP (Candes, Romberg and Tao; Foucart and Lai; Chartrand). Recasting the results from different methods of analysis into a common phase transition framework allows for the direct comparison of the efficacy of the respective results.

and Decay Properties of Restricted Isometry Constants by Jeffery Blanchard, Coralia Cartis, and Jared Tanner. The abstact reads:

The restricted isometry property (RIP) is an important technique of analysis in sparse approximation. Many sparse approximation algorithms accurately capture the sparsest solution provided the restricted isometry constants satisfy certain bounds. There are no known sufficiently large deterministic matrices that satisfy the desired RIP bounds; however, many random matrix ensembles satisfy RIP bounds with high probability on the draw of the matrix. Here we construct matrices whose RIP constants behave in a markedly different fashion from those of classical random matrix ensembles. In particular, the RIP constants can satisfy desirable bounds and also take on values in a narrow range.

Image Credit: NASA/JPL/Space Science Institute, image of Saturn taken on January 23, 2009

CS: Automatic Code Generation for Real-Time Convex Optimization, OFDM Channel Estimation, rate distortion, Jacket Webinar.

This entry has a "fast" flavor and is sometimes peripherically related to CS:

Automatic Code Generation for Real-Time Convex Optimization by Jacob Mattingley and Stephen Boyd. The abstract reads:

This chapter concerns the use of convex optimization in real-time embedded systems, in areas such as signal processing, automatic control, real-time estimation, real-time resource allocation and decision making, and fast automated trading. By ‘embedded’ we mean that the optimization algorithm is part of a larger, fully automated system, that executes automatically with newly arriving data or changing conditions, and without any human intervention or action. By ‘real-time’ we mean that the optimization algorithm executes much faster than a typical or generic method with a human in the loop, in times measured in milliseconds or microseconds for small and medium size problems, and (a few) seconds for larger problems. In real-time embedded convex optimization the same optimization problem is solved many times, with different data, often with a hard real-time deadline. In this chapter we propose an automatic code generation system for real-time embedded convex optimization. Such a system scans a description of the problem family, and performs much of the analysis and optimization of the algorithm, such as choosing variable orderings used with sparse factorizations and determining storage structures, at code generation time. Compiling the generated source code yields an extremely efficient custom solver for the problem family. We describe a preliminary implementation, built on the Python-based modeling framework CVXMOD, and give some timing results for several examples.

Just found on arxiv:

OFDM Channel Estimation Based on Adaptive Thresholding for Sparse Signal Detection by Mahdi Soltanolkotabi, Arash Amini and Farokh Marvasti. The abstract reads:

Wireless OFDMchannels can be approximated by a time varying filter with sparse time domain taps. Recent achievements in sparse signal processing such as compressed sensing have facilitated the use of sparsity in estimation, which improves the performance significantly. The problem of these sparse-based methods is the need for a stable transformation matrix which is not fulfilled in the current transmission setups. To assist the analog filtering at the receiver, the transmitter leaves some of the subcarriers at both edges of the bandwidth unused which results in an ill-conditioned DFT submatrix. To overcome this difficulty we propose Adaptive Thresholding for Sparse Signal Detection (ATSSD). Simulation results confirm that the proposed method works well in time-invariant and specially time-varying channels where other methods may not work as well.

From the text, one can read:

As a result, linear-programming-based algorithms used in compressed sensing, similar to the ones introduced in [?] can be applied to OFDM channel estimation. However, the authors of [?] did not consider zero-padding at the endpoints of the bandwidth in their scenario, which is an essential part of current OFDMstandards. This assumption, causes the matrix Fp,CP to contradict the Restricted Isometric Property (RIP) defined in [?] and thus the use of Compressive Sensing (CS) algorithms as described in [?], unpractical.

I am not quite sure about this and this is not the first time that such wording is being used. The Restricted Isometry Property is just a sufficient condition. Not fulfilling the RIP, doesn't mean that CS algorithms cannot work.

and On the rate distortion function of Bernoulli Gaussian sequences by Cheng Chang. The abstract reads:

In this paper, we study the rate distortion function of the i.i.d sequence of multiplications of a Bernoulli p random variable and a gaussian random variable = N(0, 1). We use a new technique in the derivation of the lower bound in which we establish the duality between channel coding and lossy source coding in the strong sense. We improve the lower bound on the rate distortion function over the best known lower bound by p log_2 (1/p) if distortion D is small. This has some interesting implications on sparse signals where p is small since the known gap between the lower and upper bound is H(p). This improvement in the lower bound shows that the lower and upper bounds are almost identical for sparse signals with small distortion because lim p 0 plog_2 (1/p)/ H(p) = 1.

Finally, there is a webinar today about jacket:
Jacket: Accelerating MATLAB using CUDA-Enabled GPUs, February 5, 2009, 11am PST / 2pm EST. Are you looking for ways to improve your productivity by accelerating MATLAB functions? Now you can with the unprecedented performance of GPU computing. By attending this webinar, you will learn:

• What is GPU computing
• What is NVIDIA CUDA parallel computing architecture
• What is the Jacket engine for MATLAB from AccelerEyes
• How to get 10x to 50x speed-up for several MATLAB functions

Date: Thursday, February 5, 2009
Time: 11:00am PST / 2:00pm EST
Duration: 45 Minute Presentation, 15 Minute Q&A
Register Here
Presented By: Sumit Gupta, Ph.D., Sr Product Manager of Tesla GPU Computing at NVIDIA and John Melonakos, Ph.D., CEO at AccelerEyes LLC

CS: Beyond Nyquist, Domain decomposition methods for CS, an internship, CS workshop on Youtube and Optical Imaging and Spectroscopy book and blog

Today, we have two papers, an internship offer, some news from Duke and a new blog:

Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals by Joel Tropp, Jason Laska, Marco Duarte, Justin Romberg, and Richard Baraniuk. The abstract reads:

Wideband analog signals push contemporary analog-to-digital conversion systems to their performance limits. In many applications, however, sampling at the Nyquist rate is inefficient, because the signals of interest contain only a small number of significant frequencies relative to the bandlimit, although the locations of the frequencies may not be known a priori. For this type of sparse signal, other sampling strategies are possible. This paper describes a new type of data acquisition system, called a random demodulator, that is constructed from robust, readily available components. Let K denote the total number of frequencies in the signal, and let W denote its bandlimit in Hz. Simulations show that the random demodulator requires just O(K log(W=K)) samples per second to stably reconstruct the signal. This sampling rate is exponentially lower than the Nyquist rate of W Hz. In contrast with Nyquist sampling, one must use nonlinear methods, such as convex programming, to recover the signal from the samples taken by the random demodulator. Finally, the paper provides a theoretical analysis of the system’s performance.

Domain decomposition methods for compressed sensing by Massimo Fornasier, Andreas Langer, Carola-Bibiane Schönlieb. The abstract reads:

We present several domain decomposition algorithms for sequential and parallel minimization of functionals formed by a discrepancy term with respect to data and total variation constraints. The convergence properties of the algorithms are analyzed. We provide several numerical experiments, showing the successful application of the algorithms for the restoration 1D and 2D signals in interpolation/inpainting problems respectively, and in a compressed sensing problem, for recovering piecewise constant medical-type images from partial Fourier ensembles.

Amit Agrawal is looking for interns at MERL this summer: Summer Internship (2009) at Mitsubishi Electric Research Labs (MERL)

Starting May 2009 We are looking for a student with experience and interest in one or more of the following topics Computational Imaging/Photography Active illumination LightFields and Applications Motion Deblurring Coded Aperture Techniques Project details are at http://www.merl.com/people/agrawal/index.html
* The student research background should include computer vision and image processing projects.
* Programming experience in Matlab, C/C++
* The student may also submit his/her own proposal for a research project.
* Competitive pay, fun working environment. Please send email to agrawal at merl dot com with resume, dates of availability and area of interest.

While there is no obvious relation to Compressive Sensing, work like the one performed by Roummel Marcia, Zachary Harmany, and Rebecca Willett in their latest paper entitled Compressive Coded Aperture Imaging should be a clue that much work can expand in that area with CS provinding much solid theoretical underpinnings. I have added this announcement to the Compressive Sensing Jobs list.

Rebecca Willett just mentioned to me that the upcoming Compressive Sensing Workshop will be videoed and is expected to be put on the Youtube channel of the meeting. I need to buy myself some popcorn. If somebody wants to be a reporter for NB, it would be nice if you could also have photos of the numerous posters of the poster session. I'll feature each and every one of them on the blog, promise.

Also from Duke, if you recall I mentioned earlier that David Brady would have a book out in 2009 entitled: Optical Imaging and Spectroscopy. Looks like the book already has an attendant website with Matlab and Mathematica codes for each chapter. Chapter 8 featuring some CS reconstruction. The website is at: http://opticalimaging.org/. More Importantly, the book also has an attendant blog: http://opticalimaging.org/OISblog/


Credit Photo: NASA/JPL/Space Science Institute, Saturn rings taken on February 01, 2009

CS: KGG presentation, Jacket, pystream, a paradigm shift in signal processing, 3D CS for Dynamic MRI

I mentioned her yesterday, but the links were all wrong. So here we are again: Svetlana Avramov-Zamurovic presented a tutorial on Compressive Sensing in a course at the USNA. She also made a video of it. It is here. The slides and attendant paper by Richard Baraniuk on which the presentation is based. It is added to the Compressive Sensing Videos page.

Also found on the interwebs:

Compressive Sensing Theory and L1-Related Optimization Algorithms by Yin Zhang. Of interest is the mention of a recoverability proof without the use of the RIP argument.

A presentation by Albert Cohen entitled Near optimal recovery of arbitrary signals from highly incomplete measurements.

There is a summary of the Frames for the finite world: Sampling, coding and quantization workshop organized by Sinan Gunturk, Goetz Pfander, Holger Rauhut, and Ozgur Yilmaz

Jacket v1.0, a Matlab to GPU software is now available. It's not free but heavily discounted for academics it seems. There is also pystream from the project page:

PyStream combines the power and convenience of Python with the high performance of modern Graphics Processing Units (GPUs). The focus of PyStream is on NVIDIA GPUs, such as the GeForce 8800 and Tesla series, that support the Compute Unified Device Architecture (CUDA) toolkit. With PyStream, the CUDA libraries, including the CUDA BLAS and FFT libraries, can be called from directly from Python. Data can be moved back and forth seamlessly between the GPU and Python objects (NumPy arrays) on the CPU. Initial development of PyStream was done by Tech-X Corporation. Tech-X Corporation has shifted its efforts to a new GPU related project, called GPULib, that has a higher level API than PyStream and also supports other languages other than Python. Because of this change, PyStream is no longer being actively developed. However, PyStream will remain available under the BSD license.

Also found on Arxiv, Compressive sensing: a paradigm shift in signal processing by Olga V. Holtz.

The abstract reads:We survey a new paradigm in signal processing known as "compressive sensing". Contrary to old practices of data acquisition and reconstruction based on the Shannon-Nyquist sampling principle, the new theory shows that it is possible to reconstruct images or signals of scientific interest accurately and even exactly from a number of samples which is far smaller than the desired resolution of the image/signal, e.g., the number of pixels in the image. This new technique draws from results in several fields of mathematics, including algebra, optimization, probability theory, and harmonic analysis. We will discuss some of the key mathematical ideas behind compressive sensing, as well as its implications to other fields: numerical analysis, information theory, theoretical computer science, and engineering.

There is an attendant presentation entitled An Introduction to Compressive Sensing by the same author.

Finally, Three-Dimensional Compressed Sensing for Dynamic MRI by Ali Bilgin, Ted Trouard, Maria Altbach, and Natarajan Raghunand. The introduction reads:

Dynamic contrast enhanced (DCE) magnetic resonance imaging (MRI) is a valuable tool used in a number of clinical applications. However, imaging of time-varying objects is a challenging task when both high spatial resolution and high temporal resolution is desired. It has been demonstrated that radial imaging techniques can yield increased temporal resolution without sacrificing spatial resolution and are less susceptible to motion [1,2]. However, highly undersampled radial trajectories result in increased streaking artifacts and low SNR. The recently introduced Compressed Sensing (CS) theory illustrates that a small number of linear measurements can be sufficient to reconstruct sparse or compressible signals [3,4] and has the potential to significantly accelerate data acquisition in MRI [5,6,7]. In this work, we introduce a CS theory based method for reconstruction of time-varying radial k-space data by exploiting the spatio-temporal sparsity of DCE-MRI images.

Credit: NASA/JPL/Space Science Institute,Saturn's ring taken on January 28th, 2009.

CS: Twitter, Several news and findings, A Non-Iterative Procedure for Undetermined Systems, Molecular imaging, Super-resolution X-ray

For those of who know what this is, I am on Twitter.

Thomas Blumensath sent me a kind e-mail :

As an avid reader of your blog, I thought I clarify the following points raised in one of your previous entries regarding the OLS algorithm.

Firstly, we did not propose the method in our paper. This method has been around with many names and in many guises. Our paper actually gives a good historical overview (which was its main purpose). A better reference for the OLS algorithm would be:

S. Chen, S. A. Billings, and W. Luo, “Orthogonal least squares methods and their application to non-linear system identification.,” International Journal of Control, vol. 50, no. 5, pp. 1873–1896, 1989.

Secondly, I would like to point out that ols is also available in my Sparsify toolbox (greed_ols).

Thanks Thomas for the clarification.


Svetlana Avramov-Zamurovic presented a tutorial on Compressive Sensing in a course at the USNA. She also made a video of it. It is here. The slides and attendant paper by Richard Baraniuk on which the presentation is based. I'll add it to the Compressive Sensing Videos page.

Jort Gemmeke let me know that the schedule and list of presentation of the Compressive Sensing Workshop is now available here. Lots of goodies.

Andryian Suksmono has just released a draft e-book on Compressive Sensing. The mild caveat is that it is in Indonesian. No worry, Google Translate now has Indonesian to English translation services.

Felix J. Herrmann, Yogi Erlangga, Tim Lin have released a new version of Compressive simultaneous full-waveform simulation.

A passing thought: when you hear about an imaging system that is diffraction-limited, you are really hearing that the analog way of combining light rays together to form an image has limits. If you have read the previous entry on compressive phase retrieval featuring Ab Initio Compressive Sensing Phase retrieval by Stefano Marchesini and Compressed Sensing Phase Retrieval by Matthew Moravec, Justin Romberg and Richard Baraniuk, you know by now that every time you hear about an indirect measurement system or have the ability to engineer the PSF (Point Spread Function), it is likely you should be able to use the strength of compressive sensing to perform measurements.

Here are three papers that I think are interesting in different respect:

Sparse image reconstruction for molecular imaging by Michael Ting, Raviv Raichand, Alfred O. Hero III. The abstract reads:

The application that motivates this paper is molecular imaging at the atomic level. When discretized at subatomic distances, the volume is inherently sparse. Noiseless measurements from an imaging technology can be modeled by convolution of the image with the system point spread function (psf). Such is the case with magnetic resonance force microscopy (MRFM), an emerging technology where imaging of an individual tobacco mosaic virus was recently demonstrated with nanometer resolution. We also consider additive white Gaussian noise (AWGN) in the measurements. Many prior works of sparse estimators have focused on the case when H has low coherence; however, the system matrix H in our application is the convolution matrix for the system psf. A typical convolution matrix has high coherence. The paper therefore does not assume a low coherence H. A discrete-continuous form of the Laplacian and atom at zero (LAZE) p.d.f. used by Johnstone and Silverman is formulated, and two sparse estimators derived by maximizing the joint p.d.f. of the observation and image conditioned on the hyperparameters. A thresholding rule that generalizes the hard and soft thresholding rule appears in the course of the derivation. This so-called hybrid thresholding rule, when used in the iterative thresholding framework, gives rise to the hybrid estimator, a generalization of the lasso. Unbiased estimates of the hyperparameters for the lasso and hybrid estimator are obtained via Stein’s unbiased risk estimate (SURE). A numerical study with a Gaussian psf and two sparse images shows that the hybrid estimator outperforms the lasso.

a related (older) presentation can be found in A. O. Hero, R. Raich, and M. Ting, Finding dust in space: localizing atoms from noisy projections.

Here is another interesting and somewhat surprising paper: A Non-Iterative Procedure for Computing Sparse and Sparsifiable Solutions to Slightly Underdetermined Linear Systems of Equations by Andrew Yagle. The abstract reads:

We consider the problem of reconstructing a sparse image from a few of its 2-D DFT frequency values. A sparse image has pixel values that are mostly zero, with a few non-zero values at unknown locations. The number of known 2-D DFT values must exceed four times the number of non-zero pixel values. We unwrap the 2-D problem to a 1-D problem using the Good-Thomas FFT, and apply Prony's method to compute the non-zero pixel value locations. Thus we reformulate the problem as a dual 2-D harmonic retrieval problem. Our solution has three advantages over direct application of 2-D ESPRIT: (1) Instead of solving a huge generalized eigenvalue problem, we compute the roots on the unit circle of a huge polynomial; (2) the locations of the known 2-D DFT values need not form a centrosymmetric region; and (3) there are no matching issues. Our algorithm is also applicable to 2-D beamforming.

and New Atomicity-Exploiting Algorithms for Super-Resolution X-Ray Crystallography by Andrew Yagle. The abstract reads:

The X-ray crystallography problem is to reconstruct a crystalline structure from the Fourier magnitude of its diffracted scattering data. This has three major difficulties: (1) Only Fourier magnitude (not phase) data are known; (2) There is no support constraint (since the crystal is periodic); and (3) only low-wavenumber scattering data are available. But it also has two major advantages: (1) the crystal is sparse (atomicity) since it consists of isolated atoms; and (2) the crystal structure often has even symmetry. We exploit atomicity to show that the crystal can be reconstructed easily from only low wavenumber Fourier data. We also propose new algorithms for reconstruction of crystals with even or no symmetry from low-wavenumber Fourier magnitude data using two or one isomorphic replacements (4 algorithms). Small numerical examples illustrate the algorithms.

Sparse Imputation for Noise Robust Speech Recognition Using Soft Masks by Jort Gemmeke, Bert Cranen. The abstract reads:

In previous work we introduced a new missing data imputation method for ASR, dubbed sparse imputation. We showed that the method is capable of maintaining good recognition accuracies even at very low SNRs provided the number of mask estimation errors is sufficiently low. Especially at low SNRs, however, mask estimation is difficult and errors are unavoidable. In this paper, we try to reduce the impact of mask estimation errors by making soft decisions, i.e., estimating the probability that a feature is reliable. Using an isolated digit recognition task (using the AURORA-2 database), we demonstrate that using soft masks in our sparse imputation approach yields a substantial increase in recognition accuracy, most notably at low SNRs.

Credit: NASA/JPL/Space Science Institute, Photo of Saturn's rings taken by Cassini the day before yesterday.

CS: Two jobs, Optically multiplexed imaging, Robust estimation of Gaussian mixtures by l_1 penalization, multivariate distribution for subimages,ASIFT

Pierre Vandergheynst has two open positions in his lab. Both involve sparsity and Compressive Sensing. They are also listed in the Compressive Sensing Jobs page.

Continuing on the concept of multiplexing imaging, yesterday it was through coded aperture, today the set-up is a little different and aim at a specific task: tracking. The paper is entitled: Optically multiplexed imaging with superposition space tracking by Shikhar Uttam, Nathan A. Goodman, Mark A. Neifeld, Changsoon Kim, Renu John, Jungsang Kim, and David Brady. The abstract reads:

We describe a novel method to track targets in a large field of view. This method simultaneously images multiple, encoded sub-fields of view onto a common focal plane. Sub-field encoding enables target tracking by creating a unique connection between target characteristics in superposition space and the target’s true position in real space. This is accomplished without reconstructing a conventional image of the large field of view. Potential encoding schemes include spatial shift, rotation, and magnification. We discuss each of these encoding schemes, but the main emphasis of the paper and all examples are based on one-dimensional spatial shift encoding. System performance is evaluated in terms of two criteria: average decoding time and probability of decoding error. We study these performance criteria as a function of resolution in the encoding scheme and signal-to-noise ratio. Finally, we include simulation and experimental results d onstrating our novel tracking method.

On a somewhat different note, yet tracking can be performed by some of this modeling, here is Robust estimation of Gaussian mixtures by l_1 penalization: an experimental study by Stephane Chretien. The abstract reads:

Many experiments in medicine and ecology can be conveniently modeled by finite Gaussian mixtures but face the problem of dealing with small data sets. We propose a robust version of the estimator based on self-regression and sparsity promoting penalization in order to estimate the components of Gaussian mixtures in such contexts. A space alternating version of the penalized EM algorithm is obtained and we prove that its cluster points satisfy the Karush-Kuhn-Tucker conditions. Monte Carlo experiments are presented in order to compare the results obtained by our method and by standard maximum likelihood estimation. In particular, our estimator is seen to perform well better than the maximum likelihood estimator.

Again, tracking is also of importance here with A multivariate distribution for subimages by Steve Maybank . The abstract reads:

A new method for obtaining multivariate distributions for sub-images of natural images is described. The information in each sub-image is summarized by a measurement vector in a measurement space. The dimension of the measurement space is reduced by applying a random projection to the truncated output of the discrete cosine transforms of the sub-images. The measurement space is then reparametrized, such that a Gaussian distribution is a good model for the measurement vectors in the reparametrized space. An Ornstein–Uhlenbeck process, associated with the Gaussian distribution, is used to model the differences between measurement vectors obtained from matching sub-images. The probability of a false alarm and the probability of accepting a correct match are calculated. The accuracy of the resulting statistical model for matching sub-images is tested using images from the MIDDLEBURY stereo database with promising results. In particular, if the probability of accepting a correct match is relatively large, then there is good agreement between the calculated and the experimental probabilities of obtaining a unique match that is also a correct match.

In a similar vein, if you have ever tried SIFT, you know that sometimes it does not work optimally as expected. There is a new algorithm called ASIFT developed by Jean Michel Morel and Guoshen Yu that seems to be very efficient. You can try it directly on two of your own images here at: http://mw.cmla.ens-cachan.fr/megawave/demo/asift/

Summary:
A fully affine invariant image comparison method, Affine SIFT (A-SIFT) is introduced. While SIFT is fully invariant with respect to only four parameters, the new method treats the two left over parameters : the angles defining the camera axis orientation. Against any prognosis, simulating all views depending on these two parameters is feasible with no dramatic computational load. The method permits to reliably identify features that have undergone large transition tilts, up to 36 and more, while state-of-the-art affine normalization methods hardly exceed transition tilts of 2 (SIFT), 2.5 (Harris-Affine and Hessian-Affine) and 10 (MSER).

References:
J.M. Morel and G.Yu, ASIFT: A New Framework for Fully Affine Invariant Image Comparison, to appear in SIAM Journal on Imaging Sciences, 2009.
G. Yu and J.M. Morel, A Fully Affine Invariant Image Comparison Method, accepted to IEEE ICASSP, Taipei, 2009.
J.M. Morel and G.Yu, On the consistency of the SIFT Method, Preprint, CMLA 2008-26, Sept 2008.

Here are some of the comparison between SIFT and ASIFT in videos, this is pretty stunning:






Compare that to SIFT only

Nuit Blanche

You are tired to launch a browser window and hit "nuit blanche" on the Google every morning or you think you might miss one entry of Nuit Blanche, then get new entries directly in your mailbox by entering your email address in the following box and hit the Subscribe button:

You will be asked confirmation in your mailbox.

You can also add this RSS Feed to your FeedReader's list:

http://nuit-blanche.blogspot.com/feeds/posts/default

CS: Testing the Nullspace Property using SDP, Compressive Coded Aperture Imaging, Informative Sensing, NB

Alexandre d'Aspremont and Laurent El Ghaoui recently updated their preprint entitled: Testing the Nullspace Property using Semidefinite Programming. The abstract reads

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.

A beautiful summary of the current state of our knowledge on this issue can be found in the paper:

.....Universal conditions for strong recovery based on sparse extremal eigenvalues were derived in Candes and Tao (2005) and Candes and Tao (2006) who also proved that certain (mostly random) matrix classes satisfied these conditions with an exponentially small probability of failure. More recently, Cohen et al. (2006) derived sparse recovery conditions based on properties of the nullspace of A. In particular, if we define:

α_k = max max y^T x,
{Ax=0, ||x||_1=1} {||y||_1=1, ||y||_1≤k}


Cohen et al. (2006) show that α_k less than 1/2 guarantees strong recovery.
One key issue with the current sparse recovery conditions in Candes and Tao (2005) or Cohen et al. (2006) is that except for explicit recovery thresholds available for certain types of random matrices, testing these conditions on generic matrices is potentially harder than solving the combinatorial ℓ0 problem in (1) as it implies either solving a combinatorial problem to compute αk, or computing sparse eigenvalues. Semidefinite relaxation bounds on sparse eigenvalues were used in d’Aspremont et al. (2008) to test the conditions in Candes and Tao (2005) on arbitrary matrices. In recent independent results, Juditsky and Nemirovski (2008) provide an alternative proof of some of the results in Cohen et al. (2006), extend them to the noisy case and produce a linear programming relaxation bound on α_k with explicit performance bounds. In this paper, we derive a semidefinite relaxation bound on α_k, study its tightness and compare its numerical performance with that of the relaxation in Juditsky and Nemirovski (2008). Because it involves solving a semidefinite program, the complexity of the semidefinite relaxation bound derived here is significantly higher than that of the linear programming based relaxation in Juditsky and Nemirovski (2008) and no explicit performance performance bounds are available here on matrices satisfying sparse recovery conditions, we show on small scale examples that the semidefinite bounds on αk are often, but not always, tighter than those produced by the the linear programming relaxation in Juditsky and Nemirovski (2008)....

This new document is a substantial revision from the previous draft and it now includes some discussion about the work of Anatoli Juditsky and Arkadii Nemirovski in On Verifiable Sufficient Conditions for Sparse Signal Recovery via l_1 Minimization. As you recall, this type of work is extremely valuable as it has the potential of producing guidelines for hardware implementers on how to design their Point Spread Functions and so forth. For instance, one may recall that designing a coded aperture mask for the purpose of providing superresolution hinges on the ability to map a mask to a specific type of Toeplitz matrix [1]. But superresolution may be just the beginning of producing designs beyond what we have been able to do for the past 40 years (at least in coded aperture). For this to happen, hardware designers need to have the freedom to tinker with new designs and then be able to ask the question: Can I do Compressive Sensing with this design ? Currently only the implementation of Anatoli Juditsky and Arkadii Nemirovski is available and is located at:

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

(oops, looks like the code is not available today, I'll report when it is) Alexandre d'Aspremont told me that an implementation of their code will eventually come out. [Update: The numerical part of this draft might change in an upcoming version 3. I'll report shortly on the new version of this paper if there are changes, and on the availability of the code of Anatoli Juditsky and Arkadi Nemirovski. This is a really challenging and important problem and I am glad some of the best minds are looking into it ].

In a somewhat related matter,

Roummel Marcia, Zachary Harmany, and Rebecca Willett just released their much awaited paper entitled Compressive Coded Aperture Imaging. The abstract reads:

Nonlinear image reconstruction based upon sparse representations of images has recently received widespread attention with the emerging framework of compressed sensing (CS). This theory indicates that, when feasible, judicious selection of the type of distortion induced by measurement systems may dramatically improve our ability to perform image reconstruction. However, applying compressed sensing theory to practical imaging systems poses a key challenge: physical constraints typically make it infeasible to actually measure many of the random projections described in the literature, and therefore, innovative and sophisticated imaging systems must be carefully designed to effectively exploit CS theory. In video settings, the performance of an imaging system is characterized by both pixel resolution and field of view. In this work, we propose compressive imaging techniques for improving the performance of video imaging systems in the presence of constraints on the focal plane array size. In particular, we describe a novel yet practical approach that combines coded aperture imaging to enhance pixel resolution with superimposing subframes of a scene onto a single focal plane array to increase field of view. Specifically, the proposed method superimposes coded observations and uses wavelet-based sparsity recovery algorithms to reconstruct the original subframes. We demonstrate the effectiveness of this approach by reconstructing with high resolution the constituent images of a video sequence.

Some of the work has already been covered in [1], but the hardware design and wavelet based reconstruction and the attendant results are new and very interesting. I am sure I'll come back to these later.

Also, I mentioned their work last friday, here is the preprint that introduces us to the concept of "bandwise random projections", I am loving this as it certainly has major ramifications to the understanding of the primary visual cortex, especially trying to compare current modeling efforts and the signal processing aspect of it. The preprint is Informative Sensing by Hyun Sung Chang, Yair Weiss and William T. Freeman. The abstract reads:

Compressed sensing is a recent set of mathematical results showing that sparse signals can be exactly reconstructed from a small number of linear measurements. Interestingly, for ideal sparse signals with no measurement noise, random measurements allow perfect reconstruction while measurements based on principal component analysis (PCA) or independent component analysis (ICA) do not. At the same time, for other signal and noise distributions, PCA and ICA can significantly outperform random projections in terms of enabling reconstruction from a small number of measurements. In this paper we ask: given the distribution of signals we wish to measure, what are the optimal set of linear projections for compressed sensing? We consider the problem of finding a small number of linear projections that are maximally informative about the signal. Formally, we use the InfoMax criterion and seek to maximize the mutual information between the signal, x, and the (possibly noisy) projection y=Wx. We show that in general the optimal projections are not the principal components of the data nor random projections, but rather a seemingly novel set of projections that capture what is still uncertain about the signal, given the knowledge of distribution. We present analytic solutions for certain special cases including natural images. In particular, for natural images, the near-optimal projections are bandwise random, i.e., incoherent to the sparse bases at a particular frequency band but with more weights on the low-frequencies, which has a physical relation to the multi-resolution representation of images.

An attendant presentation of some of the approach can be found in this entry. Let us thank The Google for bringing this one up.

On a different note, the Compressive Sensing Hardware page now has some videos included, if you know of any other, I'll be glad to include them.

Finally, Emmanuel Candes and Terry Tao wrote in the latest IEEE Information Theory Society Newsletter and made a reference to Nuit Blanche. Thanks Laurent for the heads-up.


Reference:
[1] Roummel Marcia and Rebecca Willett, Compressive Coded Aperture Superresolution Image Reconstruction - additional material can be found here while the slides are here

Credit: NASA/JPL-Caltech/University of Arizona/Texas A&M, sol 151 of Phoenix.

CS: Compressive dual photography, Image reconstruction by deterministic CS, Nesterov algorithm

I found the following paper at the Rice repository:


Pradeep Sen and Soheil Darabi, Compressive dual photography. (Computer Graphics Forum, March 2009)

The accurate measurement of the light transport characteristics of a complex scene is an important goal in computer graphics and has applications in relighting and dual photography. However, since the light transport data sets are typically very large, much of the previous research has focused on adaptive algorithms that capture them efficiently. In this work, we propose a novel, non-adaptive algorithm that takes advantage of the compressibility of the light transport signal in a transform domain to capture it with less acquisitions than with standard approaches. To do this, we leverage recent work in the area of compressed sensing, where a signal is reconstructed from a few samples assuming that it is sparse in a transform domain. We demonstrate our approach by performing dual photography and relighting by using a much smaller number of acquisitions than would normally be needed. Because our algorithm is not adaptive, it is also simpler to implement than many of the current approaches.

It looks like an extension of the illumination work performed earlier at Rice and University of Arizona. I will add this project to the Compressive Sensing Hardware page. The following file is in postscript and was found thanks to the Google :-)



Image reconstruction by deterministic compressive sensing by Kangyu Ni, Somantika Datta, Svetlana Roudenko, Douglas Cochran. The abstract reads:

A recently proposed approach for compressive sensing with deterministic measurement matrices is applied to images that possess varying degrees of sparsity in their wavelet representations. The use of these deterministic measurement matrices is found to be approximately as effective as the use of Gaussian random matrices in terms of image reconstruction fidelity. The ``fast reconstruction'' algorithm enabled by this deterministic sampling scheme produces accurate results, but its speed is hampered when the degree of sparsity is not sufficiently high.

Finally, as Gabriel Peyre mentioned to me, it looks like the algorithm developed using the Nesterov scheme by Pierre Weiss is fast. So here is Pierre Weiss' thesis entitled: Fast algorithms for convex optimization. Applications to image reconstruction and change detection. The abstract of which is:

This PhD contains contributions in numerical analysis and in computer vision. In the first part, we focus on the fast resolution, using first order methods, of convex optimization problems. Those problems appear naturally in many image processing tasks like image reconstruction, compressed sensing or texture+cartoon decompositions. They are generally non differentiable or ill-conditioned. We show that they can be solved very efficiently using fine properties of the functions to be minimized. We analyze in a systematic way their convergence rate using recent results due to Y. Nesterov. To our knowledge, the proposed methods correspond to the state of the art of the first order methods. In the second part, we focus on the problem of change detection between two remotely sensed images taken from the same location at two different times. One of the main difficulty to solve this problem is the differences in the illumination conditions between the two shots. This leads us to study the level line illumination invariance. We completely characterize the 3D scenes which produce invariant level lines. We show that they correspond quite well to urban scenes. Then we propose a variational framework and a simple change detection algorithm which gives satisfying results both on synthetic OpenGL scenes and real Quickbird images.

Credit: NASA, Opportunity, navigation camera, sol 1776.