This Week in Compressive Sensing

In the Compressive Sensing Group on LinkedIn, Ganesan Ramachandran is looking for PhD intern in compressive sampling but you have to respond in the thread. Today's entry could definitely use one of the papragraph title of the first paper, 

Sparsity is not enough

Enjoy!

Dirk already talked about it, but here is the paper. At last some sort of theoretical justification for using the TV-norm: Towards a Mathematical Theory of Super-Resolution by Emmanuel Candes, Carlos Fernandez-Granda. The abstract reads:

This paper develops a mathematical theory of super-resolution. Broadly speaking, super-resolution is the problem of recovering the fine details of an object---the high end of its spectrum---from coarse scale information only---from samples at the low end of the spectrum. Suppose we have many point sources at unknown locations in $[0,1]$ and with unknown complex-valued amplitudes. We only observe Fourier samples of this object up until a frequency cut-off $f_c$. We show that one can super-resolve these point sources with infinite precision---i.e. recover the exact locations and amplitudes---by solving a simple convex program. This holds provided that the distance between sources is at least $2/f_c$. This result extends to higher dimensions and other models. In one dimension for instance, it is possible to recover a piecewise smooth function by resolving the discontinuity points with infinite precision as well. We also show that the theory and methods are robust to noise. In particular, we develop some theoretical results explaining how the accuracy of the super-resolved signal is expected to degrade when both the noise level and the {\em super-resolution factor} vary.

Atomic norm denoising with applications to line spectral estimation by Badri Narayan Bhaskar, Gongguo Tang, Benjamin Recht. The abstract reads:

The sub-Nyquist estimation of line spectra is a classical problem in signal processing, but currently popular subspace-based techniques have few guarantees in the presence of noise and rely on a priori knowledge about system model order. Motivated by recent work on atomic norms in inverse problems, we propose a new approach to line spectral estimation that provides theoretical guarantees for the mean-squared-error performance in the presence of noise and without advance knowledge of the model order. We propose an abstract theory of denoising with atomic norms and specialize this theory to provide a convex optimization problem for estimating the frequencies and phases of a mixture of complex exponentials with guaranteed bounds on the mean-squared error. We show that the associated convex optimization problem, called "Atomic norm Soft Thresholding" (AST), can be solved in polynomial time via semidefinite programming. For very large scale problems we provide an alternative, efficient algorithm, called "Discretized Atomic norm Soft Thresholding" (DAST), based on the Fast Fourier Transform that achieves nearly the same error rate as that guaranteed by the semidefinite programming approach. We compare both AST and DAST with Cadzow's canonical alternating projection algorithm and demonstrate that AST outperforms DAST which outperforms Cadzow in terms of mean-square reconstruction error over a wide range of signal-to-noise ratios. For very large problems DAST is considerably faster than both AST and Cadzow.

Linear System Identification via Atomic Norm Regularization by Parikshit Shah,  Badri Narayan Bhaskar, Gongguo Tang, Benjamin Recht. The abstract reads: 

This paper proposes a new algorithm for linear system identification from noisy measurements. The proposed algorithm balances a data fidelity term with a norm induced by the set of single pole filters. We pose a convex optimization problem that approximately solves the atomic norm minimization problem and identifies the unknown system from noisy linear measurements. This problem can be solved efficiently with standard, freely available software. We provide rigorous statistical guarantees that explicitly bound the estimation error (in the H_2-norm) in terms of the stability radius, the Hankel singular values of the true system and the number of measurements. These results in turn yield complexity bounds and asymptotic consistency. We provide numerical experiments demonstrating the efficacy of our method for estimating linear systems from a variety of linear measurements.

Adaptive group testing as channel coding with feedback  by  Matthew Aldridge . The abstract reads:

Group testing is the combinatorial problem of identifying the defective items in a population by grouping items into test pools. Recently, nonadaptive group testing - where all the test pools must be decided on at the start - has been studied from an information theory point of view. Using techniques from channel coding, upper and lower bounds have been given on the number of tests required to accurately recover the defective set, even when the test outcomes can be noisy.

In this paper, we give the first information theoretic result on adaptive group testing - where the outcome of previous tests can influence the makeup of future tests. We show that adaptive testing does not help much, as the number of tests required obeys the same lower bound as nonadaptive testing. Our proof uses similar techniques to the proof that feedback does not improve channel capacity.

Probabilistic Recovery Guarantees for Sparsely Corrupted Signals  by  Graeme Pope, Annina Bracher, Christoph Studer . The abstract reads: 

We consider the recovery of sparse signals subject to sparse interference, as introduced in Studer et al., IEEE Trans. IT, 2012. We present novel probabilistic recovery guarantees for this framework, covering varying degrees of knowledge of the signal and interference support, which are relevant for a large number of practical applications. Our results assume that the sparsifying dictionaries are solely characterized by coherence parameters and we require randomness only in the signal and/or interference. The obtained recovery guarantees show that one can recover sparsely corrupted signals with overwhelming probability, even if the sparsity of both the signal and interference scale (near) linearly with the number of measurements.

Compressed Sensing for Denoising in Adaptive System Identification  by  Seyed Hossein Hosseini, Mahrokh G. Shayesteh. The abstract reads:

We propose a new technique for adaptive identification of sparse systems based on the compressed sensing (CS) theory. We manipulate the transmitted pilot (input signal) and the received signal such that the weights of adaptive filter approach the compressed version of the sparse system instead of the original system. To this end, we use random filter structure at the transmitter to form the measurement matrix according to the CS framework. The original sparse system can be reconstructed by the conventional recovery algorithms. As a result, the denoising property of CS can be deployed in the proposed method at the recovery stage. The experiments indicate significant performance improvement of proposed method compared to the conventional LMS method which directly identifies the sparse system. Furthermore, at low levels of sparsity, our method outperforms a specialized identification algorithm that promotes sparsity.

A study of the universal threshold in the L1 recovery by statistical mechanics  by  Koujin Takeda, Yoshiyuki Kabashima. The abstract reads:

We discuss the universality of the L1 recovery threshold in compressed sensing. Previous studies in the fields of statistical mechanics and random matrix integration have shown that L1 recovery under a random matrix with orthogonal symmetry has a universal threshold. This indicates that the threshold of L1 recovery under a non-orthogonal random matrix differs from the universal one. Taking this into account, we use a simple random matrix without orthogonal symmetry, where the random entries are not independent, and show analytically that the threshold of L1 recovery for such a matrix does not coincide with the universal one. The results of an extensive numerical experiment are in good agreement with the analytical results, which validates our methodology. Though our analysis is based on replica heuristics in statistical mechanics and is not rigorous, the findings nevertheless support the fact that the universality of the threshold is strongly related to the symmetry of the random matrix.

Application of Bayesian Hierarchical Prior Modeling to Sparse Channel Estimation  by  Niels Lovmand Pedersen, Carles Navarro Manchón, Dmitriy Shutin, Bernard Henri Fleury. The abstract reads:

Existing methods for sparse channel estimation typically provide an estimate computed as the solution maximizing an objective function defined as the sum of the log-likelihood function and a penalization term proportional to the l1-norm of the parameter of interest. However, other penalization terms have proven to have strong sparsity-inducing properties. In this work, we design pilot-assisted channel estimators for OFDM wireless receivers within the framework of sparse Bayesian learning by defining hierarchical Bayesian prior models that lead to sparsity-inducing penalization terms. The estimators result as an application of the variational message-passing algorithm on the factor graph representing the signal model extended with the hierarchical prior models. Numerical results demonstrate the superior performance of our channel estimators as compared to traditional and state-of-the-art sparse methods.

I caught this interesting tidbit. Beyond 4G: The future of wireless

Hospitals of the future 

While America’s technology infrastructure may be on sounder footing than elsewhere, it’s health care system is not, as current debates about Obamacare indicate. The national discussion around health care has sharpened public attention on medical records and how they’re maintained and systemized (or not, as the case may be). Dan Sodickson, director of NYU’s Langone Center for Biomedical Imaging, suggested how, in the hospital of the future, “information about the patient can flow with the patient as they move through the hospital.”

He also alerted attendees to the advances being made in compressed sensing. “Previously, you had to know what was in the image before you compressed it,” said Sodickson, but with compressed sensing, “we can acquire much less data and go much, much faster and still get the full image content.” That’s great news for patients who wish to decrease the time it takes to get an MRI. It also means improvements in digital photography.

Incorporation of prior knowledge in compressed sensing for faster acquisition of hyperpolarized gas images by S. Ajraoui,, J. Parra-Robles, J. M. Wild. The abstract reads:

Adding prior knowledge to compressed sensing reconstruction can improve image reconstruction. In this work, two approaches are investigated to improve reconstruction of two-dimensional hyperpolarized 3He lung ventilation images using prior knowledge. When compared against a standard compressed sensing reconstruction, the proposed methods allowed acquisition of images with higher under-sampling factors and reduction of the blurring effects that increase with higher reduction factors when fixed flip angles are used. These methods incorporate the prior knowledge of polarization decay of hyperpolarized 3He and the mutual anatomical information from a registered 1H image acquired in the same breath. Three times accelerated two-dimensional images reconstructed with compressed sensing and prior knowledge gave lower root-mean square error, than images reconstructed without introduction of any prior information. When introducing the polarization decay as prior knowledge, a significant improvement was achieved in the lung region, the root mean square value decreased by 45% and from the whole image by 36%. When introducing the mutual anatomical information as prior knowledge, the root mean square decreased by 21% over the lung region and by 15% over the whole image. 

Improved compressed sensing-based cone-beam CT reconstruction using adaptive prior image constraints by Ho Lee, Lei Xing, Ran Davidi, Ruijiang Li, Jianguo Qian and Rena Lee

Volumetric cone-beam CT (CBCT) images are acquired repeatedly during a course of radiation therapy and a natural question to ask is whether CBCT images obtained earlier in the process can be utilized as prior knowledge to reduce patient imaging dose in subsequent scans. The purpose of this work is to develop an adaptive prior image constrained compressed sensing (APICCS) method to solve this problem. Reconstructed images using full projections are taken on the first day of radiation therapy treatment and are used as prior images. The subsequent scans are acquired using a protocol of sparse projections. In the proposed APICCS algorithm, the prior images are utilized as an initial guess and are incorporated into the objective function in the compressed sensing (CS)-based iterative reconstruction process. Furthermore, the prior information is employed to detect any possible mismatched regions between the prior and current images for improved reconstruction. For this purpose, the prior images and the reconstructed images are classified into three anatomical regions: air, soft tissue and bone. Mismatched regions are identified by local differences of the corresponding groups in the two classified sets of images. A distance transformation is then introduced to convert the information into an adaptive voxel-dependent relaxation map. In constructing the relaxation map, the matched regions (unchanged anatomy) between the prior and current images are assigned with smaller weight values, which are translated into less influence on the CS iterative reconstruction process. On the other hand, the mismatched regions (changed anatomy) are associated with larger values and the regions are updated more by the new projection data, thus avoiding any possible adverse effects of prior images. The APICCS approach was systematically assessed by using patient data acquired under standard and low-dose protocols for qualitative and quantitative comparisons. The APICCS method provides an effective way for us to enhance the image quality at the matched regions between the prior and current images compared to the existing PICCS algorithm. Compared to the current CBCT imaging protocols, the APICCS algorithm allows an imaging dose reduction of 10–40 times due to the greatly reduced number of projections and lower x-ray tube current level coming from the low-dose protocol.

Application of compressed sensing in full-field structural health monitoring by Mulugeta Haile and Anindya Ghoshal. The abstract reads:

Embedded sensors are used in layers of composite structures to provide local damage detection. The presence of these sensors causes material and geometric discontinuities which in turn causes unwanted peaks of stress and strain with consequences on stiffness reduction. Often several of these sensors are embedded in structures aggregating the adverse effects of discontinuities to degrade the structural integrity. Structural damage is a sparse phenomenon and the mechanical metrics are smooth functions with few spikes near the location of damage. This sparsity and spikiness can be exploited to reduce the number of embedded sensors in composite structures. The goal of this paper is to adapt the compressed sensing theory and detect damage using far fewer sensors than conventionally possible. To demonstrate the efficacy of our approach, we performed a numerical experiment on a rectangular plate with a center hole, and have shown that the 2D strain-field can be recovered from few samples of discrete strain measurements acquired by embedded sensors.

A thesis: Compressive spectrum sensing for cognitive radio networks by Nakarmi, Ukash,The abstract reads::

Spectrum sensing is the most important part in cognitive radios. Wideband spectrum sensing requires high speed and large data samples. It makes sampling process challenging and expensive. In this thesis, we propose wideband spectrum sensing for cognitive radio using compressive sensing to address challenges in sampling and data acquisition during spectrum sensing. Compressive sensing based spectrum sensing for a single network is extended to large frequency overlapping networks and joint reconstruction scheme is developed to enhance the performance at minimal cost. The joint sparsity in large networks is used to improve the compressive sensing reconstruction in large networks. Further, a novel compressive sensing method for binary signal is proposed. Unlike general compressive sensing solution based on optimization process, a simple, reliable and quick compressive sensing method for binary signal using bipartite graph, edge recovery and check-sum method is developed. The proposed models and methods have been verified, proved and compared with existing approaches through numerical analysis and simulations.

On friday, there will be a talk at ParisTech on CS

Information theoretic bounds and statistical physics analysis of sparse signals support recovery.

Giuseppe Caire (University of Southern California)

We consider the support recovery of a sparse signal observed through a rank-deficient linear transformation in Gaussian background noise. This problem is similar to the classical noisy compressed sensing problem, with the difference that we care only about the support estimation (i.e., the position of the non-zero signal components).

In addition, we consider the support recovery error rate, i.e., the Hamming distance between the binary vector indicating the support of the original signal and the binary vector indicating the estimated support, normalized by the signal block length. We consider a rather general class of ''sensing matrices'' satisfying a given freeness condition.

For such problem, we develop an information theoretic rate-distortion lower bound on the achievable support recovery error rate. Also, we use the replica method of statistical physics to analyze the performance of the optimal MAP estimator (not implementable in practice) and of some practical estimators, such as a thresholded linear MMSE estimator and the Lasso estimator (L1 reconstruction with L2 norm bias) widely studied in the compressed sensing literature. The results of the replica analysis match very well with the information theoretic bounds.

Joint work with Antonia Tulino, Sergio Verdu and Shlomo Shamai.

Finally, in the good town of Lyon, there is this call for a PhD studentship at CREATIS:

Reconstruction par compressive sensing en imagerie ultrasonore 3D dynamique

Recrutement en cours

Domaine et contexte scientifiques: Le "compressive sensing" (CS) est une méthode récente qui permet d'envisager une nouvelle façon d'échantillonner les signaux ou les images. En exploitant le caractère parcimonieux que présentent la plupart des données physiques, elle permet en effet de reconstruire les données acquises avec des fréquences d'échantillonnage bien inférieures à la limite classique de Shannon. En imagerie ultrasonore 3D les acquisitions font appel à des sondes comportant une matrice de capteurs. Pour des raisons d'encombrement physique, de connexion et de pilotage, seule une faible fraction de ces capteurs peut être activée. Dans ce contexte, le compressive sensing présente donc un intérêt majeur pour aller vers une amélioration considérable des résolutions spatiales et temporelles de ces acquisitions 3D.

Objectif: Malgré son intérêt et à la différence d'autres modalités (en particulier l'IRM), l'application du compressive sensing en l'imagerie ultrasonore reste actuellement quasiment inexplorée: ceci est lié aux spécificités des signaux ultrasonores RF (nature oscillatoire et spatialement variante), qui rendent une telle application très complexe. Il n'existe de fait actuellement que quelques équipes (dont CREATIS fut l'une des premières) identifiées au niveau international travaillant sur cette thématique. Ce problème représente un verrou et sa levée une véritable rupture conceptuelle de la formation des images ultrasonores. Dans ce cadre, l'objectif de ce travail est donc de développer les éléments méthodologiques nécessaires à la mise en œuvre du compressive sensing en imagerie ultrasonore 3D dynamique (séquences d’images volumiques) et d'aboutir à une démonstration de faisabilité sur des données expérimentales.

Méthodologie et programme de recherche: La première phase de ce travail consistera à développer un dictionnaire d'atomes permettant une représentation parcimonieuse (ou suffisamment compressible) des signaux ultrasonores 3D. Deux voies seront explorées: d'une part l'exploitation de bases orthogonales adaptées aux caractéristiques oscillatoires et spatialement variantes des signaux ultrasonores, telles que les wave atoms; d'autre part l'extraction par apprentissage sur les données d'un dictionnaire et l'évaluation de sa généralité/spécificité. Dans une 2ème phase, on s’intéressera à l’exploitation de l’information temporelle en envisageant l’application du compressed sensing sur la différence incrémentale entre les images successives d’une séquence. On explorera en particulier dans quelle mesure une telle approche permet d’augmenter le caractère parcimonieux du flot de données et d’accroître ainsi la précision et la rapidité de l’algorithme de reconstruction Une attention particulière devra être apportée aux algorithmes de reconstruction (type OMP ou relaxation convexe) mis en œuvre: ainsi le volume de données correspondant à une acquisition implique la capacité de travailler en large dimension, tout en conservant des temps de calculs compatible avec la pratique "temps réel" usuelle en imagerie ultrasonore. La méthodologie développée sera évaluée en premier sur des données ultrasonores issues de simulations numériques. Elle sera ensuite appliquée sur des données expérimentales 3D acquises sur les échographes de recherche de la plateforme de Creatis, puis sur des données acquises in vivo acquises en collaboration avec le laboratoire Medical Image Computing Lab de l’Université de Leuven, Belgique).

Collaborations/partenariats extérieurs : L’acquisition des données in vivo sera réalisée en collaboration avec le laboratoire Medical Image Computing Lab de l’Université de Leuven, Belgique). Les conditions de cette collaboration sont déjà bien établies, puisqu’elle a déjà donné lieu à 3 séjours de doctorant à Leuven (financement MIRA et Explora’doc de la région Rhône-Alpes), 8 publications et 26 communications internationales co-signées.

Compétences développées au cours de la thèse et perspective professionnelle : Au travers de ce sujet, le doctorant développera une expérience en matière d’acquisition et de formation de l’image ultrasonore et une forte compétence sur les techniques très récentes d’acquisition compressée, qui sont liées au domaine du traitement numérique du signal et de l’image, des statistiques, et problèmes inverses. Du fait de la généralité de ce type de technique et de ses nombreux domaines d’application, il pourra à la suite de la thèse s’intégrer soit au sein d’une équipe de recherche (versant fondamental ou appliqué de la thématique), soit au sein entreprise de taille suffisamment importante pour posséder un département R&D. Cette entreprise pourra être en premier lieu liée à l’imagerie médicale, ou aux nombreux autres domaines d’application ouverts à ce type de technique.

Profil du candidat recherché (prérequis) : Master de type EEA ou mathématiques appliquées, avec idéalement une expérience en traitement et analyse de l’image/signal. Le prérequis ont les suivants : • Traitement numérique du signal et de l’image, statistiques, mathématiques appliquées • Programmation Matlab

Image Credit: NASA/JPL/Space Science Institute,  W00073360.jpg was taken on March 29, 2012 and received on Earth March 29, 2012. The camera was pointing toward RHEA at approximately 446,163 kilometers away, and the image was taken using the IR2 and CL2 filters.

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.