Tuesday, November 09, 2010

CS: Imaging heavens and earth




 You do remember the PACS camera that is on-board Herschel and for which some compressed sensing encoding have been tried (I still have not heard of the results). Anyway, that camera was used to image the encounter between the EPOXI spacecraft and Hartley-2. talk about a sparse scene ! The small dot is the EPOXI spacecraft.

You probably recall the Integral Pixel Camera, well on of the authors, Nathan Jacobs, just came out with an instance of Imaging With Nature in: Using Cloud Shadows to Infer Scene Structure and Camera Calibration by Nathan Jacobs, Brian Bies, Robert Pless. The abstract reads:
We explore the use of clouds as a form of structured lighting to capture the 3D structure of outdoor scenes observed over time from a static camera. We derive two cues that relate 3D distances to changes in pixel intensity due to clouds shadows. The first cue is primarily spatial, works with low frame-rate time lapses, and supports estimating focal length and scene structure, up to a scale ambiguity. The second cue depends on cloud motion and has a more complex, but still linear, ambiguity. We describe a method that uses the spatial cue to estimate a depth map and a method that combines both cues. Results on time lapses of several outdoor scenes show that these cues enable estimating scene geometry and camera focal length.

My emphasis, I also noted from the paper something I was not aware of :
The methods we describe are a valuable addition to the emerging toolbox of automated outdoor-camera calibration techniques.
The shape from cloud site is here. If you want to see the code, send an email to Nathan!

The following papers and presentations are coming from Felix Herrmann's group. The most intriguing idea is the use of they seem to call "multiples" to probe further the soil. It's a way to use diffusion to increase the mixing of  the data and thereby producing "better" compressed measurements. It is no surprise that these effects are considered bad until today where compressive sensing give a theoretical reasoning as to why these multiples should be used.

Full-waveform inversion relies on the collection of large multi-experiment data volumes in combination with a sophisticated back-end to create high-fidelity inversion results. While improvements in acquisition and inversion have been extremely successful, the current trend of incessantly pushing for higher quality models in increasingly complicated regions of the Earth reveals fundamental shortcomings in our ability to handle increasing problem size numerically. Two main culprits can be identified. First, there is the so-called ``curse of dimensionality'' exemplified by Nyquist's sampling criterion, which puts disproportionate strain on current acquisition and processing systems as the size and desired resolution increases. Secondly, there is the recent ``departure from Moore's law'' that forces us to lower our expectations to compute ourselves out of this. In this paper, we address this situation by randomized dimensionality reduction, which we adapt from the field of compressive sensing. In this approach, we combine deliberate randomized subsampling with structure-exploiting transform-domain sparsity promotion. Our approach is successful because it reduces the size of seismic data volumes without loss of information. With this reduction, we compute Newton-like updates at the cost of roughly one gradient update for the fully-sampled wavefield.
Seismic imaging typically begins with the removal of multiple energy in the data, out of fear that it may introduce erroneous structure. However, seismic multiples have effectively seen more of the earth's structure, and if treated correctly can potential supply more information to a seismic image compared to primaries. Past approaches to accomplish this leave ample room for improvement; they either require extensive modification to standard migration techniques, rely too much on prior information, require extensive pre-processing, or resort to full-waveform inversion. We take some valuable lessons from these efforts and present a new approach balanced in terms of ease of implementation, robustness, efficiency and well-posedness, involving a sparsity-promoting inversion procedure using standard Born migration and a data-driven multiple modeling approach based on the focal transform.

During this presentation, I will talk about how recent results from compressive sensing and sparse recovery can be used to solve problems in exploration seismology where incomplete sampling is ubiquitous. I will also talk about how these ideas apply to dimensionality reduction of full-waveform inversion by randomly phase encoded sources.


Randomized full-waveform inversion: a dimensionality-reduction approach. by Peyman P. Moghaddam and Felix J. Herrmann. The abstract reads:
Full-waveform inversion relies on the collection of large multi-experiment data volumes in combination with a sophisticated back-end to create high-fidelity inversion results. While improvements in acquisition and inversion have been extremely successful, the current trend of incessantly pushing for higher quality models in increasingly complicated regions of the Earth reveals fundamental shortcomings in our ability to handle increasing problem sizes numerically. Two main culprits can be identified. First, there is the so-called ``curse of dimensionality'' exemplified by Nyquist's sampling criterion, which puts disproportionate strain on current acquisition and processing systems as the size and desired resolution increases. Secondly, there is the recent ``departure from Moore's law'' that forces us to develop algorithms that are amenable to parallelization. In this paper, we discuss different strategies that address these issues via randomized dimensionality reduction.
Stabilized estimation of primaries via sparse inversion by Tim Lin, and Felix J. Herrmann. The abstract reads:

Recent works on surface-related multiple removal include a direct estimation method proposed by van Groenestijn and Verschuur (2009), where under a sparsity assumption the primary impulse response is determined directly from a data-driven wavefield inversion process called Estimation of Primaries by Sparse Inversion (EPSI). The authors have shown that this approach is superior to traditional estimationsubtraction processes such as SRME on shallow bottom marine data, where by expanding the model to simultaneously invert for the near-offset traces, which are not directly available in most situation but are observable in the data multiples, a large improvement over Radon interpolation is demonstrated. One of the major roadblocks to the widespread adoption of EPSI is that one must have precise knowledge of a time-window that contains multiple-free primaries during each update. There is some anecdotal evidence that the inversion result is unstable under errors in the time-window length, a behaviour that runs contrary to the strengths of EPSI and diminishes its effectiveness for shallow-bottom marine data where multiples are closely spaced. Moreover, due to the nuances involved in regularizing the model impulse response in the inverse problem, the EPSI approach has an additional number of inversion parameters to choose and often also does not often lead to a stable solution under perturbations to these parameters. We show that the specific sparsity constraint on the EPSI updates lead to an inherently intractable problem, and that the time-window and other inversion variables arise as additional regularizations on the unknown towards a meaningful solution. We furthermore suggest a way to remove almost all of these parameters via a L0 to L1 convexification, which stabilizes the inversion while preserving the crucial sparsity assumption in the primary impulse response model. 
Randomized sampling strategies. by Felix J. Herrmann. The abstract reads:
Seismic exploration relies on the collection of massive data volumes that are subsequently mined for information during seismic processing. While this approach has been extremely successful in the past, the current trend towards higher quality images in increasingly complicated regions continues to reveal fundamental shortcomings in our workflows for high-dimensional data volumes. Two causes can be identified.. First, there is the so-called ``curse of dimensionality'' exemplified by Nyquist's sampling criterion, which puts disproportionate strain on current acquisition and processing systems as the size and desired resolution of our survey areas continues to increase. Secondly, there is the recent ``departure from Moore's law'' that forces us to lower our expectations to compute ourselves out of this curse of dimensionality. In this paper, we offer a way out of this situation by a deliberate randomized subsampling combined with structure-exploiting transform-domain sparsity promotion. Our approach is successful because it reduces the size of seismic data volumes without loss of information. As such we end up with a new technology where the costs of acquisition and processing are no longer dictated by the size of the acquisition but by the transform-domain sparsity of the end-product.


Full-waveform inversion relies on the collection of large multi-experiment data volumes in combination with a sophisticated back-end to create high-fidelity inversion results. While improvements in acquisition and inversion have been extremely successful, the current trend of incessantly pushing for higher quality models in increasingly complicated regions of the Earth continues to reveal fundamental shortcomings in our ability to handle the ever increasing problem size numerically. Two causes can be identified as the main culprits responsible for this barrier. First, there is the so-called ``curse of dimensionality'' exemplified by Nyquist's sampling criterion, which puts disproportionate strain on current acquisition and processing systems as the size and desired resolution of our survey areas continues to increase. Secondly, there is the recent ``departure from Moore's law'' that forces us to lower our expectations to compute ourselves out of this. In this paper, we address this situation by randomized dimensionality reduction, which we adapt from the field of compressive sensing. In this approach, we combine deliberate randomized subsampling with structure-exploiting transform-domain sparsity promotion. Our approach is successful because it reduces the size of seismic data volumes without loss of information. With this reduction, we compute Newton-like updates at the cost of roughly one gradient update for the fully-sampled wavefield.

Sub-Nyquist sampling and sparsity: getting more information from fewer samples by Felix J. Herrmann. The abstract reads:
Many seismic exploration techniques rely on the collection of massive data volumes. While this approach has been extremely successful in the past, current efforts toward higher resolution images in increasingly complicated regions of the Earth continue to reveal fundamental shortcomings in our workflows. Chiefly amongst these is the so-called ``curse of dimensionality'' exemplified by Nyquist's sampling criterion, which disproportionately strains current acquisition and processing systems as the size and desired resolution of our survey areas continues to increase. In this presentation, we offer an alternative sampling method leveraging recent insights from compressive sensing towards seismic acquisition and processing of severely under-sampled data. The main outcome of this approach is a new technology where acquisition and processing related costs are no longer determined by overly stringent sampling criteria, such as Nyquist. At the heart of our approach lies randomized incoherent sampling that breaks subsampling related interferences by turning them into harmless noise, which we subsequently remove by promoting transform-domain sparsity. Now, costs no longer grow significantly with resolution and dimensionality of the survey area, but instead depend on transform-domain sparsity only. Our contribution is twofold. First, we demonstrate by means of carefully designed numerical experiments that compressive sensing can successfully be adapted to seismic exploration. Second, we show that accurate recovery can be accomplished for compressively sampled data volumes sizes that exceed the size of conventional transform-domain data volumes by only a small factor. Because compressive sensing combines transformation and encoding by a single linear encoding step, this technology is directly applicable to acquisition and to dimensionality reduction during processing. In either case, sampling, storage, and processing costs scale with transform-domain sparsity. Many seismic exploration techniques rely on the collection of massive data volumes. While this approach has been extremely successful in the past, current efforts toward higher resolution images in increasingly complicated regions of the Earth continue to reveal fundamental shortcomings in our workflows. Chiefly amongst these is the so-called ``curse of dimensionality'' exemplified by Nyquist's sampling criterion, which disproportionately strains current acquisition and processing systems as the size and desired resolution of our survey areas continues to increase. In this presentation, we offer an alternative sampling method leveraging recent insights from compressive sensing towards seismic acquisition and processing of severely under-sampled data. The main outcome of this approach is a new technology where acquisition and processing related costs are no longer determined by overly stringent sampling criteria, such as Nyquist. At the heart of our approach lies randomized incoherent sampling that breaks subsampling related interferences by turning them into harmless noise, which we subsequently remove by promoting transform-domain sparsity. Now, costs no longer grow significantly with resolution and dimensionality of the survey area, but instead depend on transform-domain sparsity only. Our contribution is twofold. First, we demonstrate by means of carefully designed numerical experiments that compressive sensing can successfully be adapted to seismic exploration. Second, we show that accurate recovery can be accomplished for compressively sampled data volumes sizes that exceed the size of conventional transform-domain data volumes by only a small factor. Because compressive sensing combines transformation and encoding by a single linear encoding step, this technology is directly applicable to acquisition and to dimensionality reduction during processing. In either case, sampling, storage, and processing costs scale with transform-domain sparsity.

Credit: ESA/Herschel/HssO Consortium
Credit: NASA/JPL-Caltech/UMD

Sunday, November 07, 2010

CS; Performance Analysis of Spectral Clustering on Compressed, Incomplete and Inaccurate Measurements, A Signal-agnostic Compressed Sensing Acquisition System for Wireless and Implantable Sensors, The Lasso under Heteroscedasticity, CS-Orion

We have three papers today, one of which (the last one) chose a title that sounds a little different:
Spectral clustering is one of the most widely used techniques for extracting the underlying global structure of a data set. Compressed sensing and matrix completion have emerged as prevailing methods for efficiently recovering sparse and partially observed signals respectively. We combine the distance preserving measurements of compressed sensing and matrix completion with the power of robust spectral clustering. Our analysis provides rigorous bounds on how small errors in the affinity matrix can affect the spectral coordinates and clusterability. This work generalizes the current perturbation results of two-class spectral clustering to incorporate multi-class clustering with k eigenvectors. We thoroughly track how small perturbation from using compressed sensing and matrix completion affect the affinity matrix and in succession the spectral coordinates. These perturbation results for multi-class clustering require an eigengap between the kth and (k+1)th eigenvalues of the affinity matrix, which naturally occurs in data with k well-defined clusters. Our theoretical guarantees are complemented with numerical results along with a number of examples of the unsupervised organization and clustering of image data.

A signal-agnostic compressed sensing (CS) acquisition system is presented that addresses both the energy and telemetry bandwidth constraints of wireless sensors. The CS system enables continuous data acquisition and compression that are suitable for a variety of biophysical signals. A hardware efficient realization of the CS sampling demonstrates data compression up to 40x on an EEG signal while maintaining low perceptual loss in the reconstructed signal. The proposed system also simultaneously relaxes the noise and resolution constraints of the analog front end (AFE) and ADC by nearly an order of magnitude. The CS sampling hardware is implemented in a 90 nm CMOS process and consumes 1.9 μW at 0.6 V and 20 kS/s.

The Lasso under Heteroscedasticity by Jinzhu Jia, Karl Rohe, Bin Yu. The abstract reads:
The performance of the Lasso is well understood under the assumptions of the standard linear model with homoscedastic noise. However, in several applications, the standard model does not describe the important features of the data. This paper examines how the Lasso performs on a non-standard model that is motivated by medical imaging applications. In these applications, the variance of the noise scales linearly with the expectation of the observation. Like all heteroscedastic models, the noise terms in this Poisson-like model are \textit{not} independent of the design matrix.
More specifically, this paper studies the sign consistency of the Lasso under a sparse Poisson-like model. In addition to studying sufficient conditions for the sign consistency of the Lasso estimate, this paper also gives necessary conditions for sign consistency. Both sets of conditions are comparable to results for the homoscedastic model, showing that when a measure of the signal to noise ratio is large, the Lasso performs well on both Poisson-like data and homoscedastic data.
Simulations reveal that the Lasso performs equally well in terms of model selection performance on both Poisson-like data and homoscedastic data (with properly scaled noise variance), across a range of parameterizations. Taken as a whole, these results suggest that the Lasso is robust to the Poisson-like heteroscedastic noise.
Finally, there is a group funded by the EU that seems to focus on Compressed Sensing for Remote Imaging in Aerial and Terrestrial Surveillance. It is called CS-Orion.


Credit: NASA/JPL-Caltech/UMD, Epoxi, close encounter to Hartley 2

Saturday, November 06, 2010

CS / Imaging With Nature: A Galaxy Wide Single Pixel Camera

Following up on this entry, I went about and went looking for information. From this site here is description of gravitational lensing:



Gravitational lenses produce different shaped images depending on the shape of the lensing body. If the lens is spherical then the image appears as an Einstein ring (in other words as a ring of light) (top); if the lens is elongated then the image is an Einstein cross (it appears split into four distinct images) (middle), and if the lens is a galaxy cluster, like Abell 2218, then arcs and arclets (banana-shaped images) of light are formed (bottom). Image credit: ESA


The third graph is interesting and points to an instance of compressed sensing. If we knew exactly the galaxy cluster between the image and the receiver (the Earth) then, with the object moving in the back and several picture taken from Earth of that object through this galaxy cluster we would have an instance of compressive sensing. Since the Hubble is the only one to take that picture, the Hubble itself would act as an instance of a single pixel camera with the DMD replaced by a whole Galaxy. I just wonder when compressed sensing will be used in the different techniques used in weak lensing. (see the review on Cluster Weak Gravitational Lensing).
Additional interesting information on the subject include this page and this page. .

Blog and Feed readers

Here are the top ten blog entries for people coming directly to the blog:

and the top ten entries for the readers using their feedreaders:

Friday, November 05, 2010

Hartley 2. Wow.

As the last Shuttle launch is postponed for a month, a robotic mission (EPOXI) was doing the job of inimaginable wonder by taking a closeby photo a Hartley.2. Just wow.

If you recall EPOXI back two years ago, it took the shot in this entry: If you are looking at the Moon from this point of view, you are in a lot of trouble!

Ed Weiler the head of AA for the Science Mission Directorate at NASA, is amazed not just by the beautiful results but because the program: "somehow [it] survived peer review."

Credit: NASA

CS: A Real-Time Compressed Sensing-Based Personal Electrocardiogram Monitoring System, From Sparse Signals to Sparse Residuals for Robust Sensing

Here is more detail on the FISTA reconstruction algorithm running on a jailbroken iPhone. From Pierre Vandergheynst twitter's stream, the implementation that received so much attention in:
Wireless body sensor networks (WBSN) hold the promise to enable next-generation patient-centric tele-cardiology systems. A WBSN-enabled electrocardiogram (ECG) monitor consists of wearable, miniaturized and wireless sensors able to measure and wirelessly report cardiac signals to a WBSN coordinator, which is responsible for reporting them to the tele-health provider. However, state-of-the-art WBSN-enabled ECG monitors still fall short of the required functionality, miniaturization and energy efficiency. Among others, energy efficiency can be significantly improved through embedded ECG compression, which reduces airtime over energy-hungry wireless links. In this paper, we propose a novel real-time energy-aware ECG monitoring system based on the emerging compressed sensing (CS) signal acquisition/compression paradigm for WBSN applications. For the first time, CS is demonstrated as an advantageous real-time and energy-efficient ECG compression technique, with a computationally light ECG encoder on the state-of-the-art ShimmerTM wearable sensor node and a realtime decoder running on an iPhone (acting as a WBSN coordinator). Interestingly, our results show an average CPU usage of less than 5% on the node, and of less than 30% on the iPhone.
Here is the attendant video:








One of the key challenges in sensor networks is the extraction of information by fusing data from a multitude of distinct, but possibly unreliable sensors. Recovering information from the maximum number of dependable sensors while specifying the unreliable ones is critical for robust sensing. This sensing task is formulated here as that of finding the maximum number of feasible subsystems of linear equations, and proved to be NP-hard. Useful links are established with compressive sampling, which aims at recovering vectors that are sparse. In contrast, the signals here are not sparse, but give rise to sparse residuals. Capitalizing on this form of sparsity, four sensing schemes with complementary strengths are developed. The first scheme is a convex relaxation of the original problem expressed as a second-order cone program (SOCP). It is shown that when the involved sensing matrices are Gaussian and the reliable measurements are sufficiently many, the SOCP can recover the optimal solution almost surely. The second scheme is obtained by replacing the initial objective function with a concave one. The third and fourth schemes are tailored for noisy sensor data. The noisy case is cast as a combinatorial problem that is subsequently surrogated by a (weighted) SOCP. Interestingly, the derived cost functions fall into the framework of robust multivariate linear regression, while an efficient block-coordinate descent algorithm is developed for their minimization. The robust sensing capabilities of all schemes are verified by simulated tests.

Thursday, November 04, 2010

Robust Mathematical Modeling Example #1: Ground Motion Models for Probabilistic Seismic Hazard Analysis

 
I initially wanted to convey the difficulty of modeling physical systems by featuring some examples I knew something about early on the Robust Mathematical Modeling blog. Instead, a reader of the blog, Nicolas Kuehn kindly provided an example he is working on. Where is this discussion going ? I am not sure but I don't see discussions like these often on the web. Many disciplines in engineering and science are facing the same type of problems, a mild case of curse of dimensionality with nonlinear models and a dearth of expensive data.  There are currently 95 people reading the blog through an RSS feed and there is an accompanying LinkedIn group. The more I think about it, the more I think some of the machine learning techniques such as manifold learning ought to be investigated alongside the generic model building capabilities generally deployed with traditional Bayesian statistics. These methods should eventually be part of the bag of tools engineers and scientists in the trenches, use. I mean it's great to do classification on images, video and text but what about doing this for real data and making sense of them ? Do you want to be part of that discussion ? I thought so, invite your friends, they're welcome too...

Wednesday, November 03, 2010

CS: Deciphering subsampled data: adaptive compressive sampling as a principle of brain communication



[Update: From NASAWatch, Launch has been scrubbed for a Wednesday launch. Electrical issues need to be addressed so launch is now set for Thursday at 3:29 PM EDT. However with a 70% chance of violating the constraints for launch due to weather, it would appear Friday is the more likely day for launch.]

Today's paper is about an important problem (* see below for a definition of an important problem) . Not only it is not about reconstruction, it's not even about the measurement matrix as it is supposed to be unknown. I cannot wait to see how phase transition in the context of ACS (the following paper) could be a good model for the understanding of neurological diseases, but more importantly how this model could be used as a quantitative tool for correlation with other observed data (such as fMRI,...) Without further due here it is: Deciphering subsampled data: adaptive compressive sampling as a principle of brain communication by Guy Isely, Christopher J. Hillar, Friedrich T. Sommer. The abstract reads:
A new algorithm is proposed for a) unsupervised learning of sparse representations from subsampled measurements and b) estimating the parameters required for linearly reconstructing signals from the sparse codes. We verify that the new algorithm performs efficient data compression on par with the recent method of compressive sampling. Further, we demonstrate that the algorithm performs robustly when stacked in several stages or when applied in undercomplete or overcomplete situations. The new algorithm can explain how neural populations in the brain that receive subsampled input through fiber bottlenecks are able to form coherent response properties.

* I take the definition of an important problem from a talk by Richard Hamming which you may have seen at the end of my page:
....Let me warn you, `important problem' must be phrased carefully. The three outstanding problems in physics, in a certain sense, were never worked on while I was at Bell Labs. By important I mean guaranteed a Nobel Prize and any sum of money you want to mention. We didn't work on (1) time travel, (2) teleportation, and (3) antigravity. They are not important problems because we do not have an attack. It's not the consequence that makes a problem important, it is that you have a reasonable attack. That is what makes a problem important. When I say that most scientists don't work on important problems, I mean it in that sense. The average scientist, so far as I can make out, spends almost all his time working on problems which he believes will not be important and he also doesn't believe that they will lead to important problems.

The video above shows the launchpad of the Last Space Shuttle (STS-133), it is set to take off at 3:52 PM EST today.

Tuesday, November 02, 2010

CS: Dimensionality reduction using compressed sensing and its application to a large-scale visual recognition task, Yves Meyer tribute, Recovering Lost Sensor Data through Compressed Sensing, Prior estimate-based compressed sensing in parallel MRI


In the CS world, we have :Dimensionality reduction using compressed sensing and its application to a large-scale visual recognition task by Son Lam Phung, Fok Hing Chi Tivive, Abdesselam Bouzerdoumz, Jie Yang. The abstract reads:
This paper presents a novel algorithm for the dimensionality reduction which employs compressed sensing (CS) to improve the generalization capability of a classifier, especially for large-scale data. Compared to traditional dimensionality reduction methods, the proposed algorithm makes no use of the problem-dependent parameters, nor does it require additional computation for the eigenvalue decomposition like PCA or LDA. Mathematically, the derived algorithm regards the input features as the dictionary in CS, and selects the features that minimize the residual output error iteratively, thus the resulting features have a direct correspondence to the performance requirements of the given problem. Furthermore, the proposed algorithm can be regarded as a sparse classifier, which selects discriminative features and classifies the training data simultaneously. Experimentally, the CS-based algorithm is tested with a hierarchical visual pattern recognition architecture. The simulation results show that not only does the proposed method utilize only 25% of full features while achieving the test accuracy of the original full architecture, but also its performance is competitive when compared to existing dimensionality reduction methods.

Also, Gabriel Peyre let me know of a series of presentations in honor of Yves Meyer at ENS Cachan. I just found a presentation by Zainul Charbiwala entitled Recovering Lost Sensor Data through Compressed Sensing and behind a paywall, we also have: Prior estimate-based compressed sensing in parallel MRI. by Wu B, Millane RP, Watts R, Bones PJ. The abstract reads:
Two improved compressed sensing (CS)-based image reconstruction methods for MRI are proposed: prior estimate-based compressed sensing (PECS) and sensitivity encoding-based compressed sensing (SENSECS). PECS allows prior knowledge of the underlying image to be intrinsically incorporated in the image recovery process, extending the use of data sorting as first proposed by Adluru and DiBella (Int J Biomed Imaging 2008: 341648). It does so by rearranging the elements in the underlying image based on the magnitude information gathered from a prior image estimate, so that the underlying image can be recovered in a new form that exhibits a higher level of sparsity. SENSECS is an application of PECS in parallel imaging. In SENSECS, image reconstruction is carried out in two stages: SENSE and PECS, with the SENSE reconstruction being used as a image prior estimate in the following PECS reconstruction. SENSECS bypasses the conflict of sampling pattern design in directly applying CS recovery in multicoil data sets and exploits the complementary characteristics of SENSE-type and CS-type reconstructions, hence achieving better image reconstructions than using SENSE or CS alone. The characteristics of PECS and SENSECS are investigated using experimental data.
.

Monday, November 01, 2010

CS: Graphical Models for CS, The Effect of Spatial Coupling on Compressive Sensing, Taken's Embedding, Super Greedy Algo, Chaotic Sensing Matrix for Compressive Sensing and abstracts of a past meeting

Today, we have a fresh arrival of new papers/preprints and the abstracts of a conference that took place in Germany back in October. The first paper shows us how 'fast' this new AMP solvers are (I'd like to get my hands on one of those), then, we have a paper that seems to cross the Donoho-Tanner phase transition . Then we have some results on Taken's embedding, a super greedy algorithm (that might taker a stab at overcomplete dictionaries) and finally some papers that use chaotic systems to produce measurement matrices that seem very suited for compressive sensing.

This paper surveys recent work in applying ideas from graphical models and message passing algorithms to solve large scale regularized regression problems. In particular, the focus is on compressed sensing reconstruction via ℓ1 penalized least-squares (known as LASSO or BPDN). We discuss how to derive fast approximate message passing algorithms to solve this problem. Surprisingly, the analysis of such algorithms allows to prove exact high-dimensional limit results for the LASSO risk.
This paper will appear as a chapter in a book on ‘Compressed Sensing’ edited by Yonina Eldar
and Gitta Kutynok.

Recently, it was observed that spatially-coupled LDPC code ensembles approach the Shannon capacity for a class of binary-input memoryless symmetric (BMS) channels. The fundamental reason for this was attributed to a "threshold saturation" phenomena derived by Kudekar, Richardson and Urbanke. In particular, it was shown that the belief propagation (BP) threshold of the spatially coupled codes is equal to the maximum a posteriori (MAP) decoding threshold of the underlying constituent codes. In this sense, the BP threshold is saturated to its maximum value. Moreover, it has been empirically observed that the same phenomena also occurs when transmitting over more general classes of BMS channels. In this paper, we show that the effect of spatial coupling is not restricted to the realm of channel coding. The effect of coupling also manifests itself in compressed sensing. Specifically, we show that spatially-coupled measurement matrices have an improved sparsity to sampling threshold for reconstruction algorithms based on verification decoding. For BP-based reconstruction algorithms, this phenomenon is also tested empirically via simulation. At the block lengths accessible via simulation, the effect is quite small and it seems that spatial coupling is not providing the gains one might expect. Based on the threshold analysis, however, we believe this warrants further study.
Takens' Embedding Theorem remarkably established that concatenating M previous outputs of a dynamical system into a vector (called a delay coordinate map) can be a one-to-one mapping of a low-dimensional attractor from the system state-space. However, Takens' theorem is fragile because even small imperfections can induce arbitrarily large errors in the attractor representation. We extend Takens' result to establish explicit, non-asymptotic sufficient conditions for a delay coordinate map to form a stable embedding in the restricted case of linear dynamical systems and observation functions. Our work is inspired by the field of Compressive Sensing (CS), where results guarantee that low-dimensional signal families can be robustly reconstructed if they are stably embedded by a measurement operator. However, in contrast to typical CS results, i) our sufficient conditions are independent of the size of the ambient state space (N), and ii) some system and measurement pairs have fundamental limits on the conditioning of the embedding (i.e., how close it is to an isometry), meaning that further measurements beyond some point add no further significant value. We use several simple simulations to explore the conditions of the main results, including the tightness of the bounds and the convergence speed of the stable embedding.

We study greedy-type algorithms such that at a greedy step we pick several dictionary elements contrary to a single dictionary element in standard greedy-type algorithms. We call such greedy algorithms {\it super greedy algorithms}. The idea of picking several elements at a greedy step of the algorithm is not new. Recently, we observed the following new phenomenon. For incoherent dictionaries these new type of algorithms (super greedy algorithms) provide the same (in the sense of order) upper bound for the error as their analogues from the standard greedy algorithms. The super greedy algorithms are computationally simpler than their analogues from the standard greedy algorithms. We continue to study this phenomenon.

Compressive Sensing (CS) is a new sampling theory which allows signals to be sampled at sub-Nyquist rate without loss of information. Fundamentally, its procedure can be modeled as a linear projection on one specific sensing matrix, which, in order to guarantee the information conservation, satisfies Restricted Isometry Property (RIP). Ordinarily, this matrix is constructed by the Gaussian random matrix or Bernoulli random matrix. In previous work, we have proved that the typical chaotic sequence - logistic map can be adopted to generate the sensing matrix for CS. In this paper, we show that Toeplitz-structured matrix constructed by chaotic sequence is sufficient to satisfy RIP with high probability. With the Toeplitz-structured Chaotic Sensing Matrix (TsCSM), we can easily build a filter with small number of taps. Meanwhile, we implement the TsCSM in compressive sensing of images.
Compressive sensing is a new methodology to capture signals at sub-Nyquist rate. To guarantee exact recovery from compressed measurements, one should choose specific matrix, which satisfies the Restricted Isometry Property (RIP), to implement the sensing procedure. In this letter, we propose to construct the sensing matrix with chaotic sequence following a trivial method and prove that with overwhelming probability, the RIP of this kind of matrix is guaranteed. Meanwhile, its experimental comparisons with Gaussian random matrix, Bernoulli random matrix and sparse matrix are carried out and show that the performances among these sensing matrix are almost equal.


# "Variational Inequalities and Morozov\'s Discrepancy Principle"
Anzengruber, Stephan
Variational Inequalities can be viewed as generalizations of classical source conditions and structural assumptions. In this talk we will show how, for non-linear ill-posed problems, Variational Inequalities can be combined with Morozov\'s Discrepancy principle to obtain convergence rates for Tikhonov Regularization with $\ell_p$ penalties, $p \geq 1$, which are well-known to promote sparsity.
# "Non-uniform sparse recovery with Gaussian matrices"
Ayaz, Ulas
Compressive sensing predicts that sufficiently sparse vectors can be recovered from highly incomplete information. Efficient recovery methods such as L1-minimization find the sparsest solution to certain systems of equations. Random matrices have become a popular choice for the measurement matrix. Indeed, near-optimal uniform recovery results have been shown for such matrices. In this note we focus on nonuniform recovery using Gaussian random matrices and `1-minimization. We provide a condition on the number of samples in terms of the sparsity and the signal length which guarantees that a fixed sparse signal can be recovered with a random draw of the matrix using L1- minimization. The constant 2 in the condition is optimal, and the proof is rather short compared to a similar result due to Donoho and Tanner. This is joint work with Holger Rauhut.
# "Regularization of linear integral equations with noisy data and noisy operator"
Bleyer, Ismael Rodrigo
Regularization methods for linear ill-posed problems $ Kf = g $ have been extensively investigated when there exists noisy measurements $g^{\delta}$ for the true data $g$. However, often also the operator is not known exactly. A common way to solve this problem is to use the regularized total least squares method. In our approach, we consider linear integral equations where we assume that both the kernel and the data are contaminated with noise, and use Tikhonov regularization for a stable reconstruction of both the kernel and the solution. Finally, we discuss computational aspects and develop an iterative shrinkage-thresholding algorithm for the reconstruction, and provide first numerical results.
# "Multilevel Preconditioning and Adaptive Sparse Solution of Inverse Problems"
Dahlke, Stephan
Multilevel Preconditioning and Adaptive Sparse Solution of Inverse Problems We are concerned with the efficient numerical solutaion of minimization problems in Hilbert spaces involving sparsity constraints. These optimization problems arise, e.g., in the context of inverse problems. We analyze a very efficient variant of the well-known iterative soft shrinkage algorithm for large or even infinite dimesnional problems. This algorithm is modified in the following way. Instead of prescribing a fixed threshold parameter, we use a decreasing thresholding strategy. Moreover, we use suitable adaptive schemes for the approximation of the infinite matrix-vector products. We also derive a block multiscale preconditioning technique which allows for local well-conditioning of the underlying matrices and for extending the concept of restricted isometry property to infinitely labelled matrices. The careful combination of these ingredients gives rise to numerical schemes that are guaranteed to cnverge with esponential rate, and which allow for the controlled inflation of the support size of the iterations. We also present numerical experiments that confirm the applicability of our approach. (Joint work with M. Fornasier and T. Raasch)
# "Linear Convergence Rates of l1-Regularization"
Haltmeier, Markus
In this talk we study the stable solution of ill-posed equations
Ax = y
where A : X → Y is a linear operator between Hilbert spaces X and Y . If this equation is ill-posed, then the solution does not depend continuously on the data y. In order to stably solve the equation, stabilization methods have to be applied. The most widely used stabilization technique is Tikhonov regularization
Τy(x) := ||Ax-y||2 + αR(x) → min.
Here R is a penalty functional and α \gt 0 is the regularization parameter.
In the recent years - motivated by the success of compresses sensing - the use of l1 penalty
R(x) = ||x||l1 := ∑λ ∈ Λ|φλ,x|
became very popular.(Here (φλ)λ ∈ Λ is some basis of X.) In this talk we study Tikhonov regularization with l1 penalty term. In particular, we show that the range condition (ran(A*) ∩ R(x+) ≠ ∅) together with a certain injectivity condition allows linear error estimates (convergence rates) between the solution x+ and minimizers of Τα,y. Moreover, we show that the range condition is even necessary for this linear convergence rate. This is talk is based on joint work with M. Grasmair and O. Scherzer.

* M. Grasmair, M. Haltmeier, and O. Scherzer. Necessary and sufficient conditions for linear convergence of l1-regularization. Reports of FSP S105 - \"Photoacoustic Imaging\" 18, University of Innsbruck, Austria, 2009.


# "Compressed Sensing in Infinite Dimensions"
Hansen, Anders C.
Compressed sensing is a great tool for solving inverse problems and it has a wide range of applications in signal processing and medical imaging. However, the current theory covers only problems in finite dimensions, and thus there are plenty of infinite dimensional inverse problems that are not covered by the existing results. In this talk I will show how the finite dimensional theory can be extended to include problems in infinite dimensions. This allows for recovery of much more general objects such as analog signals and infinite resolution images. The tools required come from probability, operator theory, optimization and geometry of Banach spaces. I\'ll give an introduction to what is already known (accompanied by numerical examples) and discuss some of the open questions.
# "Compressed sensing for ill-posed problems: recovery principles and accuracy estimates"
Herrholz, Evelyn
This talk is concerned with compressive sampling strategies and sparse recovery principles for linear and ill-posed problems. We provide compressed measurement models and accuracy estimates for sparse approximations of the solution of the underlying inverse problem. Thereby, we rely on Tikhonov variational and constraint optimization formulations. One essential difference to the classical compressed sensing framework is the incorporation of a joint sparsity measure allowing the treatment of infinite dimensional reconstruction spaces. The theoretical results are furnished with a numerical experiment.
# "New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property"
Krahmer, Felix
The Johnson-Lindenstrauss (JL) Lemma states that any set of p points in high dimensional Euclidean space can be embedded into O(δ ^{-2} log(p)) dimensions, without distorting the distance between any two points by more than a factor between 1 - δ and 1 + δ . We establish a new connection between the JL Lemma and the Restricted Isometry Property (RIP), a well-known concept in the theory of sparse recovery often used for showing the success of l_1-minimization. Consider an m x N matrix satisfying the (k, δ _k)-RIP with randomized column signs and an arbitrary set E of O(e^k) points in R^N. We show that with high probability, such a matrix with randomized column signs maps E into R^m without distorting the distance between any two points by more than a factor of 1 +/- 4 δ _k. Consequently, matrices satisfying the Restricted Isometry of optimal order provide optimal Johnson-Lindenstrauss embeddings up to a logarithmic factor in N. Moreover, our results yield the best known bounds on the necessary embedding dimension m for a wide class of structured random matrices. In particular, for partial Fourier and partial Hadamard matrices, our method optimizes the dependence of m on the distortion δ : We improve the recent bound m = O(δ ^{-4} log(p) log^4(N)) of Ailon and Liberty (2010) to m = O(δ ^{-2} log(p) log^4(N)), which is optimal up to the logarithmic factors in N. Our results also yield new Johnson-Lindenstrauss bounds for several deterministic matrices with randomized column signs. This is joint work with Rachel Ward.
# "Efficient Calculation of Sparse Solutions for Inverse Problems"
Lakhal, Aref
We present an efficient method to regularize ill-posed problems with sparsity as prior knowledge. We combine mollification methods with standard techniques of optimization to derive an efficient algorithm for solving inverse problems with L1- constrains. Numerical tests illustrate the robustness of the algorithm.
# "Exact recovery for linear ill-posed problems with l^1 regularization"
Lorenz, Dirk
Ill-posed problems are problems in which the solution does not depend continuously on the data. In this talk we consider Tikhonov regularization of such problems, and especially focus on sparse regularization. By combining techniques from ill-posed problems and sparse recovery we show, that it it is possible to reconstruct the exact support of the unknown solution even for ill-posed problems. We illustrate our results on the ill-posed problem of digital particle holography.
# "Generalization of the Neural Gas for Learning Sparse Codes"
Martinetz, Thomas
The Neural Gas is a very simple but efficient algorithm for vector quantization which has found widespread applications. We show how it can be extended to learning linear subspaces and be cast into the framework of sparse coding. It compares favorably to other approaches like k-SVD and MOD.
# "Exact Sparse Solutions of Underdetermined Linear Equations"
Pfetsch, Marc
In this talk I will review combinatorial optimization techniques to find a sparsest solution of underdetermined linear equations. The corresponding exact methods are based on branch-and-cut. Not surprisingly, these techniques are computationally much more involved than heuristics such as basis pursuit. The solutions of this and other heuristics will be compared to the exact values. I will try to show the limits and possibilities of the currently available exact approaches.
# "Compressive Sensing and Function Recovery in High Dimensions"
Rauhut, Holger
The talk reviews some basics on compressive sensing, in particular, on recovery of functions that are sparse in bounded orthonormal systems (e.g. the trigonometric system) from randomly chosen samples. We apply then compressive sensing techniques for the recovery of functions in high dimensions.
# "Iterative sparse recovery and regularization theory"
Teschke, Gerd
We shall be concerned with sparse recovery algorithms for inverse and ill-posed problems. In particular, we consider a projected steepest descent method, its stabilization and corresponding regularization results.
# "An Infeasible-Point Subgradient Method and Computational Comparison for l¹-Minimization"
Tillmann, Andreas
The l¹-minimization problem min{ ||x||_1 : Ax=b } , also known as Basis Pursuit (BP), has become important in Compressed Sensing due to its ability to sometimes yield the sparsest solution of the underdetermined system Ax=b. In the past few years, a lot of new algorithms solving (BP) or some (possibly regularized) variant of it have been developed. We introduce a subgradient scheme which -- unlike typical projected subgradient methods -- is not required to maintain feasibility of the iterates throughout the algorithmic progress. Convergence of this method (ISML1) to an optimal feasible point for (BP) can be proven under certain reasonable assumptions. In the second part of the talk we will present results of a computational comparison of various state-of-the-art l¹-solvers and our method. We also show how a new optimality check can speed up these solvers and at the same time dramatically improve the solution quality. (Joint work with D. Lorenz and M. Pfetsch)
# "Quality assessment of the l1 penalization method for sparse recovery"
Verhoeven, Caroline
The l1 penalization method is often used for sparse recovery in (linear) inverse problems. Most research on the effectiveness of this method focuses on measurement matrices with mutual incoherent columns or which satisfy the restricted isometry property. We will study matrices which do not satisfy these properties. Some typical recovery errors are computed in order to show how they are influenced by the sparsity of the desired solution, the noise level in the data, the number of data and the singular value spectrum of the matrix. These results are compared to known theoretical bounds. We also illustrate the ability of this method to predict relative errors on a magnetic tomography example. (joint work with I. Loris)
# "Regularization results for inverse problems with sparsity functional"
Wachsmuth, Gerd
We consider an optimization problem of the type \begin{equation} \left\{ \begin{aligned} \text{Minimize}\quad & F(u) = \frac12 \| \mathcal{S} u - z_\delta \|_{H}^2 + \alpha \, \| u \|_{L^2(\Omega)}^2 + \beta \, \| u \|_{L^1(\Omega)} \\ \text{such that}\quad & u \in U_\textup{ad} \subset L^2(\Omega). \end{aligned} \right.\tag{$\textbf{P}_{\alpha,\delta}$} \label{eq:P} \end{equation} Here, $\Omega \subset \mathbb{R}^n$ is a bounded domain, $H$ is some Hilbert space, $\mathcal{S} \in \mathcal{L}(L^2(\Omega), H)$ compact (e.g.\ the solution operator of an elliptic partial differential equation), $\alpha \gt 0$, and $\delta, \beta \ge 0$. The problem~\eqref{eq:P} can be interpreted as an inverse problem as well as an optimal control problem. Let us denote the solution with $u_{\alpha,\delta}$. The estimate $\| u_{\alpha,0} - u_{\alpha,\delta}\|_{L^2(\Omega)} \le \delta \, \alpha^{-1/2}$ for the error due to the noise level $\delta$ is well known for $\beta = 0$ and the proof can be extended to the case $\beta \gt 0$. A typical way to estimate the regularization error as $\alpha \searrow 0$ is via a source condition, e.g.\ $u_{0,0} = \mathcal{S}^\star w$ with some $w \in H$. This yields $\| u_{\alpha,0} - u_{0,0} \|_{L^2(\Omega)} \le C \, \alpha^{1/2}$. But if pointwise constraints are present ($U_\textup{ad} = \{ u \in L^2(\Omega) : u_a \le u \le u_b \}$), $u_{0,0}$ often is bang-bang, i.e.\ $u_{0,0}(x) \in \{u_a, 0, u_b\}$ a.e.\ in $\Omega$. Hence, $u_{0,0} \\notin H^1(\Omega)$ and by $\operatorname{range}(\mathcal{S}^\star) \subset H^1(\Omega)$ a source condition with $\mathcal{S^\star}$ can not hold. In this talk we present a new technique for deriving rates of the regularization error using a combination of a source condition and a regularity assumption on the adjoint variable $p_{0,0} = \mathcal{S}^\star(z_0 - \mathcal{S} u_{0,0})$. If the measure of $\big\{ \big| |p_{0,0}| - \beta \big| \le \varepsilon \big\} \le C \, \varepsilon$ for all $\varepsilon \ge 0$ it is possible to show $\| u_{\alpha,0} - u_{0,0} \|_{L^2(\Omega)} \le C \, \alpha^{1/2}$ without a source condition. We present examples showing that the error rates are sharp.
# "Generalized Tikhonov regularization with Bregman discrepany"
Worliczek, Nadja
This talk will deal with generalized Tikhonov regularization with Bregman distances as discrepany term. We give a short motivation for using them by means of statistical inversion theory where maximum a posteriori estimators of the solution of inverse problems are often gained by minimizing such functionals. Furthermore we will examine some basic properties of these sort of Tikhonov functionals.
# "Truncated Soft Shrinkage Iteration with Discrepancy Based Stopping Rule"
Zhariy, Mariya

Printfriendly