CS:The Long Post of the Week

In-Q-Tel is providing some venture funding to InView Technology  Here is the InView's careers site.Some people are churning along the TRL scale.

There was a Summer School on the other side of the equator this past week:  Sparsity and Model Selection, February 28 to March 4, 2011, Montevideo, Uruguay

This summer school consists in series of accessible lectures on model selection and sparse models. Model selection is an important issue of modern statistics. Besides the classical results using penalties based on the size of the model: Cp AIC BIC, a new kind of techniques have appeared with L1 penalties and the LASSO (Tibshirani, 1996) and the work of Donoho and Candès on sparse models. We hope the participation of both graduate students coming from regional Universities (Uruguay, Argentina and others) and researchers interested by the topic.

Presentations can be accessed on the site.

We have several papers today starting with the following: Accelerated Iterative Hard Thresholding by Thomas Blumensath. The abstract reads:

The iterative hard thresholding algorithm (IHT) is a powerful and versatile algorithm for compressed sensing and other sparse inverse problems. The standard IHT implementation faces two challenges when applied to practical problems. The step size parameter has to be chosen appropriately and, as IHT is based on a gradient descend strategy, convergence is only linear. Whilst the choice of the step size can be done adaptively as suggested previously, this letter studies the use of acceleration methods to improve convergence speed. Based on recent suggestions in the literature, we show that a host of acceleration methods are also applicable to IHT. Importantly, we show that these modifications not only significantly increase the observed speed of the method, but also satisfy the same strong performance guarantees enjoyed by the original IHT method.

The code that can reproduce the figures of this paper can be found here. I'll add it to the reconstruction section of the big picture soon.

Model Identification of a Network as Compressing Sensing by Donatello Materassi, G. Innocenti, Laura Giarré, Murti Salapaka. The abstract reads:

In many applications, it is important to derive information about the topology and the internal connections of dynamical systems interacting together. Examples can be found in fields as diverse as Economics, Neuroscience and Biochemistry. The paper deals with the problem of deriving a descriptive model of a network, collecting the node outputs as time series with no use of a priori insight on the topology, and unveiling an unknown structure as the estimate of a "sparse Wiener filter". A geometric interpretation of the problem in a pre-Hilbert space for wide-sense stochastic processes is provided. We cast the problem as the optimization of a cost function where a set of parameters are used to operate a trade-off between accuracy and complexity in the final model. The problem of reducing the complexity is addressed by fixing a certain degree of sparsity and finding the solution that "better" satisfies the constraints according to the criterion of approximation. Applications starting from real data and numerical simulations are provided.

Sparse Volterra and Polynomial Regression Models: Recoverability and Estimation by Vassilis Kekatos, Georgios B. Giannakis. The abstract reads:

Volterra and polynomial regression models play a major role in nonlinear system identification and inference tasks. Exciting applications ranging from neuroscience to genome-wide association analysis build on these models with the additional requirement of parsimony. This requirement has high interpretative value, but unfortunately cannot be met by least-squares based or kernel regression methods. To this end, compressed sampling (CS) approaches, already successful in linear regression settings, can offer a viable alternative. The viability of CS for sparse Volterra and polynomial models is the core theme of this work. A common sparse regression task is initially posed for the two models. Building on (weighted) Lasso-based schemes, an adaptive RLS-type algorithm is developed for sparse polynomial regressions. The identifiability of polynomial models is critically challenged by dimensionality. However, following the CS principle, when these models are sparse, they could be recovered by far fewer measurements. To quantify the sufficient number of measurements for a given level of sparsity, restricted isometry properties (RIP) are investigated in commonly met polynomial regression settings, generalizing known results for their linear counterparts. The merits of the novel (weighted) adaptive CS algorithms to sparse polynomial modeling are verified through synthetic as well as real data tests for genotype-phenotype analysis.

Geometry of log-concave Ensembles of random matrices and approximate reconstruction by Radosław Adamczak, Rafał Latała, Alexander E. Litvak, Alain Pajor, Nicole Tomczak-Jaegermann. The abstract reads:

We study the Restricted Isometry Property of a random matrix $\Gamma$ with independent isotropic log-concave rows. To this end, we introduce a parameter $\Gamma_{k,m}$ that controls uniformly the operator norm of sub-matrices with $k$ rows and $m$ columns. This parameter is estimated by means of new tail estimates of order statistics and deviation inequalities for norms of projections of an isotropic log-concave vector.

Loopy Belief Propagation, Bethe Free Energy and Graph Zeta Function by Yusuke Watanabe, Kenji Fukumizu. The abstract reads:

We propose a new approach to the theoretical analysis of Loopy Belief Propagation (LBP) and the Bethe free energy (BFE) by establishing a formula to connect LBP and BFE with a graph zeta function. The proposed approach is applicable to a wide class of models including multinomial and Gaussian types. The connection derives a number of new theoretical results on LBP and BFE. This paper focuses two of such topics. One is the analysis of the region where the Hessian of the Bethe free energy is positive definite, which derives the non-convexity of BFE for graphs with multiple cycles, and a condition of convexity on a restricted set. This analysis also gives a new condition for the uniqueness of the LBP fixed point. The other result is to clarify the relation between the local stability of a fixed point of LBP and local minima of the BFE, which implies, for example, that a locally stable fixed point of the Gaussian LBP is a local minimum of the Gaussian Bethe free energy.

Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection by Abhimanyu Das, David Kempe. The abstract reads:

We study the problem of selecting a subset of k random variables from a large set, in order to obtain the best linear prediction of another variable of interest. This problem can be viewed in the context of both feature selection and sparse approximation. We analyze the performance of widely used greedy heuristics, using insights from the maximization of submodular functions and spectral analysis. We introduce the submodularity ratio as a key quantity to help understand why greedy algorithms perform well even when the variables are highly correlated. Using our techniques, we obtain the strongest known approximation guarantees for this problem, both in terms of the submodularity ratio and the smallest k-sparse eigenvalue of the covariance matrix. We further demonstrate the wide applicability of our techniques by analyzing greedy algorithms for the dictionary selection problem, and significantly improve the previously known guarantees. Our theoretical analysis is complemented by experiments on real-world and synthetic data sets; the experiments show that the submodularity ratio is a stronger predictor of the performance of greedy algorithms than other spectral parameters.

Compressive Sensing for Cluster Structured Sparse Signals: Variational Bayes Approach by Lei Yu, Jean-Pierre Barbot, Gang Zheng, Hong Sun. The abstract reads:

Compressive Sensing (CS) provides a new paradigm of sub-Nyquist sampling which can be considered as an alternative to Nyquist sampling theorem. In particular, providing that signals are with sparse representations in some known space (or domain), information can be perfectly preserved even with small amount of measurements captured by random projections. Besides sparsity prior of signals, the inherent structure property underline some specific signals is often exploited to enhance the reconstruction accuracy and promote the ability of recovery. In this paper, we are aiming to take into account the cluster structure property of sparse signals, of which the nonzero coefficients appear in clustered blocks. By modeling simultaneously both sparsity and cluster prior within a hierarchical statistical Bayesian framework, a nonparametric algorithm can be obtained through variational Bayes approach to recover original sparse signals. The proposed algorithm could be slightly considered as a generalization of Bayesian CS, but with a consideration on cluster property. Consequently, the performance of the proposed algorithm is at least as good as Bayesian CS, which is verified by the experimental results.

Model-Based Compressive Sensing for Multi-party Distant Speech recongnition by Afsaneh Asaei, Herve Bourlard and Volkan Cevher. The abstract reads:

We leverage the recent algorithmic advances in compressive sensing, and propose a novel source separation algorithm for efficient recovery of convolutive speech mixtures in spectro-temporal domain. Compared to the common sparse component analysis techniques, our approach fully exploits structured sparsity models to obtain substantial improvement over the existing state-of-the-art. We evaluate our method for separation and recognition of a target speaker in a multi-party scenario. Our results provide compelling evidence of the effectiveness of sparse recovery formulations in speech recognition.

Sparse Target Counting and Localization in Sensor Networks Based on Compressive Sensing by Bowu Zhang, Xiuzhen Cheng, Nan Zhang Yong Cui Yingshu Li Qilian Liang. The abstract reads:

In this paper, we propose a novel compressive sensing (CS) based approach for sparse target counting and positioning in wireless sensor networks. While this is not the first work on applying CS to count and localize targets, it is the first to rigorously justify the validity of the problem formulation. Moreover, we propose a novel greedy matching pursuit algorithm (GMP) that complements the well-known signal recovery algorithms in CS theory and prove that GMP can accurately recover a sparse signal with a high probability. We also propose a framework for counting and positioning targets from multiple categories, a novel problem that has never been addressed before. Finally, we perform a comprehensive set of simulations whose results demonstrate the superiority of our approach over the existing CS and non-CS based techniques.

Sparsity Enhanced Decision Feedback Equalization by Jovana Ilic, and Thomas Strohmer. The abstract reads:

For single-carrier systems with frequency domain equalization, decision feedback equalization (DFE) performs better than linear equalization and has much lower computational complexity than sequence maximum likelihood detection. The main challenge in DFE is the feedback symbol selection rule. In this paper, we give a theoretical framework for a simple, sparsity based thresholding algorithm. We feed back multiple symbols in each iteration, so the algorithm converges fast and has a low computational cost. We show how the initial solution can be obtained via convex relaxation instead of linear equalization, and illustrate the impact that the choice of the initial solution has on the bit error rate performance of our algorithm. The algorithm is applicable in several existing wireless communication systems (SC-FDMA, MC-CDMA, MIMO-OFDM). Numerical results illustrate significant performance improvement in terms of bit error rate compared to the MMSE solution.

An L1-based variational model for Retinex theory and its application to medical images by Wenye Ma, Jean-Michel Morel, Stanley Osher, Aichi Chien. The abstract reads

Human visual system (HVS) can perceive constant color under varying illumination conditions while digital images record information of both reflectance (physical color) of objects and illumination. Retinex theory, formulated by Edwin H. Land, aimed to simulate and explain this feature of HVS. However, to recover the reflectance from a given image is in general an ill-posed problem. In this paper, we establish an L1-based variational model for Retinex theory that can be solved by a fast computational approach based on Bregman iteration. Compared with previous works, our L1-Retinex method is more accurate for recovering the reflectance, which is illustrated by examples and statistics. In medical images such asmagnetic resonance imaging (MRI), intensity inhomogeneity is often encountered due to bias fields. This is a similar formulation to Retinex theory while the MRI has some specific properties. We then modify the L1-Retinex method and develop a new algorithm for MRI data. We demonstrate the performance of our method by comparison with previous work on simulated and real data.

Phase Reconstruction Using Machine Learning For Wireless Tomography by S. J. Hou , Z. Hu , M. C. Wicks, and R. C. Qiu. The abstract reads:

This is the following paper in a series on a new initiative of wireless tomography. The goal is to combine two areas: wireless communication and radio tomography. This paper primarily focuses on phase reconstruction using machine learning for wireless tomography. When only communication components instead of sophisticated equipment are exploited to perform wireless tomography, phase information of the received field is hard to obtain. Thus self-coherent tomography is proposed, which has two main steps. First, phase reconstruction is achieved using the received amplitude only data. Second, the standard radio tomographic imaging algorithms are used for data analysis. However for the real application, the effect of noise can not be ignored. In order to improve the performance of phase reconstruction with the consideration of noise, a hybrid system for wireless tomography is proposed in this paper. Meanwhile, machine learning is explored here to execute the noise reduction.

Noncoherent Compressive Sensing with Application to Distributed Radar by  Christian R. Berger and Jose M. F. Moura. The abstract reads:

We consider a multi-static radar scenario with spatially dislocated receivers that can individually extract delay information only. Furthermore, we assume that the receivers are not phase-synchronized, so the measurements across receivers can only be combined noncoherently. We cast this scenario as a compressive sensing reconstruction problem, where the vector of unknowns consists of complex baseband coefficients of tentative targets at discrete positions within a region of interest. The difference to previous work is that each receiver has to have a separate set of variables to account for the noncoherent measurement model. This leads to multiple reconstruction problems that are individually ill-defined, but can be regularized by a shared sparsity pattern, as studied in jointly- or block-sparse reconstruction problems. We evaluate this approach in a simple scenario with three receivers and three closely spaced targets. Using the popular basis pursuit and orthogonal matching pursuit algorithms, we find that targets can be fully resolved and that the position estimation error is close to the Cram´er-Rao lower bound based on an estimator that knows the number of targets.

Wideband Spectrum Sensing based on Sparse Channel State Recovery in Cognitive Radio Networks by Lei Shi, Zheng Zhou, Liang Tang. The abstract reads:

Motivated by the compressed sensing sparse channel estimation problem, the complete channel state is sparse under the conditions of low spectral efficiency. Other than traditional method of looking for the perception of spectrum holes, this paper focus on the sparse of occupied sub-channels. Based on compressed sensing technology, a novel cooperative wideband spectrum sensing method is proposed in the cognitive radio networks. The speed and the efficiency of the single CR node sensing process are improved through the sparse measurement matrix. The fusion center reconstructs the observed data by the turbo-decoding message-passing (TDMP) algorithm, dramatically reducing the computation complexity.

Also, behind a paywall or just abstracts, we have:

Spatial Compressive Sensing for Direction-of-Arrival Estimation of Multiple Sources Using Dynamic Sensor Arrays by I. Bilik. The abstract reads:

This work addresses the problem of direction-of-arrival (DoA) estimation of multiple sources using short and dynamic sensor arrays. We propose to utilize compressive sensing (CS) theory to reconstruct the high-resolution spatial spectrum from a small number of spatial measurements. Motivated by the physical structure of the spatial spectrum we model it as a sparse signal in the wavenumber-frequency domain, where the array manifold is proposed to serve as a deterministic sensing matrix. The proposed spatial CS (SCS) approach allows exploitation of the array orientation diversity (achievable via array dynamics) in the CS framework to address challenging array signal processing problems such as left-right ambiguity and poor estimation performance at endfire. The SCS is conceptually different from well-known classical and subspace-based methods because it provides high azimuth resolution using a short dynamic linear array without restricting requirements on the spatial and temporal stationarity and correlation properties of the sources and the noise. The SCS approach was shown to outperform current super-resolution and orientation diversity based methods in single-snapshot simulations with multiple sources.

Mission Design for Compressive Sensing with Mobile Robots by Robert Hummel, Sameera Poduri, Franz Hover, Urbashi Mitra and Gaurav Sukhatme. The abstract reads:

This paper considers mission design strategies for mobile robots whose task is to perform spatial sampling of a static environmental field, in the framework of compressive sensing. According to this theory, we can reconstruct compressible fields using O(log n) nonadaptive measurements (where n is the number of sites of the spatial domain), in a basis that is “incoherent” to the representation basis; random uncorrelated measurements satisfy this incoherence requirement. Because an autonomous vehicle is kinematically constrained and has finite energy and communication resources, it is an open question how to best design missions for CS reconstruction. We compare a two-dimensional random walk, a TSP approximation to pass through random points, and a randomized boustrophedon (lawnmower) strategy. Not unexpectedly, all three approaches can yield comparable reconstruction performance if the planning horizons are long enough; if planning occurs only over short time scales, the random walk will have an advantage.

The following information is posted here mostly as a heads-up. Some of the dates may have passed.

PhD Dissertation Defense: Integrated Circuits and Systems for Sparse Signal Acquisition based on Asynchronous Sampling and Compressed Sensing, March 11, 2011. 3pm, 200 Boston Ave. Suite 2700

Speaker: Michael Trakimas, PhD Candidate, Host: Prof. Sameer Sonkusale. Abstract

This dissertation builds on the recent theoretical and experimental work on asynchronous sampling and compressed sensing. We discuss how advances in these fields can be exploited to design practical data acquisition systems capable of directly acquiring sparse signals at sub-Nyquist rates. To provide a connection to how this can benefit certain emerging technologies, we focus specifically on increasing the power efficiency and decreasing the complexity of the signal acquisition process compared to existing conventional Nyquist rate solutions for biomedical sensor and wideband spectrum sensing applications. The first half of this work presents the design and implementation of an adaptive resolution asynchronous analog-to-digital converter (ADC) targeted at biomedical signal acquisition applications such as ECG and EEG monitoring. The main contribution of this work was the implementation of an adaptive resolution algorithm which varied the quantizer resolution of the ADC with the slope of the input signal, in order to overcome the tradeoff between dynamic range and input bandwidth typically seen in asynchronous ADCs. The second half of this work presents the design and implementation of a compressed sensing based analog-to-information converter (AIC) for wideband spectrum sensing applications. The core of the design is an ultra low power moderate rate ADC that randomly samples the received signal at sub-Nyquist rates. Measurement results of the compressed sensing AIC for wideband spectrum sensing demonstrate improved power efficiency and reduced complexity compared to the conventional direct sampling architecture, while still maintaining high performance for signals with sparse frequency support.

A PhD studentship offer:at Chalmers in Goteborgin Sweden:

(110302) Large-deviation estimates and duality theory in compressive sensing

Large-deviation estimates and duality theory in compressive sensing

Abstract: Compressive sensing (CS) is a recently introduced method that enables sampling of sparse signals well below the Nyquist rate, while still guaranteeing near-perfect reconstruction. A fundamental problem in compressive sensing is to determine the number of samples (measurements) needed to guarantee near-perfect reconstruction, as a function of the sparsity level of the signal. Various results are available in the CS literature for different sensing mechanisms. Recently, a new, fairly general framework has been proposed, within which all previously known results in CS can be re-derived. This framework makes use of relatively simple results from large-deviation theory and duality in optimisation theory. The goal of this master thesis is to isolate and understand the fundamental tools underpinning this novel framework. Furthermore, these tools should be used to simplify recent results in the fields of matrix completion and robust principle component analysis.

Requirements The ideal candidate should have a strong background in probability theory and linear algebra, and should enjoy theoretical work. The master student will acquire an in-depth knowledge of compressive sensing, a hot topic at the intersection of signal processing, information theory and machine learning.

Contact Giuseppe Durisi (durisi at charmers dot se), phone: +46 31 772 18 02, Signals and systems department

Recommended reading:

[1] E. J. Candès and Y. Plan, “A probabilistic and RIPless theory of compressed sensing,” Nov. 2010. [Online]. Available: http://arxiv.org/abs/1011.3854

[2] D. Gross, “Recovering low-rank matrices from few coefficients in any basis,” Sep. 2010. [Online]. Available: http://arxiv.org/pdf/0910.1879v1

[3] E. J. Candès, X. Li, Y. Ma, and J. Wright, “Robust principal component analysis? ” Dec. 2009. [Online]. Available: http://arxiv.org/abs/0912.3599
Major subjects Information Technology
Department Signals and Systems

Here is a presentation:

Low dimensional embedding with compressed, incomplete and inaccurate measurements
When
Start: 03/02/2011 - 4:15pm
End : 03/02/2011 - 5:00pm

Category: Colloquium

Speaker
Blake Hunter (University of California, Davis)

Abstract

As the size and complexity of data continues to grow, extracting knowledge becomes exponentially more challenging. Active areas of research for mining this high dimensional data can be found across a broad range of scientific fields including pure and applied mathematics, statistics, computer science and engineering. Spectral embedding is one of the most powerful and 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. In this talk, we combine the distance preserving measurements of compressed sensing and matrix completion with the robust power of spectral embedding. Our analysis provides rigorous bounds on how small perturbations from using compressed sensing and matrix completion affect the affinity matrix and in succession the spectral coordinates. Theoretical guarantees are complemented with numerical results. A number of examples of the unsupervised organization and clustering of synthetic and real world image data are also shown
Where
Roberts North 15, Claremont McKenna College

and a seminar:

ECE Seminar on This Afternoon
"Application of Compressive Sensing to Cognitive Radio and Digital Holo," by Sang (Peter) Chin, Cyber Operations Branch, JHU Applied Physics Lab. 3 p.m. on Thursday, March 3, in Hodson 316. Hosted by Electrical and Computer Engineering.

Refreshments will be served at 2:45 p.m.

FOR DISABILITY INFORMATION CONTACT:
Candace Abel (410) 516-7031 cabel@jhu.edu

Abstract:
One of the key aspects of cognitive radio is the concept of dynamic spectrum access, where a radio searches for a (temporarily) unused white space in order to transmit and receive its data. To enable such dynamic spectrum utilization, it is critical to detect the existence/absence of primary users, and furthermore understand the spectrum usage pattern of primary users. Currently, this is done by periodically switching the radio from the operation mode (transmit/receive) to sensing mode, during which the radio tries to sense for the existence of other (incumbent) signals. It is thus of utmost importance to make the sensing period as small as possible, which can not only increase the operational utilization, but also enable detection of more white spaces (including finer ones that can't be otherwise detected). We show that the nascent theory of compressive sensing, a revolutionary sampling paradigm which enables sampling at a much lower rate than the SyQuest rate by exploiting the sparsity of a given signal, can offer new opportunities for DSA. In particular, we show that compressive sensing theory is able to reduce significantly the amount of time and size of data that a cognitive radio needs in order to sense the existence of incumbent signals. Furthermore, we show that the recent progress on compressive sensing is also applicable and useful in a digital heliographic system, especially in that it greatly reduces the number of pixels (up to 80%) in hologram that is necessary to reconstruct the image without losing essential features of the image. This offers a path to sparsely sample the hologram and produce images with resolution comparable to the fully populated array, which in turn affects a holographic system to capture images at longer ranges using an array of sparsely populated smaller CCD arrays.

Bio:
Dr. Sang (Peter) Chin is currently a branch chief scientist of Cyber Operations Branch at Johns Hopkins Applied Physics Lab, where he is conducting research in the area of compressive sensing, data fusion, game theory, MHT tracking, quantum-game inspired cyber-security, and cognitive radio. Prior to joining JHU/APL, he was a Division CTO at SAIC, and before that, he was a technology manager for 90 nm technology at LSI Logic Corp., where he also helped to develop its first Embedded DRAM technology jointly with Hitachi Semiconductor in late 90’s. He received his PhD. in mathematics from MIT and is a Phi Beta Kappa graduate from Duke University where he was a faculty scholar with a triple major in EE, computer science and mathematics.

Credit photo: NASA/JPL/Space Science Institute, Beyond Southern Rhea, February 28, 2011

This is the answer I gave on Quora to the question "Has Compressed Sensing peaked ?"

I wrote the more verbose answer about two months ago, but if you have been reading the blog during this time period, you may have seen some of the arguments expanded one way or another. Without further due, here it is:

First let me just say that about every two weeks, on average, I find a good paper that is either strictly CS or an extension of it (low rank problems,...).that clearly advances the subject in one shape or another. One recent example [as of January 12th, 2011] of a good paper is the one confirming that a CS encoding could be used in a critical system on a space mission (encoding of the PACS camera on the Herschel Space telescope). This was in the pipeline since the Herschel spacecraft launched but it took some time to figure out the quirks of how to restore images (colored noise...). In effect, even if the hardware was ready to use, it took a little while to get good data out that system. But Herschel is a peculiar example of a scientific instrumentation that was built before the CS algorithm was devised (they were expecting to use a lesser encoding algorithm in the first place). [Is it a paradigm shift where sensor are built first and then encoding designed later ?]
Second let me give some context as to why the field seems to have peaked and why questions such as the one I am responding to, gets to be asked.

The initial success of CS comes from its utilization in hardware that could already produce samples in the right space (Fourier space in MRI). Once again even if the hardware is spitting out the right type of data, it took some good algorithm development (mostly in the reconstruction stage) to get to the point where now MRI is being speed tracked by most MRI makers. This case is fascinating because a naive implementation of CS just would not be directly competitive with a whole slew of empirical methods devised for the past twenty years. In short, CS is not magic when it gets directly implemented in a technology that has already been exploited. It has however brought something extremely important: CS has accelerated investigation in a certain part of the phase/parameter space (including untouched parameter spaces) and has given good reasons as to why other part of the parameter space should not be important to investigate. Both the positive and negative insights are extremely important when making decisions on whether a certain technology climbs the Technology Readiness Level (TRL) ladder.

The reason people seem to think the subject has peaked is because they feel that besides MRI, there has not been other instrumentation providing similar success. This is indeed the case, most other hardware relying on CS are merely at the very low end of the Technology Readiness Level chart i.e. most are in the prototype stage (CS camera at Rice for instance) since common sensors in those fields do not provide the right type of sampling. This nurturing stage fueled by academic research allows one to investigate a different phase space than what other similar instrumentation can reach. In the end, there will be sensors that will not provide additional information or very little compared to existing technology. From that point of view, it may take a little while and some perseverance before we have other winners out of this list of hardware.
Even if none of the current hardware yield acceptable sensors (which I think is a far stretch), I can still see how CS can be used as just an encoding layer (see Herschel, but also the seismic work at UBC and Georgia Tech) which really put a good framework in what used to be called group testing. I also think that either sparsity or some other feature enforced a la CS, will do wonders on calibration issues thereby making these methods central for any type of sensor development.
Let us not forget that while low TRL insturmentation have appeared in the lab (see list), CS also could enable some new kind of instrumentation that could only be construed as futuristic (check "These Technologies Do Not Exist" or the recent idea of using the USPS fleet as a sensor network)
Finally, while the low maturity on the TRL scale is an important factor, there is probably another structural phenomenon at play: An explosion of different concepts enabled by CS across many branches of science and engineering has effectively diluted the core subject into domain specific areas. This fragmentation has really decreased the critical mass of efforts from one specific subject into less visible smaller subjects of inquiries. The core focus featured in the reconstruction solvers is likely to stay and should provide enough support to people designing new instrumentation or group testing procedures though.

Other related entries on the subject can be found here:

• Never, Ever Give In
• "...I found this idea of CS sketchy,..."
• Islands of Knowledge
• The Dip
• This is not a hardware-only or solver-only problem ...
• What Island Is Next ?

Doesn't the Fort being destroyed every night and reconstructed everyday by kids remind you not of a story we all share in this quest to make CS work ?

Compressed Sensing Image Reconstruction via Recursive Spatially Adaptive Filtering

Alessandro Foi just sent me the following:

Dear Igor,

a demonstration software for Matlab is now online at http://www.cs.tut.fi/~comsens/

Thanks,
Alessandro

Thanks Alessandro. Our readers may recall that the algorithm is about Compressed Sensing Image Reconstruction via Recursive Spatially Adaptive Filtering introduced as such:

We introduce a new approach to image reconstruction from highly incomplete data. The available data are assumed to be a small collection of spectral coefficients of an arbitrary linear transform. This reconstruction problem is the subject of intensive study in the recent field of "compressed sensing" (also known as "compressive sampling"). Our approach is based on a quite specific recursive filtering procedure. At every iteration the algorithm is excited by injection of random noise in the unobserved portion of the spectrum and a spatially adaptive image denoising filter, working in the image domain, is exploited to attenuate the noise and reveal new features and details out of the incomplete and degraded observations. This recursive algorithm can be interpreted as a special type of the Robbins-Monro stochastic approximation procedure with regularization enabled by a spatially adaptive filter. Overall, we replace the conventional parametric modeling used in CS by a nonparametric one. We illustrate the effectiveness of the proposed approach for two important inverse problems from computerized tomography: Radon inversion from sparse projections and limited-angle tomography. In particular we show that the algorithm allows to achieve exact reconstruction of synthetic phantom data even from a very small number projections. The accuracy of our reconstruction is in line with the best results in the compressed sensing field.

From the description file:

Description
-----------
This demo software reproduces the following four experiments from the paper
K. Egiazarian, A. Foi, and V. Katkovnik, "Compressed Sensing Image Reconstruction via Recursive Spatially Adaptive Filtering," Proc. IEEE ICIP 2007, San Antonio (TX), USA, pp. 549-552, Sept. 2007. DOI http://dx.doi.org/10.1109/ICIP.2007.4379013
Experiments 1-3
Tomographic reconstruction from sparse projections (approximating Radon projections as radial lines in FFT domain) We consider three illustrative inverse problems of compressed sensing for computerized tomography. In particular, we show reconstruction examples of the Shepp-Logan phantom from sparse Radon projections, with 22 and 11 radial lines in FFT-domain (i.e., available Radon projections), and reconstruction from limited-angle projections, with a reduced subset of 61 projections within a 90 degrees aperture. The available portions of the spectrum and the initial back-projection estimates are shown below.
experiment_case=1  - Sparse projections: 22 radial lines
experiment_case=2  - Sparse projections: 11 radial lines
experiment_case=3  - Limited-angle (90 degrees aperture, 61 radial lines)
Experiment 4
Reconstruction from low-frequency portion of Fourier spectrum. Reconstruction of the Cameraman image (256x256 pixels) from the low-frequency portion of its Fourier spectrum (a 128×128 square centered at the DC).
experiment_case=4



For all the above experiments, the block-matching and 3D filtering algorithm (BM3D) serves as the spatially adaptive filter used in the recursive stochastic approximation algorithm. The separable 3D Haar wavelet decomposition is adopted as the transform utilized internally by the BM3D algorithm. The general version of the BM3D algorithm is available at
http://www.cs.tut.fi/~foi/GCF-BM3D/


K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian,
"Image denoising by sparse 3D transform-domain collaborative filtering,"
IEEE Trans. Image Process., vol. 16, no. 8, pp. 2080-2095, August 2007.
DOI http://dx.doi.org/10.1109/TIP.2007.901238

I'll be listing this algorithm shortly in the reconstruction section of the Big picture.

Never, Ever Give In

You think you're the only one in the dip ?



What are you waiting for ?

Thanks Michele.

CS: Summary Based Structures with Improved Sublinear Recovery for Compressed Sensing, Support-Predicted Modified-CS for Recursive Robust Principal Components' Pursuit, An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors

I obviously had to miss a few papers yesterday, here they are:

Summary Based Structures with Improved Sublinear Recovery for Compressed Sensing by M. Amin Khajehnejad, Juhwan Yoo, Animashree Anandkumar, Babak Hassibi. The abstract reads:

We introduce a new class of measurement matrices for compressed sensing, using low order summaries over binary sequences of a given length. We prove recovery guarantees for three reconstruction algorithms using the proposed measurements, including $\ell_1$ minimization and two combinatorial methods. In particular, one of the algorithms recovers $k$-sparse vectors of length $N$ in sublinear time $\text{poly}(k\log{N})$, and requires at most $\Omega(k\log{N}\log\log{N})$ measurements. The empirical oversampling constant of the algorithm is significantly better than existing sublinear recovery algorithms such as Chaining Pursuit and Sudocodes. In particular, for $10^3\leq N\leq 10^8$ and $k=100$, the oversampling factor is between 3 to 8. We provide preliminary insight into how the proposed constructions, and the fast recovery scheme can be used in a number of practical applications such as market basket analysis, and real time compressed sensing implementation.

Support-Predicted Modified-CS for Recursive Robust Principal Components' Pursuit by Chenlu Qiu, Namrata Vaswani. The abstract reads:

This work proposes a causal and recursive algorithm for solving the "robust" principal components' analysis (PCA) problem. We primarily focus on robustness to correlated outliers. In recent work, we proposed a new way to look at this problem and showed how a key part of its solution strategy involves solving a noisy compressive sensing(CS) problem. However, if the support size of the outliers becomes too large, for a given dimension of the current PC space, then the number of "measurements" available for CS may become too small. In this work, we show how to address this issue by utilizing the correlation of the outliers to predict their support at the current time; and using this as "partial support knowledge" for solving Modified-CS instead of CS.

An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors by Yangyang Xu, Wotao Yin, Zaiwen Wen, Yin Zhang. The abstract reads:

This paper introduces a novel algorithm for the nonnegative matrix factorization and completion problem, which aims to nd nonnegative matrices X and Y from a subset of entries of a nonnegative matrix M so that XY approximates M. This problem is closely related to the two existing problems: nonnegative matrix factorization and low-rank matrix completion, in the sense that it kills two birds with one stone. As it takes advantages of both nonnegativity and low rank, its results can be superior than those of the two problems alone. Our algorithm is applied to minimizing a non-convex constrained least-squares formulation and is based on the classic alternating direction augmented Lagrangian method. Preliminary convergence properties and numerical simulation results are presented. Compared to a recent algorithm for nonnegative random matrix factorization, the proposed algorithm yields comparable factorization through accessing only half of the matrix entries. On tasks of recovering incomplete grayscale and hyperspectral images, the results of the proposed algorithm have overall better qualities than those of two recent algorithms for matrix completion.

CS: Would you like that entry Supersized?

Today is the jumbo sized edition as I am catching up for the past two weeks. There is a gem somewhere for you. Don't pay attention to a particular order, it's a mess. Enjoy!

First, as discovered by Jordan earlier, it looks like we have an instance of compressive clustering. Here is the paper: Active Clustering: Robust and Efficient Hierarchical Clustering using Adaptively Selected Similarities by Brian Eriksson, Gautam Dasarathy, Aarti Singh, Robert Nowak. The abstract reads:

Hierarchical clustering based on pairwise similarities is a common tool used in a broad range of scientific applications. However, in many problems it may be expensive to obtain or compute similarities between the items to be clustered. This paper investigates the hierarchical clustering of N items based on a small subset of pairwise similarities, significantly less than the complete set of N(N-1)/2 similarities. First, we show that if the intracluster similarities exceed intercluster similarities, then it is possible to correctly determine the hierarchical clustering from as few as 3N log N similarities. We demonstrate this order of magnitude savings in the number of pairwise similarities necessitates sequentially selecting which similarities to obtain in an adaptive fashion, rather than picking them at random. We then propose an active clustering method that is robust to a limited fraction of anomalous similarities, and show how even in the presence of these noisy similarity values we can resolve the hierarchical clustering using only O(N log^2 N) pairwise similarities.

Target Detection Performance Bounds in Compressive Spectral Imaging by Kalyani Krishnamurthy, Rebecca Willett, and Maxim Raginsky. The abstract reads:

This paper describes computationally efficient approaches and associated theoretical performance guarantees for the detection of known spectral targets and spectral anomalies from few projection measurements of spectral images. The proposed approaches accommodate spectra of different signal strengths contaminated by a colored Gaussian background, and perform detection without reconstructing the spectral image from the observations. The theoretical performance bounds of= the target detector highlight fundamental tradeoffs among the number of measurements collected, amount of background signal present, signal-to-noise ratio, and similarity among potential targets in a known spectral dictionary. The anomaly detector is designed to control the number of false discoveries below a desired level and can be adapted to uncertainties in the user’s knowledge of the spectral dictionary. Unlike approaches based on the principles of compressed sensing, the proposed approach does not depend on a known sparse representation of targets; rather, the theoretical performance bounds exploit the structure of a known dictionary of targets and the distance preservation property of the measurement matrix. Simulation experiments illustrate the practicality and effectiveness of the proposed approaches

SHORT AND SMOOTH SAMPLING TRAJECTORIES FOR COMPRESSED SENSING by Rebecca Willett. The abstract reads:

This paper explores a novel setting for compressed sensing (CS) in which the sampling trajectory length is a critical bottleneck and must be minimized subject to constraints on the desired reconstruction accuracy. In contrast to the existing CS literature, where the focus is on reducing the number of measurements, this contribution describes a short and smooth sampling trajectory guaranteed to satisfy the Restricted Isometry Property if the underlying signal is sparse in an appropriate basis. A na¨ıve path based on randomly choosing a collection of sample locations and using a Traveling Salesman Problem solver to choose a “short” trajectory is shown to be dramatically longer than the nearly straight and very smooth path proposed in this paper. Theoretical justification for the proposed path is presented, and applications to MRI, electromagnetics, and ecosystem monitoring are discussed.

Cooperative Wideband Spectrum Sensing for the Centralized Cognitive Radio Network by Peng Zhang, Robert Qiu. The abstract reads:

Various primary user (PU) radios have been allocated into fixed frequency bands in the whole spectrum. A cognitive radio network (CRN) should be able to perform the wideband spectrum sensing (WSS) to detect temporarily unoccupied frequency bands. We summarize four occupancy features for the frequency bands. 1. The occupancy is sparse; 2. The frequency band allocation information is fixed and common; 3. There are three categories for the frequency band usages; 4. The occupied frequency bands are common in the CRN. For the first time, we consider all features as the prior knowledge in the compressed sensing based cooperative WSS (CWSS) algorithm design for a centralized CRN. We propose a modified orthogonal matching pursuit (Mod-OMP) algorithm and a modified simultaneous orthogonal matching pursuit (Mod-SOMP) algorithm for the CWSS. We compare the CWSS performance of Mod-OMP/Mod-SOMP with the original OMP/SOMP and show the performance improvements

An Adaptive Algorithm for Compressive Approximation of Trajectory (AACAT) for Delay Tolerant Networks by Rajib Rana, Wen Hu, Tim Wark, and Chun Tung Chou. The abstract reads:

Highly efficient compression provides a promising approach to address the transmission and computation challenges imposed by moving object tracking applications on resource constrained Wireless Sensor Networks (WSNs). In this paper, we propose and design a Compressive Sensing (CS) based trajectory approximation algorithm, Adaptive Algorithm for Compressive Approximation of Trajectory (AACAT), which performs trajectory compression, so as to maximize the information about the trajectory subject to limited bandwidth. Our extensive evaluation using “real” trajectories of three di"erent object groups (animals, pedestrians and vehicles) shows that CS-based trajectory compression reduces up to 30% transmission overheads, for given information loss bounds, compared to the state-of-the-art trajectory compression algorithms. We implement AACAT on the resource-impoverished sensor nodes, which shows that AACAT achieves high compression performance with very limited resource (computation power and energy) overheads.

THE VALUE OF REDUNDANT MEASUREMENT IN COMPRESSED SENSING by Victoria Kostina, Marco Duarte, Sina Jafarpour, Robert Calderbank. The abstract reads:

The aim of compressed sensing is to recover attributes of sparse signals using very few measurements. Given an overall bit budget for quantization, this paper demonstrates that there is value to redundant measurement. The measurement matrices considered here are required to have the property that signal recovery is still possible even after dropping certain subsets of D measurements. It introduces the concept of a measurement matrix that is weakly democratic in the sense that the amount of information about the signal carried by each of the designated D-subsets is the same. Examples of deterministic measurement matrices that are weakly democratic are constructed by exponentiating codewords from the binary second order Reed Muller code. The value in rejecting D measurements that are on average larger, is to be able to provide a finer grid for vector quantization of the remaining measurements, even after discounting the original budget by the bits used to identify the reject set. Simulation results demonstrate that redundancy improves recovery SNR, sometimes by a wide margin. Optimum performance occurs when

a significant fraction of measurements are rejected.

NEW WAVELET COEFFICIENT RASTER SCANNINGS FOR COMPRESSIVE IMAGING by Marco Duarte, Sina Jafarpour, Robert Calderbank. The abstract reads:

The Delsarte-Goethals frame has been proposed for deterministic compressive sensing of sparse and compressible signals. Its performance in compressive imaging applications falls short of that obtained for arbitrary sparse vectors. Prior work has proposed specially tailored signal recovery algorithms that partition the recovery of the input vector into clustered and unclustered portions. In this paper we present a formal analysis of the Delsarte-Goethals frame that shows that its hampered performance in compressive imaging is due to the presence of clustered sparse vectors in its null space. Such a clustered structure is characteristic in commonly-used raster scanning of 2- D wavelet representations. We also show that a simple randomized raster scanning of the wavelet coefficient vector can remedy these shortcomings, allowing the use of standard recovery algorithms. Additionally, we propose an alternative deterministic raster scanning that achieves similar recovery performance. Experimental results confirm the improvements in recovery performance for both the noiseless and noisy measurement regimes.

Curvelet-Wavelet Regularized Split Bregman Iteration for Compressed Sensing by Gerlind Plonka, Jianwei Ma. The abstract reads:

Compressed sensing is a new concept in signal processing. Assuming that a signal can be represented or approximated by only a few suitably chosen terms in a frame expansion, compressed sensing allows to recover this signal from much fewer samples than the Shannon-Nyquist theory requires. Many images can be sparsely approximated in expansions of suitable frames as wavelets, curvelets, wave atoms and others. Generally, wavelets represent point-like features while curvelets represent line-like features well. For a suitable recovery of images, we propose models that contain weighted sparsity constraints in two different frames. Given the incomplete measurements f = Φu + with the measurement matrix Φ ∈ RK×N , K much less N, we consider a jointly sparsity-constrained optimization problem of the form argmin u{ ΛcΨcu 1 + ΛwΨwu 1 + 1 2 f − Φu 2 2}. Here Ψc and Ψw are the transform matrices corresponding to the two frames, and the diagonal matrices Λc, Λw contain the weights for the frame coefficients. We present efficient iteration methods to solve the optimization problem, based on Alternating Split Bregman algorithms. The convergence of the proposed iteration schemes will be proved by showing that they can be understood as special cases of the Douglas-Rachford Split algorithm. Numerical experiments for compressed sensing based Fourier-domain random imaging show good performances of the proposed curvelet-wavelet regularized split Bregman (CWSpB) methods, where we particularly use a combination of wavelet and curvelet coefficients as sparsity constraints.

Nonlinear regression modeling via Compressed Sensing by Hiroshi Inoue, Shohei Tateishi and Sadanori Konishi. The abstract reads:

We consider the problem of constructing nonlinear regression models in case that the dimension of data is less than the number of basis functions. We propose a procedure where the smooth curve are effectively estimated along with the technique of regularization method. We give a simple idea for applying the Restricted Isometry Property to curve fitting. Simulation results and real data analysis demonstrate that our methodology performs well in various situations.

A signal recovery algorithm for sparse matrix based compressed sensing by Yoshiyuki Kabashima, Tadashi Wadayama. The abstract reads: 

We have developed an approximate signal recovery algorithm with low computational cost for compressed sensing on the basis of randomly constructed sparse measurement matrices. The law of large numbers and the central limit theorem suggest that the developed algorithm saturates the Donoho-Tanner weak threshold for the perfect recovery when the matrix becomes as dense as the signal size $N$ and the number of measurements $M$ tends to infinity keep $\alpha=M/N \sim O(1)$, which is supported by extensive numerical experiments. Even when the numbers of non-zero entries per column/row in the measurement matrices are limited to $O(1)$, numerical experiments indicate that the algorithm can still typically recover the original signal perfectly with an $O(N)$ computational cost per update as well if the density $\rho$ of non-zero entries of the signal is lower than a certain critical value $\rho_{\rm th}(\alpha)$ as $N,M \to \infty$.

A simple proof of Kashin’s decomposition theorem by Simon Foucart. The abstract reads:

Compressive Sensing techniques are used in a short proof of Kashin’s decomposition theorem generalized to `p-spaces for p 1. The proof is based on the observation that the null-space of a properly-sized matrix with restricted isometry property is almost Euclidean when endowed with the `p-quasinorm.

PERTURBATIONS OF MEASUREMENT MATRICES AND DICTIONARIES IN COMPRESSED SENSING by Akram Aldroubi, Xuemei Chen, and Alexander Powell. The abstract reads:

The compressed sensing problem for redundant dictionaries aims to use a small number of linear measurements to represent signals that are sparse with respect to a general dictionary. Under an appropriate restricted isometry property for a dictionary, reconstruction methods based on l_q minimization are known to provide an effective signal recovery tool in this setting. This note explores conditions under which l_q minimization is robust to measurement noise, and stable with respect to perturbations of the sensing matrix A and the dictionary D. We propose a new condition, the D null space property, which guarantees that l_q minimization produces solutions that are robust and stable against perturbations of A and D. We also show that l_q minimization is jointly stable with respect to imprecise knowledge of the measurement matrix A and the dictionary D when A satisfi es the restricted isometry property

Matrix Probing and its Conditioning by Jiawei Chiu and Laurent Demanet. The abstract reads:

When a matrix A with n columns is known to be well approximated by a linear combination of basis matrices B1, . . . , Bp, we can apply A to a random vector and solve a linear system to recover this linear combination. The same technique can be used to recover an approximation to A^−1 A basic question is whether this linear system is invertible and well-conditioned. In this paper, we show that if the Gram matrix of the Bj ’s is sufficiently well-conditioned and each Bj has a high numerical rank, then n ∝ p log2p will ensure that the linear system is well-conditioned with high probability. Our main application is probing linear operators with smooth pseudodifferential symbols such as the wave equation Hessian in seismic imaging [6]. We demonstrate numerically that matrix probing can also produce good preconditioners for inverting elliptic operators in variable media.

Robust Lower Bounds for Communication and Stream Computation by Amit Chakrabarti, Graham Cormode, Andrew McGregor. (the slides are here). The abstract reads:

We study the communication complexity of evaluating functions when the input data is randomly allocated (according to some known distribution) amongst two or more players, possibly with information overlap. This naturally extends previously studied variable partition models such as the best-case and worst-case partition models [36, 33]. We aim to understand whether the
hardness of a communication problem holds for almost every allocation of the input, as opposed to holding for perhaps just a few atypical partitions. A key application is to the heavily studied data stream model. There is a strong connection between our communication lower bounds and lower bounds in the data stream model that are “robust” to the ordering of the data. That is, we prove lower bounds for when the order of the items in the stream is chosen not adversarially but rather uniformly (or near-uniformly) from the set of all permutations. This random-order data stream model has attracted recent interest, since lower bounds here give stronger evidence for the inherent hardness of streaming problems. Our results include the first random-partition communication lower bounds for problems including multi-party set disjointness and gap-Hamming-distance. Both are tight. We also extend and improve previous results [23, 8] for a form of pointer jumping that is relevant to the problem of selection (in particular, median finding). Collectively, these results yield lower bounds for a variety of problems in the random-order data stream model, including estimating the number of distinct elements, approximating frequency moments, and quantile estimation.

Filtering via a Reference Set by Ali Haddad, Dan Kushnir, Ronald Coifman. The abstract reads:

Patch-based de-noising algorithms and patch manifold smoothing have emerged as efficient de-noising methods. This paper provides a new insight on these methods, such as the Non Local Means [1] or the image graph de-noising [8], by showing its use for ltering a selected pattern.

Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions by Alekh Agarwal, Sahand Negahban, Martin J. Wainwright. The abstract reads:

We analyze a class of estimators based on convex relaxation for solving high-dimensional matrix decomposition problems. The observations are the noisy realizations of the sum of an (appproximately) low rank matrix $\Theta^\star$ with a second matrix $\Gamma^\star$ endowed with a complementary form of low-dimensional structure. We derive a general theorem that gives upper bounds on the Frobenius norm error for an estimate of the pair $(\Theta^\star, \Gamma^\star)$ obtained by solving a convex optimization problem that combines the nuclear norm with a general decomposable regularizer. We then specialize this result to two cases that have been studied in the context of robust PCA: low rank plus an entrywise sparse matrix, and low rank plus a columnwise sparse matrix. For both models, our theory yields non-asymptotic Frobenius error bounds for both for deterministic and stochastic noise matrices, and applies to matrices $\Theta^\star$ that can be exactly or approximately low rank, and matrices $\Gamma^\star$ that can be exactly or approximately sparse. Moreover, for the case of stochastic noise matrices, we establish matching lower bounds on the minimax error, showing that our results cannot be improved beyond constant factors. The sharpness of our theoretical predictions is confirmed by numerical simulations.

Learning pattern transformation manifolds with parametric atom selection by Vural, Elif ; Frossard, Pascal. The abstract reads:

We address the problem of building a manifold in order to represent a set of geometrically transformed images by selecting a good common sparse approximation of them with parametric atoms. We propose a greedy method to construct a representative pattern such that the total distance between the transformation manifold of the representative pattern and the input images is minimized. In the progressive construction of the pattern we select atoms from a continuous dictionary by optimizing the atom parameters. Experimental results suggest that the representative pattern built with the proposed method provides an accurate representation of data, where the invariance to geometric transformations is achieved due to the
transformation manifold model.

A Regularization Framework for Mobile Social Network Analysis by Dong, Xiaowen ; Frossard, Pascal ; Vandergheynst, Pierre ; Nefedov, Nikolai. The abstract reads:

Mobile phone data provides rich dynamic information on human activities in social network analysis. In this paper, we represent data from two different modalities as a graph and functions defined on the vertex set of the graph. We propose a regularization framework for the joint utilization of these two modalities of data, which enables us to model evolution of social network information and efficiently classify relationships among mobile phone users. Simulations based on real world data demonstrate the potential application of our model in dynamic scenarios, and present competitive results to baseline methods for combining multimodal data in the learning and clustering communities.

Exemplar-based sparse representations for noise robust automatic speech recognition by Jort F. Gemmeke, Tuomas Virtanen, Antti Hurmalainen. The abstract reads:

This paper proposes to use exemplar-based sparse representations for noise robust automatic speech recognition. First, we describe how speech can be modelled as a linear combination of a small number of exemplars from a large speech exemplar dictionary. The exemplars are time-frequency patches of real speech, each spanning multiple time frames. We then propose to model speech corrupted by additive noise as a linear combination of noise and speech exemplars, and we derive an algorithm for recovering this sparse linear combination of exemplars from the observed noisy speech. We describe how the framework can be used for doing hybrid exemplar-based/HMM recognition by using the exemplar-activations together with the phonetic information associated with the exemplars. As an alternative to hybrid recognition, the framework also allows us to take a source separation approach which enables exemplar-based feature enhancement as well as missing data mask estimation. We evaluate the performance of these exemplarbased methods in connected digit recognition on the AURORA-2 database. Our results show that the hybrid system performed substantially better than source separation or missing data mask estimation at lower SNRs, achieving up to 57.1% accuracy at SNR= -5 dB. Although not as effective as two baseline recognisers at higher SNRs, the novel approach offers a promising direction of future research on exemplar-based ASR

Data Separation by Sparse Representations by Gitta Kutyniok. The abstract reads:

Recently, sparsity has become a key concept in various areas of applied mathematics, computer science, and electrical engineering. One application of this novel methodology is the separation of data, which is composed of two (or more) morphologically distinct constituents. The key idea is to carefully select representation systems each providing sparse approximations of one of the components. Then the sparsest coefficient vector representing the data within the composed - and therefore highly redundant - representation system is computed by $\ell_1$ minimization or thresholding. This automatically enforces separation. This paper shall serve as an introduction to and a survey about this exciting area of research as well as a reference for the state-of-the-art of this research field. It will appear as a chapter in a book on "Compressed Sensing: Theory and Applications" edited by Yonina Eldar and Gitta Kutyniok.

Optimal Quantization for Compressive Sensing under Message Passing Reconstruction by Ulugbek Kamilov, Vivek K Goyal, Sundeep Rangan. The abstract reads:

We consider the optimal quantization of compressive sensing measurements following the work on generalization of relaxed belief propagation (BP) for arbitrary measurement channels. Relaxed BP is an iterative reconstruction scheme inspired by message passing algorithms on bipartite graphs. Its asymptotic error performance can be accurately predicted and tracked through the state evolution formalism. We utilize these results to design mean-square optimal scalar quantizers for relaxed BP signal reconstruction and empirically demonstrate the superior error performance of the resulting quantizers.

Rank Aggregation via Nuclear Norm Minimization by David F. Gleich, Lek-Heng Lim. The abstract reads:

The process of rank aggregation is intimately intertwined with the structure of skew-symmetric matrices. We apply recent advances in the theory and algorithms of matrix completion to skew-symmetric matrices. This combination of ideas produces a new method for ranking a set of items. The essence of our idea is that a rank aggregation describes a partially filled skew-symmetric matrix. We extend an algorithm for matrix completion to handle skew-symmetric data and use that to extract ranks for each item. Our algorithm applies to both pairwise comparison and rating data. Because it is based on matrix completion, it is robust to both noise and incomplete data. We show a formal recovery result for the noiseless case and present a detailed study of the algorithm on synthetic data and Netflix ratings.

Measurement Matrix Design for Compressive Sensing Based MIMO Radar by Yao Yu, Athina P. Petropulu, H.Vincent. Poor. The abstract reads:

In colocated multiple-input multiple-output (MIMO) radar using compressive sensing (CS), a receive node compresses its received signal via a linear transformation, referred to as measurement matrix. The samples are subsequently forwarded to a fusion center, where an L1-optimization problem is formulated and solved for target information. CS-based MIMO radar exploits the target sparsity in the angle-Doppler-range space and thus achieves the high localization performance of traditional MIMO radar but with many fewer measurements. The measurement matrix is vital for CS recovery performance. This paper considers the design of measurement matrices that achieve an optimality criterion that depends on the coherence of the sensing matrix (CSM) and/or signal-to-interference ratio (SIR). The first approach minimizes a performance penalty that is a linear combination of CSM and the inverse SIR. The second one imposes a structure on the measurement matrix and determines the parameters involved so that the SIR is enhanced. Depending on the transmit waveforms, the second approach can significantly improve SIR, while maintaining CSM comparable to that of the Gaussian random measurement matrix (GRMM). Simulations indicate that the proposed measurement matrices can improve detection accuracy as compared to a GRMM.

Verifiable and Computable $\ell_\infty$ Performance Evaluation of $\ell_1$ Sparse Signal Recovery by Gongguo Tang, Arye Nehorai. The abstract reads:

In this paper, we develop verifiable and computable performance analysis of the $\ell_\infty$ norms of the recovery errors for $\ell_1$ minimization algorithms. We define a family of goodness measures for arbitrary sensing matrices as a set of optimization problems, and design algorithms with a theoretical global convergence guarantee to compute these goodness measures. The proposed algorithms solve a series of second-order cone programs, or linear programs. As a by-product, we implement an efficient algorithm to verify a sufficient condition for exact $\ell_1$ recovery in the noise-free case. This implementation performs orders-of-magnitude faster than the state-of-the-art techniques. We derive performance bounds on the $\ell_\infty$ norms of the recovery errors in terms of these goodness measures. We establish connections between other performance criteria e.g., the $\ell_2$ norm, $\ell_1$ norm, and support recovery) and the $\ell_\infty$ norm in a tight manner. We also analytically demonstrate that the developed goodness measures are non-degenerate for a large class of random sensing matrices, as long as the number of measurements is relatively large. Numerical experiments show that, compared with the restricted isometry based performance bounds, our error bounds apply to a wider range of problems and are tighter, when the sparsity levels of the signals are relatively low.

SPARSE SPECTRAL FACTORIZATION: UNICITY AND RECONSTRUCTION ALGORITHMS by Yue M. Lu, and Martin Vetterli. The abstract reads:

Spectral factorization is a classical tool in signal processing and communications. It also plays a critical role in X-ray crystallography, in the context of phase retrieval. In this work, we study the problem of sparse spectral factorization, aiming to recover a one-dimensional sparse signal from its autocorrelation. We present a sufficient condition for the recovery to be unique, and propose an iterative algorithm that can obtain the original signal (up to a sign change, time-shift and time-reversal). Numerical simulations verify the effectiveness of the proposed algorithm.

Multichannel Sampling with Unknown Gains and Offsets: A Fast Reconstruction Algorithmby Yue M. Lu, and Martin Vetterli.. The abstract reads:

We study a multichannel sampling scheme, where different channels observe scaled and shifted versions of a common bandlimited signal. The channel gains and offsets are unknown a priori, and each channel samples at sub-Nyquist rates. This setup appears in many practical signal processing applications, including time-interleaved ADC with timing skews, unsynchronized distributed sampling in sensor networks, and superresolution imaging. In this paper, we propose a new algorithm to efficiently estimate the unknown channel gains and offsets. Key to our algorithm is a novel linearization technique, which converts a system of trigonometric polynomial equations of the unknown parameters to an overparameterized linear system. The computation steps of the proposed algorithm boil down to forming a fixed data matrix from the discrete-time Fourier transforms of the observed channel samples and computing the singular value decomposition of that matrix. Numerical simulations verify the effectiveness, efficiency, and robustness of the proposed algorithm in the presence of noise. In the high SNR regime (40 dB and above), the proposed algorithm significantly outperforms a previous method in the literature in terms of estimation accuracy, at the same time being three orders of magnitudes faster.

LEARNING SPARSE SYSTEMS AT SUB-NYQUIST RATES: A FREQUENCY-DOMAIN APPROACH by Martin McCormick, Yue M. Lu, and Martin Vetterli. The abstract reads:

We propose a novel algorithm for sparse system identification in the frequency domain. Key to our result is the observation that the Fourier transform of the sparse impulse response is a simple sum of complex exponentials, whose parameters can be efficiently determined from only a narrow frequency band. From this perspective, we present a sub-Nyquist sampling scheme, and show that the original continuous-time system can be learned by considering an equivalent low-rate discrete system. The impulse response of that discrete system can then be adaptively obtained by a novel frequency-domain LMS filter, which exploits the parametric structure of the model. Numerical experiments confirm the effectiveness of the proposed scheme for sparse system identification tasks.

Occlusion Detection and Motion Estimation via Convex Optimization by Michalis Raptis, Alper Ayvaci and Stefano Soatto. The abstract reads:

We tackle the problem of detecting occluded regions in a video stream. Under assumptions of Lambertian reflection and static illumination, the task can be posed as a variational optimization problem, and its solution approximated using convex minimization. We describe efficient numerical schemes that reach the global optimum of the relaxed cost functional, for any number of independently moving objects, and any number of occlusion layers. We test the proposed algorithm on benchmark datasets, expanded to enable evaluation of occlusion detection performance, in addition to optical flow.

LOCALIZING POINT SOURCES IN DIFFUSION FIELDS FROM SPATIOTEMPORAL SAMPLES by Yue M. Lu,, Pier Luigi Dragotti and Martin Vetterli The abstract reads:

Consider a diffusion field induced by a finite number of localized and instantaneous sources. In this paper, we study the problem of estimating these sources (including their intensities, spatial locations, and activation time) from the spatiotemporal samples taken by a network of spatially distributed sensors. We propose two estimation algorithms, depending on whether the activation time of the sources is known. For the case of known activation time, we present an annihilating filter based method to estimate the Euclidean distances between the sources and sensors, which can be subsequently used to localize the sources. For the case of a single source but with unknown activation time, we show that the diffusion field at any spatial location is a scaled and shifted version of a common prototype function, and that this function is the unique solution to a particular differential equation. This observation leads to an efficient algorithm that can estimate the unknown parameters of the source by solving a system of linear equations. For both algorithms proposed in this work, the minimum number of sensors required is d + 1, where d is the spatial dimension of the field. This requirement is independent of the number of active sources.

Interest Zone Matrix Approximation by Gil Shabat and Amir Averbuch. The abstract reads:

We present an algorithm for low rank approximation of matrices where only some of the entries in the matrix are taken into consideration. This algorithm appears in recent literature under di erent names, where it is described as an EM based algorithm that maximizes the likelihood for the missing entries without any relation for the mean square error minimization. When the algorithm is minimized from a mean-square-error point of view, we prove that the error produced by the algorithm is monotonically decreasing. It guarantees to converge to a local MSE minimum. We also show that an extension of the EM based algorithm for weighted low rank approximation, which appeared in recent literature, claiming that it converges to a local minimum of the MSE is wrong. Finally, we show the use of the algorithm in di erent
applications for physics, electrical engineering and data interpolation

Patch-to-Tensor Embedding by Guy Wolf Moshe Salhov Amir Averbuch. The abstract reads:

A popular approach to deal with the \curse of dimensionality" in relation with the analysis of high-dimensional datasets, is to assume that points in these datasets lie on a low-dimensional manifold immersed in a high-dimensional ambient space. Kernel methods operate on this assumption and introduce the notion of local affinities between data-points via the construction of a suitable kernel. Spectral analysis of this kernel provides a global, preferably low-dimensional, coordinate system that preserves the qualities of the manifold. In this paper, we extend the scalar relations used in this framework to matrix relations, which can encompass multidimensional similarities between local neighborhoods of points on the manifold. We utilize the diffusion maps method together with linear-projection operators between tangent spaces of the manifold to construct a super-kernel that represents these relations. The properties of the presented super-kernels are explored and their spectral decompositions are utilized to embed the patches of the manifold into a tensor space in which the relations between them are revealed.

Cooperative Wideband Spectrum Sensing for the Centralized Cognitive Radio Network by Peng Zhang, Robert Qiu. The abstract reads:

Various primary user (PU) radios have been allocated into fixed frequency bands in the whole spectrum. A cognitive radio network (CRN) should be able to perform the wideband spectrum sensing (WSS) to detect temporarily unoccupied frequency bands. We summarize four occupancy features for the frequency bands. 1. The occupancy is sparse; 2. The frequency band allocation information is fixed and common; 3. There are three categories for the frequency band usages; 4. The occupied frequency bands are common in the CRN. For the first time, we consider all features as the prior knowledge in the compressed sensing based cooperative WSS (CWSS) algorithm design for a centralized CRN. We propose a modified orthogonal matching pursuit (Mod-OMP) algorithm and a modified simultaneous orthogonal matching pursuit (Mod-SOMP) algorithm for the CWSS. We compare the CWSS performance of Mod-OMP/Mod-SOMP with the original OMP/SOMP and show the performance improvements.

Subspace Expanders and Matrix Rank Minimization by Amin Khajehnejad, Samet Oymak, Babak Hassibi. The abstract reads:

Matrix rank minimization (RM) problems recently gained extensive attention due to numerous applications in machine learning, system identification and graphical models. In RM problem, one aims to find the matrix with the lowest rank that satisfies a set of linear constraints. The existing algorithms include nuclear norm minimization (NNM) and singular value thresholding. Thus far, most of the attention has been on i.i.d. Gaussian measurement operators. In this work, we introduce a new class of measurement operators, and a novel recovery algorithm, which is notably faster than NNM. The proposed operators are based on what we refer to as subspace expanders, which are inspired by the well known expander graphs based measurement matrices in compressed sensing. We show that given an $n\times n$ PSD matrix of rank $r$, it can be uniquely recovered from a minimal sampling of $O(nr)$ measurements using the proposed structures, and the recovery algorithm can be cast as matrix inversion after a few initial processing steps.

Random Tight Frames by Martin Ehler. The abstract reads:

We introduce probabilistic frames to study finite frames whose elements are chosen at random. While finite tight frames generalize orthonormal bases by allowing redundancy, independent, uniformly distributed points on the sphere approximately form a finite unit norm tight frame (FUNTF). In the present paper, we develop probabilistic versions of tight frames and FUNTFs to significantly weaken the requirements on the random choice of points to obtain an approximate finite tight frame. Namely, points can be chosen from any probabilistic tight frame, they do not have to be identically distributed, nor have unit norm. We also observe that classes of random matrices used in compressed sensing are induced by probabilistic tight frames.

Improved RIP Analysis of Orthogonal Matching Pursuit by Ray Maleh. The abstract reads:

Orthogonal Matching Pursuit (OMP) has long been considered a powerful heuristic for attacking compressive sensing problems; however, its theoretical development is, unfortunately, somewhat lacking. This paper presents an improved Restricted Isometry Property (RIP) based performance guarantee for T-sparse signal reconstruction that asymptotically approaches the conjectured lower bound given in Davenport et al. We also further extend the state-of-the-art by deriving reconstruction error bounds for the case of general non-sparse signals subjected to measurement noise. We then generalize our results to the case of K-fold Orthogonal Matching Pursuit (KOMP). We finish by presenting an empirical analysis suggesting that OMP and KOMP outperform other compressive sensing algorithms in average case scenarios. This turns out to be quite surprising since RIP analysis (i.e. worst case scenario) suggests that these matching pursuits should perform roughly T^0.5 times worse than convex optimization, CoSAMP, and Iterative Thresholding.

Structure-Aware Sampling: Flexible and Accurate Summarization by Edith Cohen, Graham Cormode, Nick Duffield. The abstract reads:

In processing large quantities of data, a fundamental problem is to obtain a summary which supports approximate query answering. Random sampling yields flexible summaries which naturally support subset-sum queries with unbiased estimators and well-understood confidence bounds.Classic sample-based summaries, however, are designed for arbitrary subset queries and are oblivious to the structure in the set of keys. The particular structure, such as hierarchy, order, or product space (multi-dimensional), makes range queries much more relevant for most analysis of the data.
Dedicated summarization algorithms for range-sum queries have also been extensively studied. They can outperform existing sampling schemes in terms of accuracy on range queries per summary size. Their accuracy, however, rapidly degrades when, as is often the case, the query spans multiple ranges. They are also less flexible - being targeted for range sum queries alone - and are often quite costly to build and use.
In this paper we propose and evaluate variance optimal sampling schemes that are structure-aware. These summaries improve over the accuracy of existing structure-oblivious sampling schemes on range queries while retaining the benefits of sample-based summaries: flexible summaries, with high accuracy on both range queries and arbitrary subset queries.

Sparse Bayesian Methods for Low-Rank Matrix Estimation by S. Derin Babacan, Martin Luessi, Rafael Molina, Aggelos K. Katsaggelos. The abstract reads:

Recovery of low-rank matrices has recently seen significant activity in many areas of science and engineering, motivated by recent theoretical results for exact reconstruction guarantees and interesting practical applications. A number of methods have been developed for this recovery problem. However, a principled method for choosing the unknown target rank is generally not provided. In this paper, we present novel recovery algorithms for estimating low-rank matrices in matrix completion and robust principal component analysis based on sparse Bayesian learning (SBL) principles. Starting from a matrix factorization formulation and enforcing the low-rank constraint in the estimates as a sparsity constraint, we develop an approach that is very effective in determining the correct rank while providing high recovery performance. We provide connections with existing methods in other similar problems and empirical results and comparisons with current state-of-the-art methods that illustrate the effectiveness of this approach.

An Adaptive Inverse Scale Space Method for Compressed Sensing by Martin Burger, Michael Moller, Martin Benning, Stanley Osher. The abstract reads:

In this paper we introduce a novel adaptive approach for solving L_1-minimization problems as frequently arising in compressed sensing, which is based on the recently introduced inverse scale space method. The scheme allows to e ciently compute minimizers by solving a sequence of low-dimensional nonnegative least-squares problems. We provide a detailed convergence analysis in a general setup as well as re fined results under special conditions. In addition we discuss experimental observations in several numerical examples.

RECONSTRUCTING AND SEGMENTING HYPERSPECTRAL IMAGES FROM COMPRESSED MEASUREMENTS by Qiang Zhang, Robert Plemmons, David Kittle, David Brady, Sudhakar Prasad. The abstract reads:

A joint reconstruction and segmentation model for hyperspectral data obtained from a compressive measurement system is described. Although hyperspectral imaging (HSI) technology has incredible potential, its utility is currently limited because of the enormous quantity and complexity of the data it gathers. Yet, often the scene to be reconstructed from the HSI data contains far less information, typically consisting of spectrally and spatially homogeneous segments that can be represented sparsely in an appropriate basis. Such vast informational redundancy thus implicitly contained in the HSI data warrants a compressed sensing (CS) strategy that acquires appropriately coded spectral-spatial data from which one can reconstruct the original image more efficiently while still enabling target identification procedures. A codedaperture snapshot spectral imager (CASSI) that collects compressed measurements is considered here, and a joint reconstruction and segmentation model for hyperspectral data obtained from CASSI compressive measurements is described. Promising test results on simulated and real data are reported.

Belief propagation for joint sparse recovery by Jongmin Kim, Woohyuk Chang, Bangchul Jung, Dror Baron, Jong Chul Ye. The abstract reads:

Compressed sensing (CS) demonstrates that sparse signals can be recovered from underdetermined linear measurements. We focus on the joint sparse recovery problem where multiple signals share the same common sparse support sets, and they are measured through the same sensing matrix. Leveraging a recent information theoretic characterization of single signal CS, we formulate the optimal minimum mean square error (MMSE) estimation problem, and derive a belief propagation algorithm, its relaxed version, for the joint sparse recovery problem and an approximate message passing algorithm. In addition, using density evolution, we provide a sufficient condition for exact recovery.

Compressive MUSIC with optimized partial support for joint sparse recovery by Jong Min Kim, Ok Kyun Lee, Jong Chul Ye. The abstarct reads:

Multiple measurement vector (MMV) problem addresses the identification of unknown input vectors that share common sparse support. The MMV problems had been traditionally addressed either by sensor array signal processing or compressive sensing. However, recent breakthrough in this area such as compressive MUSIC (CS-MUSIC) or subspace-augumented MUSIC (SA-MUSIC) optimally combines the compressive sensing (CS) and array signal processing such that $k-r$ supports are first found by CS and the remaining $r$ supports are determined by generalized MUSIC criterion, where $k$ and $r$ denote the sparsity and the independent snapshots, respectively. Even though such hybrid approach significantly outperforms the conventional algorithms, its performance heavily depends on the correct identification of $k-r$ partial support by compressive sensing step, which often deteriorate the overall performance. The main contribution of this paper is, therefore, to show that as long as $k-r+1$ correct supports are included in any $k$-sparse CS solution, the optimal $k-r$ partial support can be found using a subspace fitting criterion, significantly improving the overall performance of CS-MUSIC. Furthermore, unlike the single measurement CS counterpart that requires infinite SNR for a perfect support recovery, we can derive an information theoretic sufficient condition for the perfect recovery using CS-MUSIC under a {\em finite} SNR scenario.

Density Evolution Analysis of Node-Based Verification-Based Algorithms in Compressed Sensing by Yaser Eftekhari, Anoosheh Heidarzadeh, Amir H. Banihashemi, Ioannis Lambadaris. The abstract reads:

In this paper, we present a new approach for the analysis of iterative node-based verification-based (NB-VB) recovery algorithms in the context of compressive sensing. These algorithms are particularly interesting due to their low complexity (linear in the signal dimension $n$). The asymptotic analysis predicts the fraction of unverified signal elements at each iteration $\ell$ in the asymptotic regime where $n \rightarrow \infty$. The analysis is similar in nature to the well-known density evolution technique commonly used to analyze iterative decoding algorithms. To perform the analysis, a message-passing interpretation of NB-VB algorithms is provided. This interpretation lacks the extrinsic nature of standard message-passing algorithms to which density evolution is usually applied. This requires a number of non-trivial modifications in the analysis. The analysis tracks the average performance of the recovery algorithms over the ensembles of input signals and sensing matrices as a function of $\ell$. Concentration results are devised to demonstrate that the performance of the recovery algorithms applied to any choice of the input signal over any realization of the sensing matrix follows the deterministic results of the analysis closely. Simulation results are also provided which demonstrate that the proposed asymptotic analysis matches the performance of recovery algorithms for large but finite values of $n$. Compared to the existing technique for the analysis of NB-VB algorithms, which is based on numerically solving a large system of coupled differential equations, the proposed method is much simpler and more accurate.

Phase Transition in Limiting Distributions of Coherence of High-Dimensional Random Matrices by Tony Cai, Tiefeng Jiang. The abstract reads:

The coherence of a random matrix, which is defined to be the largest magnitude of the Pearson correlation coefficients between the columns of the random matrix, is an important quantity for a wide range of applications including high-dimensional statistics and signal processing. Inspired by these applications, this paper studies the limiting laws of the coherence of $n\times p$ random matrices for a full range of the dimension $p$ with a special focus on the ultra high-dimensional setting. Assuming the columns of the random matrix are independent random vectors with a common spherical distribution, we give a complete characterization of the behavior of the limiting distributions of the coherence. More specifically, the limiting distributions of the coherence are derived separately for three regimes: $\frac{1}{n}\log p \to 0$, $\frac{1}{n}\log p \to \beta\in (0, \infty)$, and $\frac{1}{n}\log p \to\infty$. The results show that the limiting behavior of the coherence differs significantly in different regimes and exhibits interesting phase transition phenomena as the dimension $p$ grows as a function of $n$. Applications to statistics and compressed sensing in the ultra high-dimensional setting are also discussed.

Limiting Laws of Coherence of Random Matrices with Applications to Testing Covariance Structure and Construction of Compressed Sensing Matrices by Tony Cai, 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\times p$ random matrix in the high-dimensional setting where $p$ can be much larger than $n$. Both the law of large numbers and the 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. We also apply the asymptotic results to the construction of compressed sensing matrices.

Modified Orthogonal Matching Pursuit Algorithm for Cognitive Radio Wideband Spectrum Sensing by Peng Zhang, Robert Qiu. The abstract reads:

Sampling rate is the bottleneck for spectrum sensing over multi-GHz bandwidth. Recent progress in compressed sensing (CS) initialized several sub-Nyquist rate approaches to overcome the problem. However, efforts to design CS reconstruction algorithms for wideband spectrum sensing are very limited. It is possible to further reduce the sampling rate requirement and improve reconstruction performance via algorithms considering prior knowledge of cognitive radio spectrum usages. In this paper, we group the usages of cognitive radio spectrum into three categories and propose a modified orthogonal matching pursuit (OMP) algorithm for wideband spectrum sensing. Simulation results show that this modified OMP algorithm outperforms two modified basis pursuit de-noising (BPDN) algorithms in terms of reconstruction performance and computation time.

Bounds on the Reconstruction of Sparse Signal Ensembles from Distributed Measurements by Marco F. Duarte, Michael B. Wakin, Dror Baron, Shriram Sarvotham, Richard G. Baraniuk. The abstract reads:

In compressive sensing, a small collection of linear projections of a sparse signal contains enough information to permit signal recovery. Distributed compressive sensing (DCS) extends this framework, allowing a correlated ensemble of sparse signals to be jointly recovered from a collection of separately acquired compressive measurements. In this paper, we introduce an ensemble sparsity model for capturing the intra- and inter-signal correlations within a collection of sparse signals. For strictly sparse signals obeying an ensemble sparsity model, we characterize the fundamental number of noiseless measurements that each sensor must collect to ensure that the signals are jointly recoverable. Our analysis is based on a novel bipartite graph representation that links the sparse signal coefficients with the measurements obtained for each signal.

A Novel Sparsity-Promoted Approach to State Estimation from Dynamic Observation by Lianlin Li, Behnam. Jafarpour. The abstract reads:

The problem of time-varying signal estimation or state estimation from dynamic observation is encountered in many applications. Among well-developed approaches the Kalman filter-type approaches are the most popular and have played an important role of estimating dynamic signal from sequential observations. However, when the number of observations at each time step is highly limited, they usually take too many time steps to catch up with the true value with satisfied accuracy, even fail to do that in many cases. How to address this problem has become appealing for many practical applications, for example, real-time radar tracing, navigation, medical images, and so on. A feasible strategy is to incorporate other efficient prior information into Kalman filter (KF) approach. An elegant achievement coming from compressed sensing (CS) recently developed shows that the signal which is sparse or compressible in some transform domain can be exactly reconstructed from highly limited observations through the use of sparsity constraint regularization. Accordingly, one key to the estimation of dynamic statess how to efficiently deal with sparsity of unknown state and prior information coming from forecast step simultaneously. This paper proposes a novel approach which is the heuristic generalization of the well-known Kalman filter (for convenience, we call it sparsity-promoted Kalman filter, or SKF). Basically, the proposed three-step sparsity-promoted Kalman filter consists of sparse processing following the forecast and prediction steps involved in standard KF procedure. The primary results provided in this paper show the proposed SKF is highly efficient, and can bring us important improvement on the results generated by standard Kalman filter, or only sparsity-promoted reconstruction.

And finally, just the abstract : SUBTYPING OF LEUKEMIA WITH GENE EXPRESSION ANALYSIS USING COMPRESSIVE SENSING METHOD by Tang W, Cao H, Wang Y. The abstract reads:

Detection of different types of cancers is important in clinical diagnosis and treatment. Leukemia is one of the cancers that has different subtypes: acute lymphoblastic leukemia (ALL) and acute myeloid leukemia (AML). The detection of these subtypes according to different genetic markups in leukemia patients will lead to individualized therapies. Gene expression analysis has been used for the study of leukemia patients, and a variety of approaches have been developed to classify leukemia subtypes. In this paper, we propose a novel compressive sensing (CS) based approach for the subtyping of leukemia. The CS method is an emerging approach in statistics and mathematical signal analysis, which enables the reconstruction of signals from a small set of incoherent projections. We develop a CS based detector to classify ALL and AML, based on 1 or 2 gene expression data samples out of 7129 samples. The accuracy of the classification is as high as 97% evaluated with cross validation method among 38 subjects (27 ALL and 11 AML), and 94% evaluated with an independent collection (21 ALL and 14 AML). This work demonstrates that the CS method can be effectively used to detect subtypes of leukemia subjects, implying improved accuracy of diagnosing leukemia patients.