Nuit Blanche

CS: New version of ISD and attendant video tutorials

noreply@blogger.com (Igor) — Fri, 06 Nov 2009 06:01:00 +0000

You probably recall the concept of ISD, a reconstruction solver that uses all measurements available to compute a solution. Well, Wotao Yin just sent me the following: I put a very clean and simple ISD code at http://www.caam.rice.edu/~optimization/L1/ISD/. It comes with two video tutorials. Here is extract of what's new in the package: Version 1.1 (November 3, 2009). [download] This version is much simpler and clearer than ver 1.0 below.Video tutorials: Demo [online] or [download]; Main code [online] or [download].To adapter the code to your data and sparse/compressible signal and for best results, please (i) tune the thresholding methods and parameters, and (ii) consider replacing YALL1 by one designed for your data. The technical report [pdf] describes ideas of effective thresholding.Despite the small problems given in the demos, the code is capable of solving large-scale, multi-dimensional problems. Ver 1.0 below includes large-scale tests. The allowed size of the problem is merely subject to the limit posted by the subproblem solver used.The main code can be extended to deal with multi-dimensional signals in a straightforward way. Enjoy !

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

The Nuit Blanche Effect

noreply@blogger.com (Igor) — Thu, 05 Nov 2009 06:01:00 +0000

When was the last time you knew for a fact that more than 120 people had read the abstract of your paper within a week of releasing it ? Back in May 2008 at the Nonlinear L1 meeting at Texas A&M University, I suddenly realized the power of the blog when Adam Oberman mentioned to me over lunch with Anna Gilbert and Simon Foucart that he knew of the blog (first surprise, we are in College Station, Texas and somebody has heard of the blog :-)) through a friend who had seen a spike of downloads of his paper after being mentioned here (second surprise!). Ever since that moment I have been trying to quantify this effect which, it seems, has grown over time. If you have stories about this or any other stories connected to the blog (you can stay anonymous), I would be very happy to hear them. Let us note that this number is a conservative one as it does not include the people being directly mailed the blog entries (237 as we speak), nor the people coming directly to the website nor people using another feed than the one listed above (412). One more note, the first technincal blog entry after that meeting pointed out the need to understand better the RIP (Restricted Isometry Property: What is it good for ?), a subject of continuing interest.

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: UWB Through-Wall Imaging Based on Compressive Sensing

noreply@blogger.com (Igor) — Wed, 04 Nov 2009 06:01:00 +0000

I picked this up from Lianlin Li's blog ( translation is here): another UWB radar that can detect moving things through walls: UWB Through-Wall Imaging Based on Compressive Sensing by Qiong Huang, Lele Qu, Bingheng Wu, and Guangyou Fang. The abstract reads: To achieve high-resolution 2-D images, through-wall imaging (TWI) radar with ultra-wideband and long antenna arrays faces considerable technical challenges such as a prolonged data collection time, a huge amount of data, and a high hardware complexity. This paper presents a novel data acquisition scheme and an imaging algorithm for TWI radar based on compressive sensing (CS), which states that a signal having a sparse representation can be reconstructed from a small number of nonadaptive randomized projections by solving a tractable convex program. Instead of measuring all spatial-frequency data, a few samples, by employing an overcomplete dictionary, are sufficient to obtain reliable target space images even at high noise levels. Preliminary simulated and experimental results show that the proposed algorithm outperforms the conventional delay-and-sum beamforming method even though many fewer CS measurements are used. I am adding this the Compressive Sensing Hardware page.

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: A Matrix Completion Entry

noreply@blogger.com (Igor) — Tue, 03 Nov 2009 06:01:00 +0000

After Friday's entry on the subject, here some more matrix completion cods and papers:Yi Ma just sent me the following: You may want to check out our new website dedicated for low-rank matrix recovery and completion at: http://perception.csl.illinois.edu/matrix-rank/home.html Matrix recovery (also known as robust PCA) is arguably a more difficult problem that matrix completion and it reveals some nice tradeoff between rank and sparsity. On the website we gather all up to date work on theory, algorithms, and applications (soon). We also provide the code for the fastest algorithms know todate for both matrix recovery and completion.I note that they list the other matrix completion approaches here. and then we have: A Simpler Approach to Matrix Completion by Benjamin Recht. The abstract reads: This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low rank matrix. These results improve on prior work by Candes and Recht, Candes and Tao, and Keshavan, Montanari, and Oh. The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular values, of the hidden matrix subject to agreement with the provided entries. If the underlying matrix satisfies a certain incoherence condition, then the number of entries required is equal to a quadratic logarithmic factor times the number of parameters in the singular value decomposition. The proof of this assertion is short, self contained, and uses very elementary analysis. The novel techniques herein are based on recent work in quantum information theory. and Compressed Quantum Process Tomography by Alireza Shabani, R. L. Kosut, Herschel Rabitz. The abstract reads: The characterization of a decoherence process is among the central challenges in quantum physics. A major difficulty with current quantum process tomography methods is the enormous number of experiments needed to accomplish a tomography task. Here we present a highly efficient method for tomography of a quantum process that has a small number of significant elements. Our method is based on the compressed sensing techniques being used in information theory. In this new method, for a system with Hilbert space dimension n and a process matrix of dimension n^2 x n^2 with sparsity s, the required number of experimental configurations is O(s log n^4). This heralds a logarithmic advantage in contrast to other methods of quantum process tomography. More specifically, for q-qubits with n=2^q, the scaling of resources is O(sq) linear in the product of sparsity and number of qubits.

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

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

noreply@blogger.com (Igor) — Mon, 02 Nov 2009 06:01:00 +0000

Today, we have two papers and two codes: Real vs. complex null space properties for sparse vector recovery by Simon Foucart, Remi Gribonval. The abstract reads: We identify and solve an overlooked problem about the characterization of underdetermined systems of linear equations for which sparse solutions have minimal `1-norm. This characterization is known as the null space property. When the system has real coefficients, sparse solutions can be considered either as real or complex vectors, leading to two seemingly distinct null space properties. We prove that the two properties actually coincide by establishing a link with a problem about convex polygons in the real plane. Incidentally, we also show the equivalence between stable null space properties which account for the stable reconstruction by `1-minimization of vectors that are not exactly sparse. Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations by Mingyuan Zhou, Haojun Chen, John Paisley, Lu Ren, Guillermo Sapiro and Lawrence Carin. The abstract reads: Non-parametric Bayesian techniques are considered for learning dictionaries for sparse image representations, with applications in denoising, inpainting and compressive sensing (CS). The beta process is employed as a prior for learning the dictionary, and this non-parametric method naturally infers an appropriate dictionary size. The Dirichlet process and a probit stick-breaking process are also considered to exploit structure within an image. The proposed method can learn a sparse dictionary in situ; training images may be exploited if available, but they are not required. Further, the noise variance need not be known, and can be nonstationary. Another virtue of the proposed method is that sequential inference can be readily employed, thereby allowing scaling to large images. Several example results are presented, using both Gibbs and variational Bayesian inference, with comparisons to other state-of-the-art approaches.From the BCS webpage: BPFA image denoising and inpainting: The package includes the inference update equations and Matlab codes for image denoising and inpainting via the non-parametric Bayesian dictionary learning approach. Download: BPFA.zip (Last Updated: Oct. 30, 2009) Back in March I mentioned the following paper Coordinate Descent Optimization for $\ell^1$ Minimization with Application to Compressed Sensing; a Greedy Algorithm by Yingying Li and Stanley Osher. The code is now available on Matlab Central. Credit: OnOrbit, X-prize, Unreasonable rocket.

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

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

noreply@blogger.com (Igor) — Fri, 30 Oct 2009 05:01:00 +0000

Two items first. In yesterday's entry on the Sudoku paper ( Linear Systems, Sparse Solutions, and Sudoku by Prabhu Babu, Kristiaan Pelckmans, Petre Stoica, and Jian Li) it is interesting to find out that a re-weighted scheme seems to be doing better than some game specific greedy algorithm. Furthermore, at the end of the paper, we can read the following: The presently known sufficient conditions on A for checking the equivalence of P0 and P1, like the restricted isometry property (RIP) [5] and Kashin, Garnaev, Gluskin (KGG) inequality [6], do not hold for Sudoku. So analyzing the equivalence of l0 and l1 norm solutions in the context of Sudoku requires novel conditions for sparse recovery.I am not sure that RIP of [5] is the condition to check for here, (RIP-2) more likely the sparsity of the measurement matrix implies some type of RIP-1 condition. I also thought KGG was a necessary and sufficient condition albeit an NP-Hard at that. Other conditions can be found on the Compressive Sensing Big Picture page. In the super-resolution paper mentioned earlier this week, entitled Super-resolution ghost imaging via compressive sampling reconstruction by Wenlin Gong and Shensheng Han, Wenlin confirms to me that only l1_magic was used not GPSR as the reference would tend to indicate. I am sure we are going to see some improvement in the near future. Other reconstruction solvers can be found in the Compressive Sensing Big Picture page too. David Gross just sent me the following: ...I'm a physicist and new to the field. Originally, some colleagues and me got interested in compressed sensing and matrix completion in the context of quantum state tomography (meaning the experimental characterization of a quantum system). Our paper arXiv:0909.3304 was mentioned on your blog. The methods we needed to develop in order to translate known results on matrix completion by Candes, Recht, Tao and others to quantum mechanics proved far more general than anticipated. We can now show that a low-rank (n x n)-matrix may be recovered from basically O(n r log^2 n) randomly selected expansion coefficients with respect to any matrix basis. The matrix completion problem is just a special case. Most importantly, though, the complexity of the proofs was reduced substantially. The spectacular argument by Candes and Tao in arXiv:0903.1476 covered about 40 pages. The new paper implies these results, but is much simpler to digest. The first version of the paper went onto the arxiv two weeks ago: arXiv:0910.1879. However, it significantly evolved since then. In some cases the bounds are now down to O(n r log n), which -- I'm happy to say -- is tight up to multiplicative factors. There is an obvious challenge to be met. The O(n r log n)-bounds do not currently extend to the original matrix completion problem. They come tantalizingly close, though, with only one single lemma obstructing a more general result. The precise problem is pointed out at the end of Section III B. Before submitting the paper, I plan to add a final note. The statements all continue to be true if instead of a matrix basis a "tight frame" (a.k.a. "overcomplete basis") is used. I should also point out Benjamin Recht's recent and strongly related pre-print arXiv:0910.0651 to you. He independently translated some of the results in our earlier paper on quantum tomography to the matrix completion problem (apparently overlooking our announcement of exactly the same result in the physics paper). Let us note that the last preprint of Benjamin Recht was recently updated. But first, here is the new revision entitled: Recovering low-rank matrices from few coefficients in any basis by David Gross We establish novel techniques for analyzing the problem of low-rank matrix recovery. The methods are both considerably simpler, and more general than previous approaches. It is shown that an unknown n × n matrix of rank r can be efficiently reconstructed given knowledge of only O(nr \nu log2 n) randomly...

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: Linear Systems, Sparse Solutions, and Sudoku, Compressed sensing performance bounds under Poisson noise

noreply@blogger.com (Igor) — Thu, 29 Oct 2009 05:01:00 +0000

Angshul Majumdar just pointed out to me the following paper entitled: Linear Systems, Sparse Solutions, and Sudoku by Prabhu Babu, Kristiaan Pelckmans, Petre Stoica, and Jian Li. The abstract reads: In this paper, we show that Sudoku puzzles can be formulated and solved as a sparse linear system of equations. We begin by showing that the Sudoku ruleset can be expressed as an underdetermined linear system: ${mmb{Ax}}={mmb b}$, where ${mmb A}$ is of size $mtimes n$ and $n>m$. We then prove that the Sudoku solution is the sparsest solution of ${mmb{Ax}}={mmb b}$, which can be obtained by $l_{0}$ norm minimization, i.e. $minlimits_{mmb x}Vert{mmb x}Vert_{0}$ s.t. ${mmb{Ax}}={mmb b}$. Instead of this minimization problem, inspired by the sparse representation literature, we solve the much simpler linear programming problem of minimizing the $l_{1}$ norm of ${mmb x}$, i.e. $minlimits_{mmb x}Vert{mmb x}Vert_{1}$ s.t. ${mmb{Ax}}={mmb b}$, and show numerically that this approach solves representative Sudoku puzzles. We have heard about Sudoku before in compressive sensing. The code implementing this can be found here. I also found the following on arxiv: Compressed sensing performance bounds under Poisson noise by Maxim Raginsky, Zachary Harmany, Roummel Marcia, Rebecca Willett. The abstract reads: This paper describes performance bounds for compressed sensing (CS) where the underlying sparse or compressible (sparsely approximable) signal is a vector of nonnegative intensities whose measurements are corrupted by Poisson noise. In this setting, standard CS techniques cannot be applied directly for several reasons. First, the usual signal-independent and/or bounded noise models do not apply to Poisson noise, which is non-additive and signal-dependent. Second, the CS matrices typically considered are not feasible in real optical systems because they do not adhere to important constraints, such as nonnegativity and photon flux preservation. Third, the typical $\ell_2$--$\ell_1$ minimization leads to overfitting in the high-intensity regions and oversmoothing in the low-intensity areas. In this paper, we describe how a feasible positivity- and flux-preserving sensing matrix can be constructed, and then analyze the performance of a CS reconstruction approach for Poisson data that minimizes an objective function consisting of a negative Poisson log likelihood term and a penalty term which measures signal sparsity. We show that, as the overall intensity of the underlying signal increases, an upper bound on the reconstruction error decays at an appropriate rate (depending on the compressibility of the signal), but that for a fixed signal intensity, the signal-dependent part of the error bound actually grows with the number of measurements or sensors. This surprising fact is both proved theoretically and justified based on physical intuition. On his webpage, Roummel Marcia has the following announcement: Opportunities: Positions for graduate and undergraduate students are available in the areas of optimization, linear algebra, and compressed sensing. These positions are in conjunction with the National Science Foundation grant, DMS-0811062: Second-order methods for large-scale optimization in compressed sensing. Send me an email if you are interested in any of these positions.

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: Super-resolution ghost imaging via compressive sampling reconstruction

noreply@blogger.com (Igor) — Wed, 28 Oct 2009 05:01:00 +0000

Bada bing, bada boom, when was the last time you had to increase the size of your pixel on a CCD dye in order to obtain a better resolution ? Looks like this is a result coming out of a CS reconstruction in another Ghost Imaging experiment. Enjoy ! Super-resolution ghost imaging via compressive sampling reconstruction by Wenlin Gong and Shensheng Han. The abstract reads: For ghost imaging, pursuing high resolution images and short acquisition times required for reconstructing images are always two main goals. We report an image reconstruction algorithm called compressive sampling (CS) reconstruction to recover ghost images. By CS reconstruction, ghost imaging with both super-resolution and a good signal-to-noise ratio can be obtained via short acquisition times. Both effect influencing and approaches further improving the resolution of ghost images via CS reconstruction, relationship between ghost imaging and CS theory are also discussed.

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: A job with Exxon.

noreply@blogger.com (Igor) — Tue, 27 Oct 2009 05:01:00 +0000

As much as it looks like a nice opportunity, this one is not located in Paris so I will pass up on it. Here is a job opportunity that showed up on my radar screen which has been added to the Compressive Sensing Jobs page: Employer: ExxonMobil Location: Clinton, NJ United States Last Updated: 10/26/2009 Job Code: 7382BR AutoReqId 7382BR Job or Campus Folder Research Scientists (2) -Wave Propagation and Numerical Methods Job Description ExxonMobil's Corporate Strategic Research Laboratory is seeking applications from talented individuals in physics, applied mathematics, or engineering with a strong record of achievements in fields related to wave propagation in heterogeneous media, and its associated mathematical and numerical methods. Research Scientist - Wave propagation and transport in heterogeneous and porous media. Experience with the physical, mathematical and numerical analyses of one of: wave propagation in heterogeneous media, multi-scale transport phenomena, and/or fluid-structure interactions at the rock pore scale and their impact on the macro scale. Research Scientist-Compressive sensing. Experience with the mathematics of signal/image processing, denoising, sub-Nyquist signal reconstruction, and sparse representation of data. Applicants should have a PhD in applied mathematics, physics, engineering, geophysics, or a related field, with a strong ability in their field of expertise. Proficiency with scientific programming languages and experience with large-scale, parallel, numerical simulations are definite advantages. The ability to communicate and interact with internal and external groups will be an important selection criterion. Candidates should have a strong publication record, excellent oral presentation and writing skills, and show a desire and ability to grow into new science areas. The successful candidate will join a dynamic, multi-disciplinary group of world-class scientists who focus on performing breakthrough research and creating new approaches to solve our most challenging problems. Technical staff members in this position implement and report on independent research, participate in program development, as well as collaborate internationally with leading engineers and scientists from industry, universities and other technical institutions. ExxonMobil's Corporate Strategic Research (CSR) laboratory is a powerhouse in energy research focusing on fundamental science that can lead to technologies having a direct impact on solving our biggest energy challenges. Our facilities are centrally located in scienic Annandale, New Jersey, approximately one hour from both New York City and Phildelphia. ExxonMobil is an Equal Opportunity Employer Job Location Clinton, NJ

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: Making CS Mainstream, CS Data Recovery in Wireless Sensor Networks, Routing and Signal for CS in WSNs, Very High Resolution SAR, Postdoc

noreply@blogger.com (Igor) — Mon, 26 Oct 2009 08:13:00 +0000

One of the ways to make compressive sensing more mainstream is to enable tinkerers to play with something that implements some sorts of controlled multiplexing. Case in point, what could be done with the newly released tiny DMD based projectors or these ? and what about this DMD kit with no driver ? then there is always the more expensive DLP kits from TI ? By the way, if you are wondering how much an SLM cost, such the one used in the work of by Ivo Vellekoop and Allard Mosk ( Phase control algorithms for focusing light through turbid media ) that is about 3,000 US$ and up. Today, we have papers and jobs mostly from Europe, enjoy! A Bayesian Analysis of Compressive Sensing Data Recovery in Wireless Sensor Networks by Riccardo Masiero, Giorgio Quer, Michele Rossi and Michele Zorzi. The abstract reads: In this paper we address the task of accurately reconstructing a distributed signal through the collection of a small number of samples at a data gathering point using Compressive Sensing (CS) in conjunction with Principal Component Analysis (PCA). Our scheme compresses in a distributed way real world non-stationary signals, recovering them at the data collection point through the online estimation of their spatial/temporal correlation structures. The proposed technique is hereby characterized under the framework of Bayesian estimation, showing under which assumptions it is equivalent to optimal maximum a posteriori (MAP) recovery. As the main contribution of this paper, we proceed with the analysis of data collected by our indoor wireless sensor network (WSN) testbed, proving that these assumptions hold with good accuracy in the considered real world scenarios. This provides empirical evidence of the effectiveness of our approach and proves that CS is a legitimate tool for the recovery of real-world signals in WSNs. On the Interplay Between Routing and Signal Representation for Compressive Sensing in Wireless Sensor Networks by Giorgio Quer, Riccardo Masiero, Daniele Munaretto, Michele Rossi, Joerg Widmer and Michele Zorzi. The abstract reads: Compressive Sensing (CS) shows high promise for fully distributed compression in wireless sensor networks (WSNs). In theory, CS allows the approximation of the readings from a sensor field with excellent accuracy, while collecting only a small fraction of them at a data gathering point. However, the conditions under which CS performs well are not necessarily met in practice. CS requires a suitable transformation that makes the signal sparse in its domain. Also, the transformation of the data given by the routing protocol and network topology and the sparse representation of the signal have to be incoherent, which is not straightforward to achieve in real networks. In this work we address the data gathering problem in WSNs, where routing is used in conjunction with CS to transport random projections of the data.We analyze synthetic and real data sets and compare the results against those of random sampling. In doing so, we consider a number of popular transformations and we find that, with real data sets, none of them are able to sparsify the data while being at the same time incoherent with respect to the routing matrix. The obtained performance is thus not as good as expected and finding a suitable transformation with good sparsification and incoherence properties remains an open problem for data gathering in static WSNs. At Fringe 2009, a meeting organized by ESA in Italy the following paper will be presented (only the abstract is available): Very High Resolution SAR Tomography via Compressive Sensing by Zhu Xiaoxiang and Bamler Richard. The abstract reads: SAR tomography (TomoSAR) extends the synthetic aperture principle into the elevation direction for 3-D imaging. It uses stacks of several acquisitions from slightly different viewing angles (the elevation aperture) to reconstruct the reflectivity function along the elevation direction by means of spectral analysis for every...

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: Compressed Sensing for Fusion Frames, Combinatorial Compressed Sensing, The Geometry of Generalized Binary Search, Ranging Imager,TCS and finance.

noreply@blogger.com (Igor) — Sat, 24 Oct 2009 05:01:00 +0000

Here are a few papers of related interest for the week-end. Compressed Sensing for Fusion Frames by Petros Boufounos, Gitta Kutyniok, and Holger Rauhut. The abstract reads: Compressed Sensing (CS) is a new signal acquisition technique that allows sampling of sparse signals using significantly fewer measurements than previously thought possible. On the other hand, a fusion frame is a new signal representation method that uses collections of subspaces instead of vectors to represent signals. This work combines these exciting new fields to introduce a new sparsity model for fusion frames. Signals that are sparse under the new model can be compressively sampled and uniquely reconstructed in ways similar to sparse signals using standard CS. The combination provides a promising new set of mathematical tools and signal models useful in a variety of applications. With the new model, a sparse signal has energy in very few of the subspaces of the fusion frame, although it needs not be sparse within each of the subspaces it occupies. We define a mixed `1/`2 norm for fusion frames. A signal sparse in the subspaces of the fusion frame can thus be sampled using very few random projections and exactly reconstructed using a convex optimization that minimizes this mixed `1/`2 norm. The sampling conditions we derive are very similar to the coherence and RIP conditions used in standard CS theory. Then there is a presentation by Mark Iwen on Combinatorial Compressed Sensing: Fast algorithms with Recovery Guarantees. Of noted interest is the application section at the very end where one considers learning a function with multiple parameters: A situation that is also the subject of much interest in calibration or machine learning in general. Let us note that another way of performing some type of function learning is through the Experimental Probabilistic Hypersurface (more details can be found here). Not really related to compressive sensing but of interest nonetheless since it deals with learning functions: The Geometry of Generalized Binary Search by Robert Nowak. The abstract reads: This paper investigates the problem of determining a binary-valued function through a sequence of strategically selected queries. The focus is an algorithm called Generalized Binary Search (GBS). GBS is a well-known greedy algorithm for determining a binary-valued function through a sequence of strategically selected queries. At each step, a query is selected that most evenly splits the hypotheses under consideration into two disjoint subsets, a natural generalization of the idea underlying classic binary search and Shannon-Fano coding. GBS is used in many applications including channel coding, experimental design, fault testing, machine diagnostics, disease diagnosis, job scheduling, image processing, computer vision, and machine learning. This paper develops novel incoherence and geometric conditions under which GBS achieves the information-theoretically optimal query complexity; i.e., given a collection of N hypotheses, GBS terminates with the correct function in O(logN) queries. Furthermore, a noise tolerant version of GBS is developed that also achieves the optimal query complexity. These results are applied to learning multidimensional threshold functions, a problem arising routinely in image processing and machine learning. And here are two architectures for cameras to determine ranges: Annular folded optic imager (paper)Coded Aperture PhotographyThey are interesting in that they don't have your usual Point Spread Function (or transfer function). Finally, I have always been impressed by some results in TCS (Theoretical Computer Science) and always wonders what type of impact they will have in the civil society, here are two in particular: The security of knowing nothing by Bernard ChazelleComputational Complexity and Information Asymmetry in Financial Products by Sanjeev Arora, Boaz Barak, Markus Brunnermeier and Rong Ge. Of note, the excellent blog...

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: Learning with Compressible Priors, Spatially-Localized Compressed Sensing and Routing in Multi-Hop Sensor Networks?, Learning low dim manifolds

noreply@blogger.com (Igor) — Fri, 23 Oct 2009 05:01:00 +0000

If you recall, one of the reason Compressive Sensing is bound to touch on many subjects and fields of engineering ( see sparsity in everything series of posts) lies in the fact that most occurrences in Nature follow some type of power law. Volkan Cevher provides some insight on the subject of signal sparsity and the probability distribution from which they are sampled from in his upcoming paper at NIPS entitled: Learning with Compressible Priors. The abstract reads: We describe a set of probability distributions, dubbed compressible priors, whose independent and identically distributed (iid) realizations result in p-compressible signals. A signal x element of R^N is called p-compressible with magnitude R if its sorted coefficients exhibit a power-law decay as |x|_(i) . R i^(-d), where the decay rate d is equal to 1/p. p-compressible signals live close to K-sparse signals (K \lt\lt N) in the l_r-norm (r \gt p) since their best K-sparse approximation error decreases with O (R K^(1/r-1/p) ) We show that the membership of generalized Pareto, Student’s t, log-normal, Frechet, and log-logistic distributions to the set of compressible priors depends only on the distribution parameters and is independent of N. In contrast, we demonstrate that the membership of the generalized Gaussian distribution (GGD) depends both on the signal dimension and the GGD parameters: the expected decay rate of N-sample iid realizations from the GGD with the shape parameter q is given by 1/[q log (N/q)]. As stylized examples, we show via experiments that the wavelet coefficients of natural images are 1.67-compressible whereas their pixel gradients are 0:95 log (N/0.95)-compressible, on the average. We also leverage the connections between compressible priors and sparse signals to develop new iterative re-weighted sparse signal recovery algorithms that outperform the standard l_1-norm minimization. Finally, we describe how to learn the hyperparameters of compressible priors in underdetermined regression problems. Volkan Cevher also makes available RANDSC, a small code generating compressible signals from a specified distribution. If we could now make a connection between these distributions and the l_q ( q less than 1) minimization techniques used to recover signals, it would be great[Oops, let me take that back, Volkan points to section 5.2 entitled " Iterative l_s-decoding for iid scale mixtures of GGD", duh] Also found via another blog: Spatially-Localized Compressed Sensing and Routing in Multi-Hop Sensor Networks? by Sungwon Lee, Sundeep Pattem, Maheswaran Sathiamoorthy, Bhaskar Krishnamachari, and Antonio Ortega. The abstract reads: We propose energy-efficient compressed sensing for wireless sensor networks using spatially-localized sparse projections. To keep the transmission cost for each measurement low, we obtain measurements from clusters of adjacent sensors. With localized projection, we show that joint reconstruction provides signicantly better reconstruction than independent reconstruction. We also propose a metric of energy overlap between clusters and basis functions that allows us to characterize the gains of joint reconstruction for dierent basis functions. Compared with state of the art compressed sensing techniques for sensor network, our experimental results demonstrate signicant gains in reconstruction accuracy and transmission cost.Finally, I am rebounding on yesterday's statement on Machine Learning and Compressive Sensing here is a view of some of the subject in ML and Manifolds featured in the recent talk by Yoav Freund entitled Learning low dimensional manifolds and presented at Google (by the way, what's up with Google engineers who don't know their mics are on ? uh ?) What is interesting is his use of manifold for system calibration at 52 minutes into the video where he describes the 3 dimensional manifold living in a 23-dimension dataset. Yoav's project described in the video is the Automatic Cameraman.

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: NIPS Workshop on Manifolds, sparsity, and structured models, Active Learning, Random Coding, FRI,

noreply@blogger.com (Igor) — Thu, 22 Oct 2009 05:01:00 +0000

Ever since that blog entry featuring work on manifold signal processing and CS , I have had some expectation of some type of integration of compressive sensing in machine learning topics beyond simply publications. It looks like 2009 is the year when this is happening in the form of workshops within an ML conference. First, Mike Wakin is co-organizing a NIPS workshop on Low-dimensional geometric models along with Richard Baraniuk, Piotr Indyk, Bruno Olshausen, Volkan Cevher, and Mark Davenport,. The call for contributions for that workshop follows: CALL FOR CONTRIBUTIONSNIPS Workshop on Manifolds, sparsity, and structured models: When can low-dimensional geometry really help? Whistler, BC, Canada, December 12, 2009 http://dsp.rice.edu/nips-2009 Important Dates: ---------------- Submission of extended abstracts: October 30, 2009 (later submission might not be considered for review) Notification of acceptance: November 5, 2009 Workshop date: December 12, 2009 Overview: --------- Manifolds, sparsity, and other low-dimensional geometric models have long been studied and exploited in machine learning, signal processing and computer science. For instance, manifold models lie at the heart of a variety of nonlinear dimensionality reduction techniques. Similarly, sparsity has made an impact in the problems of compression, linear regression, subset selection, graphical model learning, and compressive sensing. Moreover, often motivated by evidence that various neural systems are performing sparse coding, sparse representations have been exploited as an efficient and robust method for encoding a variety of natural signals. In all of these cases the key idea is to exploit low-dimensional models to obtain compact representations of the data. The goal of this workshop is to find commonalities and forge connections between these different fields and to examine how we can we exploit low-dimensional geometric models to help solve common problems in machine learning and beyond. Submission instructions: ------------------------ We invite the submission of extended abstracts to be considered for a poster presentation at this workshop. Extended abstracts should be 1-2 pages, and the submission does not need to be blind. Extended abstracts should be sent to md@rice.edu in PDF or PS file format. Accepted extended abstracts will be made available online at the workshop website. Organizers: ----------- * Richard Baraniuk, Volkan Cevher, Mark Davenport, Rice University. * Piotr Indyk, MIT. * Bruno Olshausen, UC Berkeley. * Michael Wakin, Colorado School of Mines. Second, Rui Castro is one of the organizer of a NIPS workshop on Adaptive Sensing, Active Learning and Experimental Design. From the NIPS workshop webpage: Submission of extended abstracts: October 27, 2009 (later submission might not be considered for review) Notification of acceptance: November 5, 2009 Workshop date: December 11, 2009 Also found on the interwebs: Channel protection: Random coding meets sparse channels, by M. Salman Asif, William Mantzel and Justin Romberg. The abstract reads: Multipath interference is an ubiquitous phenomenon in modern communication systems. The conventional way to compensate for this effect is to equalize the channel by estimating its impulse response by transmitting a set of training symbols. The primary drawback to this type of approach is that it can be unreliable if the channel is changing rapidly. In this paper, we show that randomly encoding the signal can protect it against channel uncertainty when the channel is sparse. Before transmission, the signal is mapped into a slightly longer codeword using a random matrix. From the received signal, we are able to simultaneously estimate the channel and recover the transmitted signal. We discuss two schemes for the recovery. Both of them exploit the sparsity of the underlying channel. We show that if the channel impulse...

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: Workshop on Sparsity and Modern Mathematical Methods for High Dimensional Data, Learning Deep Architectures for AI

noreply@blogger.com (Igor) — Wed, 21 Oct 2009 05:01:00 +0000

One of the use of focusing light in turbid tissues could easily be used in system like this one. In a different area, I have always wondered why when one delivers a certain radiation dose to a particular area of the body, additional sensors were not arranged around that would perform an imaging task at the same time. Food for thoughts. Anyway, there will be an Interdisciplinary Workshop on Sparsity and Modern Mathematical Methods for High Dimensional Data on April 6--10, 2010 in Brussels, Belgium. While reading Learning Deep Architectures for AI by Yoshua Bengio. The abstract reads; Theoretical results suggest that in order to learn the kind of complicated functions that can represent high level abstractions (e.g. in vision, language, and other AI-level tasks), one may need deep architectures. Deep architectures are composed of multiple levels of non-linear operations, such as in neural nets with many hidden layers or in complicated propositional formulae re-using many sub-formulae. Searching the parameter space of deep architectures is a difficult task, but learning algorithms such as those for Deep Belief Networks have recently been proposed to tackle this problem with notable success, beating the state-of-the-art in certain areas. This paper discusses the motivations and principles regarding learning algorithms for deep architectures, in particular those exploiting as building blocks unsupervised learning of single-layer models such as Restricted Boltzmann Machines, used to construct deeper models such as Deep Belief Networks.I noted a nice discussion about compressive sensing in paragraph 7.1 entitled "Sparse Representations in Auto-Encoders and RBMs" Credit: NASA / JPL / SSI / colorization by Gordan Ugarkovic, Tethys and Titan, Cassini captured a grayscale animation of Tethys crossing in front of Titan on October 17, 2009. In this version, Gordan Ugarkovic has colored in Titan based on its color as seen in previous Cassini photos.

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: Lower Bounds for Sparse Recovery, Super-resolution, Sparse Multipath Channels, RIP for Structurally-Subsampled Unitary Matrices

noreply@blogger.com (Igor) — Tue, 20 Oct 2009 05:01:00 +0000

The photo on the side shows the resulting plume as seen from the LCROSS cameras. In a different direction, here is a thing I did not know about SSDs. As opposed to Hard Disk Drives, SSDs can allow parallel access to different jobs running on the CPU. SSDs also allow faster access to the data in memory (that part I knew). I wonder how this could help some of the reconstruction processes in Compressive Sensing ? Jean-Luc Stark will give a talk at Saclay today, let us hope that the audience will get to hear if the initial tests of Compressive Sensing encoding of the PACS camera on Herschel are good. Now let's go back to papers. I mentioned the abstract earlier, but now the paper is now available: Lower Bounds for Sparse Recovery by Khanh Do Ba, Piotr Indyk, Eric Price and David Woodruff. The abstract reads: We consider the following k-sparse recovery problem: design an m * n matrix A, such that for any signal x, given Ax we can efficiently recover x^ satisfying ||x - x^||_1 \le C min_k-sparse x0 ||x - x'||_1. It is known that there exist matrices A with this property that have only O(k log(n/k)) rows. In this paper we show that this bound is tight. Our bound holds even for the more general randomized version of the problem, where A is a random variable, and the recovery algorithm is required to work for any fixed x with constant probability (over A). I mentioned this approach before as it was featured in a video online, here is the associated paper: Super-Resolution with Sparse Mixing Estimators by Stephane Mallat and Guoshen Yu. The abstract reads: We introduce a class of inverse problem estimators computed by mixing adaptively a family of linear estimators corresponding to different priors. Sparse mixing weights are calculated over blocks of coefficients in a frame providing a sparse signal representation. They minimize an l1 norm taking into account the signal regularity in each block. Adaptive directional image interpolations are computed over a wavelet frame with an O(N logN) algorithm. According to the paper, the SME algorithm is at http://www.cmap.polytechnique.fr/~mallat/SME.html, but it is not there for the moment. Also found on the interwebs: Signal Detection in Sparse Multipath Channels by Matt Malloy and Akbar Sayeed. The abstract reads: In this paper, we revisit the problem of signal detection in multipath environments. Existing results implicitly assume a rich multipath environment. Our work is motivated by physical arguments and recent experimental results that suggest physical channels encountered in practice exhibit a sparse structure, especially at high signal space dimension (i.e., large time-bandwidth product). We first present a model for sparse channels that quantifies the independent degrees of freedom (DoF) in the channel as a function of the physical propagation environment and signal space dimension. The number of DoF represents the delay-Doppler diversity afforded by the channel and, thus, critically impacts detection performance. Our focus is on two types of non-coherent detectors: the energy detector (ED) and the optimal non-coherent detector (ONCD) that assumes full knowledge of channel statistics. Results show, for a uniform distribution of paths in delay and Doppler, the channel exhibits a rich structure at low signal space dimension and then gets progressively sparser as this dimension is increased. Consequently, the performance of the detectors is identical in the rich regime. As the signal space dimension is increased and the channel becomes sparser, the ED suffers significant degradation in performance relative to the ONCD. Finally, our results show the existence of an optimal signal space dimension - one that yields the best detection performance - as a function of the physical channel characteristics and the operating signal to noise ratio (SNR). After the result on Toeplitz matrices, which eventually could be used for coded aperture here is a new paper for measurement matrices...

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: KSVDS-Box and OMPS-Box, Simultaneous Sparse Approximation, Inferring Ranking using Constrained Sensing, Justice Pursuit

noreply@blogger.com (Igor) — Mon, 19 Oct 2009 05:01:00 +0000

Another blogger who went to the OSA meeting on top of David Brady blogged about the meeting and his encounter with compressive sensing and ghost imaging :-). On top of the previous answers, Angshul Majumdar seems to think that a "very neat answer to his question" is the Sparse Signal Restoration course by Ivan Selesnick at: http://cnx.org/content/m32168/latest/ Rebounding on Lianlin Li's blog entry (English translation here) of this week-end that features the second reference of this entry namely Phase control algorithms for focusing light through turbid media by Ivo Vellekoop and Allard Mosk and discusses Sparse Bayesian Algorithm, I allso want to show two figures from that paper: There is a discussion of three algorithms for focusing light through some random medium by using different set of configurations for the Spatial Light Modulator (SLM). The first set is equivalent to the usual raster mode, while the third one has a random permutation component to it which is not unlike what we have in Compressive Sensing. The convergence of these algorithms can be shown in the following figures: One final note on this work is that it is more or less equivalent to how one used to solve coded aperture problems and this is why I think CS reconstruction algorithms might provide faster way of focusing light. Ron Rubinstein has released the KSVDS-Box and OMPS-Box packages..." These packages implement the OMP and K-SVD algorithms for sparse dictionaries, as introduced in their paper Double Sparsity - Learning Sparse Dictionaries for Sparse Signal Approximation (see below). He also published the packages KSVD-Boxv13 and OMP-Box v10. These new versions reduce memory consumption, accelerate computation, and resolve a few minor bugs..." OMP-Box v10 Implementation of the Batch-OMP and OMP-Cholesky algorithms for quick sparse-coding of large sets of signals.OMPS-Box v1 Implementation of the Batch-OMP and OMP-Cholesky algorithms for sparse dictionaries.KSVD-Box v13 Implementation of the K-SVD and Approximate K-SVD dictionary training algorithms, and the K-SVD Denoising algorithm. Requires OMP-Box v10.KSVDS-Box v11 Implementation of the sparse K-SVD dictionary training algorithm and the sparse K-SVD Denoising algorithm. Requires OMPS-Box v1. The package is also available without demo volumes (less recommended) at KSVDS-Box v11-min.The paper is : Double Sparsity: Learning Sparse Dictionaries for Sparse Signal Approximation by Ron Rubinstein, Michael Zibulevsky and Michael Elad. The abstract reads: An efficient and flexible dictionary structure is proposed for sparse and redundant signal representation. The proposed sparse dictionary is based on a sparsity model of the dictionary atoms over a base dictionary, and takes the form D = \Phi A where \Phi is a fixed base dictionary and A is sparse. The sparse dictionary provides efficient forward and adjoint operators, has a compact representation, and can be effectively trained from given example data. In this, the sparse structure bridges the gap between implicit dictionaries, which have efficient implementations yet lack adaptability, and explicit dictionaries, which are fully adaptable but non-efficient and costly to deploy. In this paper we discuss the advantages of sparse dictionaries, and present an efficient algorithm for training them. We demonstrate the advantages of the proposed structure for 3-D image denoising. Here are a set of papers I found on the interwebs: Simultaneous Sparse Approximation : insights and algorithms by Alain Rakotomamonjy. The abstract reads: This paper addresses the problem of simultaneous sparse approximation of signals, given an overcomplete dictionary of elementary functions, with a joint sparsity profile induced by a ℓp − ℓq mixednorm. Our contributions are essentially two-fold i) making connections between such an approach and other methods available in the literature and ii) on providing algorithms for solving the problem with different values of p and q. At...

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: Food for thoughts for the week-end.

noreply@blogger.com (Igor) — Fri, 16 Oct 2009 10:39:00 +0000

Before all of you go home for the week-end, let me add one more thing to the entry of yesterday and then some. Even though I suck, I don't think I am the only one who is going to save that entry, print it and parse it over the week-end. Looks like Giuseppe Paleologo is going to do the same but I am sure we won't be the only ones. Giuseppe added the following in the comment section of yesterday's entry: I have to say that it's quite amazing that a tweet I shot to Igor cascaded in two detailed replies from none other than Jared Tanner and Remi Gribonval. Thanks to Jared for the nice geometric intuition provided for the NSP. I still have to digest his comment, and his recent paper with Blanchard and Cartis. Briefly, I should mention that the question of RIP vs NSP is interesting to me because in statistical applications where A is observational, RIP is not obviously satisfied. However, even when it is not satisfied, l1 minimization or lasso perform well, so possibly there is a different explanation for their success. In this respect, I am especially interested in stable recovery under the two assumptions. I have been reading some papers and presentations by Remi, and have been thinking about his statement: "however the RIP seems necessary to guarantee robustness to noise" (which appears in the recent IEEE paper). In most papers this seems to be the case, because stability depends obviously on the metric properties of the encoder, which RIP captures. The (lone?) exception is a recent paper of Yin Zhang (http://www.caam.rice.edu/~zhang/reports/tr0811_revised.pdf), which characterizes stability not using RIP or the canonical NSP, but still in terms of projections on the null space. The quantity of interest in that analysis is the value of (||x||_1/||x||_2) for x \in N(A), which is different from NSP...... thanks Giuseppe ! By the way, don't miss Giuseppe's very interesting entry (and the comments) on being an Intern at Enron. As a person who was nearby Houston at that time, it really looked like some of the people who worked there, either did not have a clue about the real business of Enron or were fooling themselves in believing that some part of their business was actually making money. I do not know if I was the only one, but I clearly remember something was terribly amiss when Jeffrey Skilling had an interview on the Houston Chronicle saying he wanted to retire to spend more time with his family, that was August 15th 2001. Returning to RIP vs NSP, I'll add on top of Giuseppe's comment that one of the most important step for an engineer to convince herself/himself that compressive sensing might be a good thing for her/him, revolves around trying to fit their known "measurement" device to the CS setting. An example of that was recently featured in TomoPIV meets Compressed Sensing by Stefania Petra and Christoph Schnörr or in the approach I am suggesting when we 'only' have integro-differential equations for which we have some knowledge about computing eigenfunctions fo said operators. Let us note also the fact that NSP can also include a more specific class of signals: positive signals. I think, at some point, I am also going to have to write down what some of you have been saying to me about the spectral gap of sparse measurement matrices in the RIP-1 setting and its potential relationship to the eigenfunctions of that operator. In particular my interest is in finding out if there is a relationship between the non-normality of a measurement operator and its potential to be a good/bad expander and how this influence their goodness or badness for doing CS with them. All this is highly speculative. Unrelated to this, two entries by David Brady got my attention recently: this one on superresolutionand this one of the cost of pixels. It looks to me that memory is still cheaper than a CMOS pixel ! This last one also reminded me of the beginning of the video by Ramesh Raskar at ECTV'08 ( Computational Photography: Epsilon to...

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: RIP vs NSP, Clarifications by Jared Tanner and Remi Gribonval

noreply@blogger.com (Igor) — Thu, 15 Oct 2009 05:01:00 +0000

Yesterday's post got some nice feedback. Two things: Thank you to Jared Tanner and Remi Gribonval for being kind enough to take some time off to answer yesterday's question.I suck as I have covered some of these issues/papers before but cannot seem to have a good grasp on this issue. Here are these answers: Jared Tanner was the first one to respond to yesterday's post: Dear Igor, I just read your Oct. 14th posting on Nuit Blanche where the following question was raised by Giuseppe Paleologo: "do you know how much weaker is the nullspace property vs. restricted isometry? Are there studies on this?" and your comment that "I am sure a specialist could clear that up for all of us by sending me a short E-mail." Here are a few take away "bullets", followed by a longer discussion. a) The RIP is a generic tool that can be used for many algorithms, whenever sparsity is the simplicity being exploited. b) The NSP is only applicable to sparse approximation questions where there is an "objective", such as l1 minimization. c) For l1 minimization, the NSP is a weaker assumption than the RIP, see "Compressed Sensing: How sharp is the RIP?" by Blanchard, Cartis, and Tanner. d) l1 minimization is the only setting where NSP and the RIP have been used to try to answer the same question, and is the only setting where it is fair to compare them. NSP is equivalent to l1 minimization recovery, and for this reason RIP implies the NSP, but not the other way around. e) Both methods can be used to imply stability. f) Many matrix ensembles are proven to have bounded RIP (Gaussian, Fourier, etc...). Many matrix ensembles are proven to have the NSP, see " Counting the faces of randomly-projected hypercubes and orthants, with applications" by Donoho and Tanner, to appear in Discrete and Computational Geometry. Now for the longer discussion: First of all, what is the NSP? Lets focus on the case of \min \|x\|_1 subject to Ax=b where there is an x_0 that is k-sparse with Ax_0=b and A is of size n by N. (Note the ordering k\lt n \lt N.) min l1 recovers x_0 if and only if thereis no vector \nu in the null space of A such that x_0+\nu is interior to (or intersects the boundary of) the l1 ball defined by \|x_0\|_1. (See image above depicting this, with the blue object being the l1 ball, the yellow circle being x_0 and the red line being the null space of A.) The NSP asks if this occurs for any x_0 that is k sparse, effectively moving x_0 to each of the 2^N (N \choose k) k-faces of the l1 ball. That the null space of A shifted to k-faces of the l1 ball never goes interior probably seems a very strict requirement, but it often holds. In fact, this notion isn't new, it is referred to as "neighborliness" in the convex polytope community. David L. Donoho analyzed this question in detail in 2005, precisely characterizing the values of (k,n,N) when this does and does not hold, see "Neighborly Polytopes and Sparse Solutions of Underdetermined Linear Equations." How does this compare with RIP? First of all, RIP has nothing to do with l1 minimization, but is clearly a natural property to desire in sparse approximation. This is both the strength and weakness of the RIP. It has been used to prove convergence results for many algorithms, including many for which the null space property would give no information. However, because it is a general tool, the RIP based conditions are generally very restrictive. There is only one venue where it is appropriate to directly compare the null space property and the RIP, this is the recovery results for l1 minimization where both can be used. Not surprisingly, the null space results derived by Donoho are much weaker than associated RIP based results. This raises a very related point, how does one read RIP based results? When is it true that RIP constants of order 2k are less then 0.45? (See Foucart and Lai, ACHA 2009, pages 395-407 for this l1 recovery condition.) How much more restrictive is it to require...

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: RIP vs NSP, Deterministic Sensing Matrices with Statistical Isometry Property , Modified Basis Pursuit Denoising,

noreply@blogger.com (Igor) — Wed, 14 Oct 2009 05:01:00 +0000

When listening to the beginning of this video entitled Gutenberg and the Monks, Seth Godin introduces the subject with this amusing little story: So it's a few hundred year ago and one the most famous German of all time says "I have this really cool thing, I have invented it, it's called the printing press and what we can do is print a lots of copies and ship them all around the country they can put them on display and when they don't sell them they can ship them back and we'll shred them and then we can print more copies." And I would imagine a conversation when he announced this and the monks said: "Well, that's all well and good but will this impact our ability to sit in a dark quiet abbey and do calligraphy all day ?" To which he responded "Well it doesn't really help your ability to do calligraphy all day, and in fact it's a totally different way of going about doing what you do." and in response most of the monks, my guess, said: "Well we are really busy let us know how it goes." I cannot but help thinking that you could replace some of these words with compressive sensing if instead of looking at increment of current technologies, CS were to be judiciously applied to new hardware. The new hardware must absolutely bring a new dimension to the data gathering process and its eventual use. So much so that the current technology players would have to look at it and say in unison: Well we are really busy let us know how it goes. Giuseppe Paleologo on Twitter, asks the following burning question: @igorcarron do you know how much weaker is the nullspace property vs. restricted isometry? Are there studies on this? #compressedsensingMy recollection is that there isn't, however, there seems to be that there is an issue about whether one property is stronger than the other (especially considering that there seems to be different definition for the Null Space Property). See this recent entry for a view on this. In all, I think somebody ought to write a paper on this as it clearly is an issue some people (including me) would like to have a closure on. Then again, I am sure a specialist could clear that up for all of us by sending me a short E-mail. I'll make sure it gets wide publicity. Checking for RIP is hard, this is why some are looking at building deterministic sensing matrices with some similar property as shown in Construction of a Large Class of Deterministic Sensing Matrices that Satisfy a Statistical Isometry Property by Robert Calderbank, Stephen Howard, Sina Jafarpour. The abstract reads: Compressed Sensing aims to capture attributes of $k$-sparse signals using very few measurements. In the standard Compressed Sensing paradigm, the $\m\times \n$ measurement matrix $\A$ is required to act as a near isometry on the set of all $k$-sparse signals (Restricted Isometry Property or RIP). Although it is known that certain probabilistic processes generate $\m \times \n$ matrices that satisfy RIP with high probability, there is no practical algorithm for verifying whether a given sensing matrix $\A$ has this property, crucial for the feasibility of the standard recovery algorithms. In contrast this paper provides simple criteria that guarantee that a deterministic sensing matrix satisfying these criteria acts as a near isometry on an overwhelming majority of $k$-sparse signals; in particular, most such signals have a unique representation in the measurement domain. Probability still plays a critical role, but it enters the signal model rather than the construction of the sensing matrix. We require the columns of the sensing matrix to form a group under pointwise multiplication. The construction allows recovery methods for which the expected performance is sub-linear in $\n$, and only quadratic in $\m$; the focus on expected performance is more typical of mainstream signal processing than the worst-case analysis that prevails in standard Compressed Sensing. Our framework encompasses many families of deterministic...

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: Model-Based Compressive Sensing

noreply@blogger.com (Igor) — Tue, 13 Oct 2009 05:01:00 +0000

Woohoo. If you recall, Model-based compressive sensing is a way of acquiring less compressive sensing signals than usual by using the tree-like structure of images in wavelet bases. The authors at Rice Richard Baraniuk, Volkan Cevher, Marco Duarte, Chinmay Hegde, Michael Wakin have written the following papers on it (Preprint, SPARS 2009, CISS 2009, NIPS 2008, ICASSP 2008, SPARS 2005). They have released the attendant toolbox. From the website: The standard compressive sensing (CS) theory dictates that robust signal recovery is possible from $M=O(K\log(N/K))$ measurements. We demonstrate that it is possible to substantially decrease $M$ without sacrificing robustness by leveraging more realistic signal models that go beyond simple sparsity and compressibility by including dependencies between values and locations of the signal coefficients. We have designed algorithms that enable fast recovery of piecewise smooth signals - sparse signals that have a distinct "connected tree" structure in the wavelet domain. Our Tree Matching Pursuit (TMP) algorithm significantly reduces the search space of the traditional Matching Pursuit greedy algorithm, resulting in a substantial decrease in computational complexity for recovering piecewise smooth signals. Our Hidden Markov Tree-based Reweighted $\ell_1$-norm minimization algorithm leverages the probabilistic model for wavelet-sparse signals to enable a reduction on the number of measurements necessary for recovery. An additional advantage of these algorithms is that they perform an implicit regularization to combat noise in the reconstruction. We also propose a union-of-subspaces model-based CS theory that parallels the conventional theory and provides concrete guidelines on how to create model-based recovery algorithms with provable performance guarantees. For some well-suited signal models, we can provably offer robust recovery from just $M=O(K)$ measurements.

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: Wavefront Coding for Random Lens Imagers ?

noreply@blogger.com (Igor) — Sun, 11 Oct 2009 18:51:00 +0000

Do you recall that question I asked a while back to Rich Baraniuk annd Justin Romberg about the reason why the soccer ball image from the single pixel camera was Ok but still kind of blurry (this was a question initially asked by an anonymous commenter on the blog) ? Do you recall the so-so quality of the reconstruction of the random lens imager ? Maybe part of the issue is that, in either cases, the light wavefront phase was not considered in the calibration process. Indeed, if you recall the calibration process of the random lens imager, it does not into account for this parameter: In a totally different area, Allard Mosk and Ivo Vellekoop [1] [2] are concerned, among other things, with light delivery in human tissues. One of the problems with human tissue is its extraordinary diffusivity. Some folks spent much time trying to compute light dispersion through these tissues in order to detect specific cancers or known markers and so forth. In effect, they either are solving an inverse problem with the diffusion equation and some are even heroic to the point of doing it with the full transport (or radiative transfer) equation. In the problem of delivering light to a specific area inside the body, one has to control the forward problem. In their recent publication [1][2] Allard Mosk and Ivo Vellekoop show that by modulating the phase of an incoming light beam through the use of an SLM they can rectify the direction of the light after it has gone through a random medium (also called 'opaque lens') as shown in the diagram below: In their more recent paper, Ivo Vellekoop, A. Lagendijk and Allard Mosk have essentially achieved a higher focusing capability than what would be offered by a simple lens thanks to the use of a random medium. This is explained in their recent Exploiting disorder for perfect focusing. The abstract reads: We demonstrate experimentally that disordered scattering can be used to improve, rather than deteriorate, the focusing resolution of a lens. By using wavefront shaping to compensate for scattering, light was focused to a spot as small as one tenth of the diraction limit of the lens. We show both experimentally and theoretically that it is the scattering medium, rather than the lens, that determines the width of the focus. Despite the disordered propagation of the light, the prole of the focus was always exactly equal to the theoretical best focus that we derived. One cannot escape the similarities between these figures and the ones above for the random lens imager. Figure 2.a is the same beam of light through a simple lens, Figure 2.b, is the random projection of the same single beam of light after it has gone through the random/opaque material. Figure 2.d is the configuration of the SLM that allows the initial beam of light to be focused. Figure 2.c is the resulting beam of light modulated with the SLM configuration in 2.d after it has gone through the random/opaque material. In other words, Figure 2.b is the random projection of a dirac like input in about the same way as in the Random Lens imager case. What is very interesting from this paper is that they have an analog algorithm that allows them to go through a series of SLM configurations that eventually provides a single focused beam. For any random medium, they can find a certain SLM configuration so that a focused beam comes out on the outside. In effect, they are solving a calibration issue. In the random lens imager case, calibration is performed by sending several coded signals (not phase coded) and by gathering their responses. This collection of responses is then used to produce a dictionary. The dictionary is then used to build future images obtained from the random lens imager. What this paper shows is that the random medium provides phase modulation and that any random lens imager should need a calibration step that includes some phase information. Other cameras designs that are either affected by this issue or are solving...

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: Video of Dror Baron at Google on CS-BP

noreply@blogger.com (Igor) — Sun, 11 Oct 2009 05:01:00 +0000

As an add-on to the last entry, Dror Baron just gave a talk at Google. The belief propagation algorithm is explained starting here. At 1 hour into the talk, Dror and Muthu briefly try to evaluate how a new algorithm (different from BP) fares with regards to the group testing based reconstruction solvers. Dror then goes on to explain some of the differences between the generic Compressed Sensing setting and that found in Finance where Hedge funds or high frequency traders are trying to devise the future of a stock price. The video will be added to the compressive sensing video page.

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: LP Decoding meets LP Decoding: A Connection between Channel Coding and Compressed Sensing, A Q&A with Dror Baron and Dongning Guo/ Two jobs

noreply@blogger.com (Igor) — Fri, 09 Oct 2009 05:01:00 +0000

Baam!...Today we have some deep impact stuff. First, recall that LCROSS will smash on the Moon in exactly six hours and thirty minutes (at 6:31 CST or 12:31 GMT) and you can watch it live. Let us note that it was re-targeted thanks to the recent observations of the Japanese Kaguya probe. Second, we have a new paper, a Q&A with authors of another and two job offers. Before all that, there is an interview by Kareem Carr of Terry Tao and how he does it all (including the blogging thing). Israel Gelfand passed away, I am sure he is the one who gave his name to the Gelfand's width, a subject related to CS. Terry Tao has an entry on him. Lei Yu, Laurent Jacques, Dirk Lorenz agree that this paper answers Angshul Majumdar's question of yesterday. Dirk also mentions another paper. Thanks guys! The second question of yesterday's entry might find an answer in the first job offer at the end of this entry. Let's explore the deep impact stuff now. By the way the first article might answer a recent commenter's question on Terry's blog. Here it is: LP Decoding meets LP Decoding: A Connection between Channel Coding and Compressed Sensing by Alexandros Dimakis and Pascal Vontobel. The abstract reads: This is a tale of two linear programming decoders, namely channel coding linear programming decoding (CCLPD) and compressed sensing linear programming decoding (CS-LPD). So far, they have evolved quite independently. The aim of the present paper is to show that there is a tight connection between, on the one hand, CS-LPD based on a zero-one measurement matrix over the reals and, on the other hand, CC-LPD of the binary linear code that is obtained by viewing this measurement matrix as a binary parity-check matrix. This connection allows one to translate performance guarantees from one setup to the other. The slides of the presentation can be found here. Alex summed it nicely for me in a short email conversation:...The paper connects the channel coding problem to compressed sensing. The result is if a binary code corrects k errors under Feldman's LP decoding (that is a LP relaxation of the channel coding problem ) then the same (0,1) matrix, (taken over the reals) recovers all k-sparse signals. Further if it corrects a given set of errors, you can recover the same sparsity in a signal, and there are channel coding conditions that correspond to l1/l1 robust recovery and l2/l1 robust recovery. This means that you can use error correcting code parity check matrices as measurement matrices and you can transfer theoretical results from coding theory into compressed sensing Thanks Alex ! I was struck by Dongning Guo, Dror Baron, and Shlomo Shamai's paper (mentionned here) entitled A Single-letter Characterization of Optimal Noisy Compressed Sensing. and specifically these excerpts: "...What can one infer about an individual element of the sparse signal based on the measurements?...Taking another perspective, we can say that whatever one can infer about an input element of the sparse signal based on the measurements is asymptotically identical to what one can infer about the same element if all other input elements were zero, but the measurements were noisier...The single-letter characterization of the marginal posterior distribution leads to a simple characterization of all other elemental metrics of the CS problem, such as the minimum mean-square error (MMSE), the error probability, the entropy, etc. This result is convenient for many practical purposes, for example, to determine the number of measurements and the SNR required for achieving a certain quality of reconstruction. We note that the results in this paper also advance the understanding of the fundamental nature of noisy CS by describing a boundary between what is physically possible and what is not. Another sharp characterization of phase transition deals only with noiseless measurements [3], [4]. The result in this paper is thus sharper than many other results on...

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: Questions on IST, Audio CS and anoter GPR

noreply@blogger.com (Igor) — Thu, 08 Oct 2009 11:42:00 +0000

I get often different questions from different types of readers and sometimes I cannot think of an answer right away and I find somebody who can or I blog about it. Today I have two questions, if you have an answer, please feel free to answer in the comment or send me a blurb. In the latter case, please also let me know if you want me to use your name: Angshul Majumdar asked me the following question: Can you please refer a paper, where it is being derived that the Iterative Soft Thresholding is actually solving the l1 regularized least squares problem? Any specialists out there can help ? Another reader who shall remain nameless asked the following question: I have a problem about compressed sensing. My major project is "compressed sensing of audio signal using multiple sensor". Can you help me about method of compressed sensing audio using multiple sensor ? It looks like an assignment of some sort but I very glad this person asked the question as this was a subject of a conversation I had with some of you including Bob Sturm. The issue at hand is really interesting in that recording is a well known business and plenty of actors in that field have very different offerings in terms of low and high end equipment. So the idea is really, how does a Compressed Sensing method of acquiring an audio signal become disruptive compared to the well established industry ? My take and it is a crazy one, is to see if we can let Nature help. Instead of Imaging with Nature (TM), what about performing Audio with Nature. Any thoughts from any of you on this would be very much welcome. By the way, I am half kidding when I say that we ought to be thinking on how we could perform audio recording on a pottery which we all know is a myth. In a different area, yesterday, I mentioned a Step-Frequency Radar with Compressive Sampling (SFR-CS) concept out of the Drexel. As an anonymous reader pointed out, the claim of being the first might not be entirely accurate. From the comment: The authors say "The application of compressive sampling to narrow-band radar systems was recently investigated in [2], [3] and [4], [5], and [6]. The application of CS on SFR has not been investigated before." Hadn't Gurbuz, McLellan and Scott done GPR using stepped frequency radar in "A Compressive Sensing Data Acquisition and Imaging Method for Stepped Frequency GPRs," IEEE Transactions in Signal Processing, vol. 57, issue 7, pp. 2640-2650 (2009) That paper is here behind a paywall. I had heard about it only through a talk given at Rice. Thank you anonymous reader !

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]

CS: Step-Frequency Radar with Compressive Sampling (SFR-CS)

noreply@blogger.com (Igor) — Wed, 07 Oct 2009 07:17:00 +0000

Here is an application of compressive sensing to a specific type of radar. The description of the approach is given in Step-Frequency Radar with Compressive Sampling (SFR-CS) by Sagar Shah, Yao Yu, Athina Petropulu. The abstract reads: Step-frequency radar (SFR) is a high resolution radar approach, where multiple pulses are transmitted at different frequencies, covering a wide spectrum. The obtained resolution directly depends on the total bandwidth used, or equivalently, the number of transmitted pulses. This paper proposes a novel SFR system, namely SFR with compressive sampling (SFRCS), that achieves the same resolution as a conventional SFR, while using significantly reduced bandwidth, or equivalently, transmitting significantly fewer pulses. This bandwidth reduction is accomplished by employing compressive sampling ideas and exploiting the sparseness of targets in the range velocity space. I'll add it to the Compressive Sensing Hardware page shortly.

[ Be sure to visit the blog for a corrected version of this article and for the comments. Thanks ]