Hayabusa, an impressive robotic equivalent of Apollo 13 is coming back today. woohoo!To start off the week in good mood here is a large selection of very interesting and new papers related to compressive sensing but first, Laurent Jacques responded in the comment section to a question on RIP:
"... Now if we set A’=cA, where c is a constant, then the singular values are bounded above and below by c^2(1-\delta) and c^2(1-\delta). Thus A and A’ have different \delta. A’ may be not satisfy RIP. But for signal reconstruction, A and A’ are no different. So how do you explain it? Or for a given matrix B, how can we choose a constant c, make matrix cB have the minimum \delta? Do you have any suggestions?...."
Multiplication by a constant is not a problem. what matters actually is the ratio of the two bounds, which is scale invariant by definition. This can be made clear from the l2-l1 instance optimality of Basis Pursuit (DeNoise), as described for instance in Candes' paper "The restricted isometry property and its implications for compressed sensing", or the paper from Simon Foucart and Ming-Jun Lai, "Sparsest solutions of underdetermined linear systems via ell-q minimization for 0 \lt q \le 1".
What is more problematic is the mutiplication of a RIP matrix by another matrix, i.e., BA seems to have a different ratio of bounds than A. This motivated research on the null space property, as in the papers of Zhang et al., e.g.
Yin Zhang, "On theory of compressive sensing via ell-1-minimization: Simple derivations and extensions"
and other related precursor studies (e.g. from J.-J. Fuchs).
Thanks Laurent.
So here we go, here is the list of papers and presentation that will rock your world this week Enjoy!
The MUSIC Algorithm for Sparse Objects: A Compressed Sensing Analysis by Albert C. Fannjiang. The abstract reads:
The MUSIC algorithm, with its extension for imaging sparse {\em extended} objects, is analyzed by compressed sensing (CS) techniques. The notion of restricted isometry property (RIP) and an upper bound on the restricted isometry constant (RIC) are employed to establish sufficient conditions for the exact localization by MUSIC with or without the presence of noise. In the noiseless case, the sufficient condition gives an upper bound on the numbers of random sampling and incident directions necessary for exact localization. In the noisy case, the sufficient condition assumes additionally an upper bound for the noise-to-object ratio (NOR) in terms of the RIC. Rigorous comparison of performance between MUSIC and the CS minimization principle, Lasso, is given. In general, the MUSIC algorithm guarantees to recover, with high probability, $s$ scatterers with $n=\cO(s^2)$ random sampling and incident directions and sufficiently high frequency. For the favorable imaging geometry where the scatterers are distributed on a transverse plane MUSIC guarantees to recover, with high probability, $s$ scatterers with a median frequency and $n=\cO(s)$ random sampling/incident directions. Numerical results confirm that the Lasso outperforms MUSIC in the well-resolved case while the opposite is true for the under-resolved case. The latter effect indicates the superresolution capability of the MUSIC algorithm. Another advantage of MUSIC over the Lasso as applied to imaging is the former's flexibility with grid spacing and guarantee of {\em approximate} localization of sufficiently separated objects in an arbitrarily fine grid. The error can be bounded from above by $\cO(\lambda s)$ for general configurations and $\cO(\lambda)$ for objects distributed in a transverse plane.
In this paper, we analyze a collaborative filter that answers the simple question: What is popular amongst your friends? While this basic principle seems to be prevalent in many practical implementations, there does not appear to be much theoretical analysis of its performance. In this paper, we partly fill this gap. While recent works on this topic, such as the low-rank matrix completion literature, consider the probability of error in recovering the entire rating matrix, we consider probability of an error in an individual recommendation (bit error rate (BER)). For a mathematical model introduced in [1],[2], we identify three regimes of operation for our algorithm (named Popularity Amongst Friends (PAF)) in the limit as the matrix size grows to infinity. In a regime characterized by large number of samples and small degrees of freedom (defined precisely for the model in the paper), the asymptotic BER is zero; in a regime characterized by large number of samples and large degrees of freedom, the asymptotic BER is bounded away from 0 and 1/2 (and is identified exactly except for a special case); and in a regime characterized by a small number of samples, the algorithm fails. We also present numerical results for the MovieLens and Netflix datasets. We discuss the empirical performance in light of our theoretical results and compare with an approach based on low-rank matrix completion.
A Geometric Approach to Low-Rank Matrix Completion by Wei Dai, Ely Kerman, Olgica Milenkovic. The abstract reads:
The low-rank matrix completion problem can be succinctly stated as follows: given a subset of the entries of a matrix, find a low-rank matrix consistent with the observations. While several low-complexity algorithms for matrix completion have been proposed so far, it remains an open problem to devise search procedures with provable performance guarantees for a broad class of matrix models. The standard approach to the problem, which involves the minimization of an objective function defined using the Frobenius metric, has inherent difficulties: the objective function is not continuous and the solution set is not closed. To address this problem, we consider an optimization procedure that searches for a column (or row) space that is geometrically consistent with the partial observations. The geometric objective function is continuous everywhere and the solution set is the closure of the solution set of the Frobenius metric. We also preclude the existence of local minimizers, and hence establish strong performance guarantees, for special completion scenarios, which do not require matrix incoherence or large matrix size.
Generalized Block Sparse Constraint Based Compressive Wideband Spectrum Sensing for Cognitive Radio by Yipeng Liu, Qun Wan. The abstract reads:
Wideband spectrum sensing detects the unused spectrum holes for dynamic spectrum access of cognitive radios. However the too high sampling rate is the challenge for application. As the survey shows that the monitoring primary signal has sparse representation in frequency domain, compressive sensing can be used to transfer the sampling burden to the digital signal processor. An analog to information converter can randomly sample the received signal with sub-Nyquist rate to obtain the random measurements. In the spectrum recovery, to match the practical situation, an improved block sparse signal model can be formulated in that the static frequency spectrum allocation of primary radios means the bounds between di?erent primary radios is known. The whole monitoring spectrum is divided sections of di?erent length in accordance with di?erent allocated primary radios. The minimization of the l2 norm can encourage the dense distribution locally, while the l1 norm of the l2 norms can give the sparse distribution of the blocks. To further enhance the performance, iterative weights can be added on each block to strength the generalized block sparse distribution. The weights used for the next iteration are computed from the value of the current solution. Simulation demonstrates that the proposed method outperforms standard sparse spectrum estimation in accuracy, denoising ability, etc.
Here is another connection to Random Matrix Theory and this time it has to do with very large measurement matrices and coherence: Limiting Laws of Coherence of Random Matrices with Applications to Testing Covariance Structure and Construction of Compressed Sensing Matrices by Tony Cai and Tiefeng Jiang. The abstract reads:
Testing covariance structure is of significant interest in many areas of statistical analysis and construction of compressed sensing matrices is an important problem in signal processing. Motivated by these applications, we study in this paper the limiting laws of the coherence of an n × p random matrix in the high-dimensional setting where p can be much larger than n. Both law of large numbers and limiting distribution are derived. We then consider testing the bandedness of the covariance matrix of a high dimensional Gaussian distribution which includes testing for independence as a special case. The limiting laws of the coherence of the data matrix play a critical role in the construction of the test. The asymptotic results is also applied to the construction of compressed sensing matrices.
I note their remark 4.2 on page 14 that hints at an error in other people's work.
Proximal Methods for Sparse Hierarchical Dictionary Learning by Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, Francis Bach. The abstract reads:
We propose to combine two approaches for modeling data admitting sparse representations: on the one hand, dictionary learning has proven effective for various signal processing tasks. On the other hand, recent work on structured sparsity provides a natural framework for modeling dependencies between dictionary elements. We thus consider a tree-structured sparse regularization to learn dictionaries embedded in a hierarchy. The involved proximal operator is computable exactly via a primal-dual method, allowing the use of accelerated gradient techniques. Experiments show that for natural image patches, learned dictionary elements organize themselves in such a hierarchical structure, leading to an improved performance for restoration tasks. When applied to text documents, our method learns hierarchies of topics, thus providing a competitive alternative to probabilistic topic models.
Collaborative hierarchical sparse modeling by Pablo Sprechmann, Ignacio Ramírez, Guillermo Sapiro, and Yonina Eldar. The abstract reads:
Sparse modeling is a powerful framework for data analysis and processing. Traditionally, encoding in this framework is done by solving an `1-regularized linear regression problem, usually called Lasso. In this work we first combine the sparsity inducing property of the Lasso model, at the individual feature level, with the block-sparsity property of the group Lasso model, where sparse groups of features are jointly encoded, obtaining a sparsity pattern hierarchically structured. This results in the hierarchical Lasso, which shows important practical modeling advantages. We then extend this approach to the collaborative case, where a set of simultaneously coded signals share the same sparsity pattern at the higher (group) level but not necessarily at the lower one. Signals then share the same active groups, or classes, but not necessarily the same active set. This is very well suited for applications such as source separation. An efficient optimization procedure, which guarantees convergence to the global optimum, is developed for these new models. The underlying presentation of the new framework and optimization approach is complemented with experimental examples and preliminary theoretical results.
Universal sparse modeling by Ignacio Ramírez and Guillermo Sapiro. The abstract reads:
Sparse data models, where data is assumed to be well represented as a linear combination of a few elements from a dictionary, have gained considerable attention in recent years, and their use has led to state-of-the-art results in many signal and image processing tasks. It is now well understood that the choice of the sparsity regularization term is critical in the success of such models. In this work, we use tools from information theory, and in particular universal coding theory, to propose a framework for designing sparsity regularization terms which have several theoretical and practical advantages when compared to the more standard `0 or `1 ones, and which lead to improved coding performance and accuracy in reconstruction and classification tasks. We also report on further improvements obtained by imposing low mutual coherence and Gram matrix norm on the corresponding learned dictionaries. The presentation of the framework and theoretical foundations is complemented with examples in image denoising and classification.
Adaptive group testing strategies for target detection and localization in noisy environments by Mark Iwen and Ahmed Tewfik. The abstract reads:
This paper studies the problem of recovering a signal with a sparse representation in a given orthonormal basis using as few noisy observations as possible. As opposed to previous studies, this paper models observations which are subject to the type of ‘clutter noise’ encountered in radar applications (i.e., the measurements used influence the observed noise). Given this model, the paper develops bounds on the number of measurements required to reconstruct the support of the signal and the signal itself up to any given accuracy level when the measurement noise is Gaussian using non-adaptive and adaptive measurement strategies. Further, the paper demonstrates that group testing measurement constructions may be combined with statistical binary detection and estimation methods to produce practical and computationally efficient adaptive algorithms for sparse signal approximation and support recovery. In particular, the paper proves that a wide class of sparse signals can be recovered by adaptive methods using fewer noisy linear measurements than required by any recovery method based on non-adaptive Gaussian measurement ensembles. This result demonstrates an improvement over previous non-adaptive methods in the compressed sensing literature for sparse support pattern recovery in the sublinear-sparse support regime under the measurement model considered herein.
Multichannel Sampling of Signals with Finite Rate of Innovation by Hojjat Akhondi Asl, Pier Luigi Dragotti and Loic Baboulaz. The abstract reads:
In this paper we present a possible extension of the theory of sampling signals with finite rate of innovation (FRI) to the case of multichannel acquisition systems. The essential issue of a multichannel system is that each channel introduces different unknown delays and gains that need to be estimated for the calibration of the channels. We pose both the synchronization stage and the signal reconstruction stage as a parametric estimation problem and demonstrate that a simultaneous exact synchronization of the channels and reconstruction of the FRI signal is possible. We also consider the case of noisy measurements and evaluate the Cram´er-Rao bounds (CRB) of the proposed system. Numerical results as well as the CRB show clearly that multichannel systems are more resilient to noise than the single-channel ones.
Online and Adaptive Tracking of Subspaces from Highly Incomplete Information by Laura Balzano, Robert Nowak, Benjamin Recht. The abstract reads:
We present GROUSE (Grassmanian Rank-One Update Subspace Estimation), an efficient online algorithm for tracking subspaces from highly incomplete observations. GROUSE requires only basic linear algebraic manipulations at every iteration, and each subspace update can be performed in linear time in the dimension of the subspace. We derive our algorithm by analyzing incremental gradient descent on the Grassmannian manifold of subspaces, and relate this approach to other iterative approaches to subspace tracking that use full measurement information. We also show how a slight modification of our subspace tracking approach allows GROUSE to be used as an online incremental algorithm for the matrix completion problem where one aims to fill in the entries of a low-rank matrix. We show that GROUSE performsexceptionally well in practice both in tracking subspaces and as an online algorithm for matrix completion.
Here are also some presentations:
by Felix Herrmann.
by Andrew McGregor
- "Data Streams, Dyck Languages, and Detecting Dubious Data Structures" (University
- of Edinburgh, Random Graals '10)
- Annotations in Data Streams
- Graph and Geometry Problems in the Data Stream Model and "Data Streams: Random Order and Multiple Passes
- Robust Lower Bounds for Communication and Stream Computation
- Streaming and Sketching for Distributions
and a presentation of a proposal on CS and communication.
The paper that was the support of the human interest story in Wired and on NPR has been published:
Improved Pediatric MR Imaging with Compressed Sensing.
Vasanawala SS, Alley MT, Hargreaves BA, Barth RA, Pauly JM, Lustig M.
Departments of Pediatric Radiology and Radiology, Stanford University School of Medicine, 725 Welch Rd, Room 1679, Stanford, CA 94305-5913.
Abstract
Purpose: To develop a method that combines parallel imaging and compressed sensing to enable faster and/or higher spatial resolution magnetic resonance (MR) imaging and show its feasibility in a pediatric clinical setting. Materials and Methods: Institutional review board approval was obtained for this HIPAA-compliant study, and informed consent or assent was given by subjects. A pseudorandom k-space undersampling pattern was incorporated into a three-dimensional (3D) gradient-echo sequence; aliasing then has an incoherent noiselike pattern rather than the usual coherent fold-over wrapping pattern. This k-space-sampling pattern was combined with a compressed sensing nonlinear reconstruction method that exploits the assumption of sparsity of medical images to permit reconstruction from undersampled k-space data and remove the noiselike aliasing. Thirty-four patients (15 female and 19 male patients; mean age, 8.1 years; range, 0-17 years) referred for cardiovascular, abdominal, and knee MR imaging were scanned with this 3D gradient-echo sequence at high acceleration factors. Obtained k-space data were reconstructed with both a traditional parallel imaging algorithm and the nonlinear method. Both sets of images were rated for image quality, radiologist preference, and delineation of specific structures by two radiologists. Wilcoxon and symmetry tests were performed to test the hypothesis that there was no significant difference in ratings for image quality, preference, and delineation of specific structures. Results: Compressed sensing images were preferred more often, had significantly higher image quality ratings, and greater delineation of anatomic structures (P < .001) than did images obtained with the traditional parallel reconstruction method. Conclusion: A combination of parallel imaging and compressed sensing is feasible in a clinical setting and may provide higher resolution and/or faster imaging, addressing the challenge of delineating anatomic structures in pediatric MR imaging
Finally, a short course at the next OSA annual meeting:
SC354. Compressive SensingThis past week, there was a meeting on Sparsity and Computation at the Hausdorff Center for Mathematics. I could not located any video or presentations online. Too bad.
Sunday, October 24, 2010
Kevin Kelly; Rice Univ., USA
Level: No level selected.
Course Description
This tutorial will review the mathematical framework of compressive sensing, highlighting its implementation in various optical imaging and spectroscopy systems. The basis of these systems is a well-established body of work which asserts that one can exploit sparsity or compressibility when acquiring signals of general interest, and that one can design non-adaptive sampling techniques that condense the information in a compressible signal using far fewer data points than were thought necessary.
For various systems, this strategy has many advantages over the traditional raster scan method given factors such as sensitivity, resolution, dwell time, and bandwidth limit. Specific examples will include implementation in infrared, hyperspectral, and fluorescence-based imaging systems. Discussions will also include the mathematics behind the reconstruction algorithms. An explicit comparison of each of these strategies on robustness to noise, speed of reconstruction, and specific feature recognition tasks will be presented. Lastly, limitations and future challenges in the field of compressed imaging will be reviewed.
Benefits and Learning Objectives
This course should enable you to:
Appreciate the underlying mathematics of compressive sensing.
Compare different optimization methods employed for image reconstruction.
Describe optical systems using both fixed masks and spatial light modulators.
Identify the limitations and challenges to implementation in real systems.
Discuss the future directions of the field.
Intended Audience
This course is intended for graduate students, post-doctoral researchers, and anyone with an interest in computational based imaging techniques. A familiarity with MATLAB will be beneficial.
Here is a new DIMACS workshop announcement:
DIMACS Workshop on Network Data Streaming and Compressive Sensing
October 14 - 15, 2010
DIMACS Center, CoRE Building, Rutgers UniversityPresented under the auspices of the DIMACS Special Focus on Algorithmic Foundations of the Internet.
- Organizers:
- Jin Cao, Alcatel-Lucent Bell Labs, cao at research.bell-labs.com
- Cristian Estan, NetLogic, estan at netlogicmicro.com
- Jun (Jim) Xu, Georgia Tech, jx at cc.gatech.edu
Data streaming algorithms and compressive sensing techniques, developed originally in theoretical computer science and image-processing contexts respectively, have recently found many applications in computer networking. Single-node data streaming algorithms have been developed to extract important summary information or statistics, such as entropy, flow size distributions, and flow counts, from a single stream of packets passing through a high-speed network link, using a small amount of high-speed memory. Multi-node data streaming algorithms are proposed to extract such summary information from the union of multiple packet streams without the need to physically aggregate these streams together, which may incur prohibitive communication cost. Compressive sensing techniques have been employed to detect sparse (small in the number of affected nodes/links at any moment of time) network events such as sudden dramatic change in traffic volumes and the existence of dirty network measurements, and to recover network statistics vectors (e.g., traffic matrices and flow sizes) that are sparse (containing few large scalars) in nature. Data streaming and compressive sensing are closely related since random projection is the underlying methodology for both.
While both topics have been featured in earlier DIMACS workshops within other special focus series, the majority of the work there do not directly address research challenges faced by the networking community. In this workshop, we aim at bringing together researchers in both networking and theory communities who are interested in solving real-world networking problems using new or existing data streaming and compressive sensing techniques. The workshop will invite/feature such work not only in the more established application domain of Internet measurements, but also in other emerging contexts such as wireless and sensor networks.
We also plan to propose a JSAC (Journal on Selected Areas in Communications) special issue on this topic to JSAC editorial board and serve as guest editors of the issue.
Credit: ESA/NASA Soho.
No comments:
Post a Comment