An issue in data analysis is that of incomplete data, for example a photograph with scratches or seismic data collected with fewer than necessary sensors. There exists a unified approach to solving this problem and that of data separation: namely, minimizing the norm of the analysis (rather than synthesis) coefficients with respect to particular frame(s).There have been a number of successful applications of this method recently. Analyzing this method using the concept of clustered sparsity leads to theoretical bounds and results, which will be presented. Furthermore, necessary conditions for the frames to lead to sufficiently good solutions will be shown, and this theoretical framework will be use to show that shearlets are able to inpaint larger gaps than wavelets. Finally, the results of numerical experiments comparing this approach to inpainting to numerous others will be presented.

The automated reconstruction of neuronal morphology is a fundamental task for investigating several problems associated with the nervous system. Revealing the mechanisms of synaptic plasticity, signal transmission, network connectivity and circuit dynamics requires accurate quantitative analyses of digital three-dimensional reconstructions. Yet, while many commercial and non-commercial software packages for neuronal reconstruction are available, these packages typically provide limited quantitative information and require a significant manual intervention. Recent advances in applied harmonic analysis, especially in the area of multiscale representations, offer a variery of techniques and ideas which have the potential to dramatically impact this very active field of scientific investigation. In this paper, we apply such ideas for (i) the derivation of a multiscale directional representation from isotropic filters aimed at detecting tubular structures and (ii) the development of a multiscale quantitative measure capable of distingushing isotropic from anisotropic structures. We showcase the application of these methods for the extraction of geometric features used for the detection of somas and dendritic branches of neurons.

The novel framework of parabolic molecules provides for the first time a unifying framework for (sparse) approximation properties of directional representation systems by, in particular, including curvelets and shearlets. However, the considered common bracket is parabolic scaling, which excludes systems such as ridgelets and wavelets. In this paper, we therefore provide a generalization of this framework, which we coin α-molecules, by introducing an additional parameter α, which specifies the extent of anisotropy in the scaling. We show that, for instance, both ridgelets and wavelets are in fact α-molecules. As an application of the concept, we then analyze the sparse approximation behavior of α-molecules. Utilizing the idea of sparsity equivalence, it is possible to identify large classes of α-molecules providing the same sparse approximation behavior.

In this paper, we first briefly review the directional properties of the Dual-Tree complex wavelet transform and we investigate how the directional selectivity of the transform can be increased (i.e., to obtain more than 6 orientations per scale). To this end, we describe a new augmented Lagrangian optimization algorithm to jointly perform the 2D spectral factorization of a set of 2D directional filters, with a high numerical accuracy. We demonstrate how this approach can be used to design compactly supported shearlet frames that are tight. Finally, a number of experimental results are given to show the merits of the resulting shearlet frames.

In a recent work, it was shown that the shearlet representation provides a useful formula for the reconstruction of 3D objects from their X-ray projections. One major advantage of this approach is that it yields a near-optimal rate of convergence in estimating piecewise smooth objects from 3D X-ray projections which are corrupted by white Gaussian noise. In this work, we provide numerical demonstrations to illustrate the effectiveness of this method and its performance as compared with other X-ray data restoration algorithms.

Shift invariant spaces are common in the study of analysis, appearing, for example, as cornerstones of the theories of wavelets and sampling. The interplay of these three notions is discussed at length over R, with the one-dimensional study providing motivation for later discussions of Rn, locally compact abelian groups, and some non-abelian groups. Two fundamental tools, the so-called bracket" as well as the Zak transform(s), are described, and their deep connections to the aforementioned areas of study are made explicit.

In this paper we derive weighted and reweighted AMP algorithms for signal reconstruction from compressed sensing measurements. Weighted AMP incorporates prior support information into the AMP algorithm and iteratively solves the weighted I₁ minimization which is much faster than the usual linear programming algorithms used to solve this problem. We also introduce a reweighting scheme for regular and weighted AMP algorithms which enhances the recovery performance of both regular and weighted AMP while still maintaining the low complexity nature of AMP algorithms.

We study the exact recovery of signals from quantized frame coefficients. Here, the basis of the quantization is hard thresholding, and we present a simple algorithm for the recovery of reconstructable signals. The set of non-reconstructable signals is shown to be star-shaped and symmetric with respect to the origin. Moreover, we provide a criterion on the frame for the boundedness of this set. In this case, we also give a priori bounds.

The objective of this paper is to study the performance of fusion frames for packet encodings in the presence of erasures. These frames encode a vector in a Hilbert space in terms of its components in subspaces, which can be identified with packets of linear coefficients. We evaluate the fusion frame performance under some statistical assumption on the vector to be transmitted, when part of the packets is transmitted perfectly and another part is lost in an adversarial, deterministic manner. The performance is measured by the mean-squared Euclidean norm of the reconstruction error when averaged over the transmission of all unit vectors. Our main result is that a random selection of fusion frames performs nearly as well as previously known optimal bounds for the error, characterized by optimal packings of subspaces, which are known not to exist in all dimensions.

The recently introduced and characterized scalable frames can be considered as those frames which allow for perfect preconditioning in the sense that the frame vectors can be rescaled to yield a tight frame. In this paper we define m−scalability, a refinement of scalability based on the number of non-zero weights used in the rescaling process. We enlighten a close connection between this notion and elements from convex geometry. Another focus lies in the topology of scalable frames. In particular, we prove that the set of scalable frames with “usual” redundancy is nowhere dense in the set of frames.

In this paper we study the property of phase retrievability by redundant systems of vectors under perturbations of the frame set. Specifically we show that if a set F of m vectors in the complex Hilbert space of dimension n allows for vector reconstruction from magnitudes of its coefficients, then there is a perturbation bound ρ so that any frame set within ρ from F has the same property. In particular this proves the recent construction in¹⁵ is stable under perturbations. By the same token we reduce the critical cardinality conjectured in¹¹ to proving a stability result for non phase-retrievable frames.

We review scale-discretized wavelets on the sphere, which are directional and allow one to probe oriented structure in data defined on the sphere. Furthermore, scale-discretized wavelets allow in practice the exact synthesis of a signal from its wavelet coefficients. We present exact and efficient algorithms to compute the scale-discretized wavelet transform of band-limited signals on the sphere. These algorithms are implemented in the publicly available S2DW code. We release a new version of S2DW that is parallelized and contains additional code optimizations. Note that scale-discretized wavelets can be viewed as a directional generalization of needlets. Finally, we outline future improvements to the algorithms presented, which can be achieved by exploiting a new sampling theorem on the sphere developed recently by some of the authors.

Pressing questions in cosmology such as the nature of dark matter and dark energy can be addressed using large galaxy surveys, which measure the positions, properties and redshifts of galaxies in order to map the large-scale structure of the Universe. We review the Fourier-Laguerre transform, a novel transform in 3D spherical coordinates which is based on spherical harmonics combined with damped Laguerre polynomials and appropriate for analysing galaxy surveys. We also recall the construction of aglets, 3D wavelets obtained through a tiling of the Fourier-Laguerre space, which can be used to extract scale-dependent, spatially localised features on the ball. We exploit a sampling theorem to obtain exact Fourier-Laguerre and aglet transforms, such that band-limited signals can analysed and reconstructed at oating point accuracy on a nite number of voxels on the ball. We present a potential application of the aglet transform for nding voids in galaxy surveys and studying the large-scale structure of the Universe.

We present several 3D sparse decompositions based on wavelets on the sphere that are useful for different kind of data set such as regular 3D spherical measurements (r,θ, φ) and multichannel spherical measurements (λ, θ, φ). We show how these new decompositions can be used for astronomical data denoising and deconvolution, when the data are contaminated by Gaussian and Poisson noise.

In this paper, we present an optimal filter for the enhancement or estimation of signals on the 2-sphere corrupted by noise, when both the signal and noise are realizations of anisotropic processes on the 2-sphere. The estimation of such a signal in the spatial or spectral domain separately can be shown to be inadequate. Therefore, we develop an optimal filter in the joint spatio-spectral domain by using a framework recently presented in the literature | the spatially localized spherical harmonic transform - enabling such processing. Filtering of a signal in the spatio-spectral domain facilitates taking into account anisotropic properties of both the signal and noise processes. The proposed spatio-spectral filtering is optimal under the mean-square error criterion. The capability of the proposed filtering framework is demonstrated with by an example to estimate a signal corrupted by an anisotropic noise process.

This paper considers the construction of Reproducing Kernel Hilbert Spaces (RKHS) on the sphere as an alternative to the conventional Hilbert space using the inner product that yields the L²(S²) function space of finite energy signals. In comparison with wavelet representations, which have multi-resolution properties on L²(S²), the representations that arise from the RKHS approach, which uses different inner products, have an overall smoothness constraint, which may offer advantages and simplifications in certain contexts. The key contribution of this paper is to construct classes of closed-form kernels, such as one based on the von Mises-Fisher distribution, which permits efficient inner product computation using kernel evaluations. Three classes of RKHS are defined: isotropic kernels and non-isotropic kernels both with spherical harmonic eigenfunctions, and general anisotropic kernels.

We review the construction of three different Slepian bases on the sphere, and illustrate their theoretical behavior and practical use for solving ill-posed satellite inverse problems. The first basis is scalar, the second vectorial, and the third suitable for the vector representation of the harmonic potential fields on which we focus our analysis. When data are noisy and incompletely observed over contiguous domains covering parts of the sphere at satellite altitude, expanding the unknown solution in terms of a Slepian basis and seeking truncated expansions to achieve least-squares data fit has advantages over conventional approaches that include the ease with which the solutions can be computed, and a clear statistical understanding of the competing effects of solution bias and variance in modulating the mean squared error, as we illustrate with several new examples.

We consider the problem of reconstructing an audio signal from multiple observations, each of which is contaminated with time-varying noise. Assuming that the time-variation is different for each observation, we propose an estimation formulation that can adapt to these changes. Specifically, we postulate a parametric reconstruction and choose the parameters so that the reconstruction minimizes a cost function. The cost function is selected so that audio signals are penalized less compared to arbitrary signals with the same energy. As cost functions, we experiment with a recently proposed prior as well as mixed norms placed on the short time Fourier coefficients.

We consider the problem of estimating a group sparse vector x ∈ Rⁿ under a generalized linear measurement model. Group sparsity of x means the activity of different components of the vector occurs in groups - a feature common in estimation problems in image processing, simultaneous sparse approximation and feature selection with grouped variables. Unfortunately, many current group sparse estimation methods require that the groups are non-overlapping. This work considers problems with what we call generalized group sparsity where the activity of the different components of x are modeled as functions of a small number of boolean latent variables. We show that this model can incorporate a large class of overlapping group sparse problems including problems in sparse multivariable polynomial regression and gene expression analysis. To estimate vectors with such group sparse structures, the paper proposes to use a recently-developed hybrid generalized approximate message passing (HyGAMP) method. Approximate message passing (AMP) refers to a class of algorithms based on Gaussian and quadratic approximations of loopy belief propagation for estimation of random vectors under linear measurements. The HyGAMP method extends the AMP framework to incorporate priors on x described by graphical models of which generalized group sparsity is a special case. We show that the HyGAMP algorithm is computationally efficient, general and offers superior performance in certain synthetic data test cases.

In this paper we share our recent observations on methods for sparsity enforced orthogonal transform design. In our previous work on this problem, our target was to design transforms (sparse orthonormal transforms - SOT) that minimize the overall sparsity-distortion cost of a collection of image patches mainly for improving the performance of compression methods. In this paper we go one step further to understand why these transforms achieve better approximation and how different they are from transforms like the DCT or the Karhunen-Loeve transform (KLT). Our study lead us to mathematically validate that for a Gaussian process the KLT is the optimal transform not only in a linear approximation sense but also in a nonlinear approximation sense, the latter forming the basis for sparsity-based regularization. This means that the search for SOTs yields the KLT in Gaussian processes, but results in transforms that are distinctly different from the KLT in non-Gaussian cases by capturing useful structures within the data. Both toy examples and real compression results in various representation domains are presented in this paper to support our observations.

This paper proposes efficient algorithms for group sparse optimization with mixed l_2,1-regularization, which arises from the reconstruction of group sparse signals in compressive sensing, and the group Lasso problem in statistics and machine learning. It is known that encoding the group information in addition to sparsity can often lead to better signal recovery/feature selection. The l_2,1-regularization promotes group sparsity, but the resulting problem, due to the mixed-norm structure and possible grouping irregularity, is considered more difficult to solve than the conventional l_1-regularized problem. Our approach is based on a variable splitting strategy and the classic alternating direction method (ADM). Two algorithms are presented, one derived from the primal and the other from the dual of the l_2,1-regularized problem. The convergence of the proposed algorithms is guaranteed by the existing ADM theory. General group configurations such as overlapping groups and incomplete covers can be easily handled by our approach. Computational results show that on random problems the proposed ADM algorithms exhibit good efficiency, and strong stability and robustness.

In this paper, we introduce a LIDAR return pulse analysis framework based on the concept of finite rate of innovations (FRI). Specifically, the proposed FRI-based model allows us to characterize the temporal return pulse envelopes captured by 3rd generation LIDAR systems in a low dimensional space. Furthermore, the extracted model parameters can often be mapped to specific physical features of the scene being captured, aiding in high-level interpretation. After describing the model formulation and extraction process, we illustrate its potential utility in two specific applications: sub-spot size ranging (super-resolution) and random impulsive scene scanning. In the course of this discussion, we also relate the FRI model to compressive sensing and sparse range-map reconstruction.

We propose a stable reconstruction method for polynomial splines from compressive samples based on the maximum a posteriori (MAP) estimation. The polynomial splines are one of the most powerful tools for modeling signals in real applications. Since such signals are not band-limited, the classical sampling theorem cannot be applied to them. However, splines can be regarded as signals with finite rate of innovation and therefore be perfectly reconstructed from noiseless samples acquired at, approximately, the rate of innovation. In noisy case, the conventional approach exploits Cadzow denoising. Our approach based on the MAP estimation reconstructs the signals more stably than not only the conventional approach but also a maximum likelihood estimation. We show the effectiveness of the proposed method by applying it to compressive sampling of vehicular signals.

In this work, we show that great circles, the intersection of a plane through the origin and a sphere centered at the origin, can be perfectly recovered at their rate of innovation. Specifically, we show that 4K(8K − 7) + 7 samples are sufficient to perfectly recover K great circles, given an appropriate sampling scheme. Moreover, we argue that the number of samples can be reduced to 2K(4K − 1) while maintaining accurate results. This argument is supported by our numerical results. To improve the robustness to noise of our approach, we propose a modification that uses all the available information, instead of the critical amount. The increase in accuracy is demonstrated using numerical simulations.

In the last few years, several new methods have been developed for the sampling and the exact reconstruction of specific classes of non-bandlimited signals known as signals with finite rate of innovation (FRI). This is achieved by using adequate sampling kernels and reconstruction schemes. An important class of such kernels is the one made of functions able to reproduce exponentials. In this paper we review a new strategy for sampling these signals which is universal in that it works with any kernel. We do so by noting that meeting the exact exponential reproduction condition is too stringent a constraint, we thus allow for a controlled error in the reproduction formula in order to use the exponential reproduction idea with any kernel and develop a reconstruction method which is more robust to noise. We also present a novel method that is able to reconstruct infinite streams of Diracs, even in high noise scenarios. We sequentially process the discrete samples and output locations and amplitudes of the Diracs in real-time. In this context we also show that we can achieve a high reconstruction accuracy of 1000 Diracs for SNRs as low as 5dB.

We present a method for joint reconstruction of a set of images representing a given scene from few multi-view measurements obtained by compressed sensing. We model the correlation between measurements using global geometric transformations represented by few parameters. Then, we propose an algorithm able to jointly estimate these transformation parameters and the observed images from the available measurements. This method is also robust to occlusions appearing in the scene. The reconstruction algorithm minimizes a non-convex functional and generates a sequence of estimates converging to a critical point of this functional. Finally, we demonstrate the efficiency of the proposed method using numerical simulations.

We propose a new method to better estimate and subtract the contribution of detected compact sources to the microwave sky. These bright compact source emissions contaminate the full-sky data over a significant fraction of the sky, and should therefore be accurately removed if a high resolution and full-sky estimate of the components is sought after. However the point source spectral variability hampers accurate blind source separation, even with state-of-the-art localized source separation techniques. In this work, we rather propose to estimate the flux of the brightest compact sources using a morphological separation approach, relying on a more sophisticated model for the background than in standard approaches. Essentially, this amounts to separate point sources with known support and shape from a background assumed sparse in the spherical harmonic domain. This approach is compared to standard local χ² minimization modeling the background as a low order polynomial on WMAP realistic simulations. If in noisy situations estimating more than a few parameter does not improve flux recovery, in the first WMAP channels the proposed method leads to lower biases (typically by factors of 2) and increased robustness.

Coded apertures and energy resolving detectors may be used to improve the sampling efficiency of x-ray tomography and increase the physical diversity of x-ray phenomena measured. Coding and decompressive inference enable increased molecular specificity, reduced exposure and scan times. We outline a specific coded aperture x-ray coherent scatter imaging architecture that demonstrates the potential of such schemes. Based on this geometry, we develop a physical model using both a semi-analytic and Monte Carlo-based framework, devise an experimental realization of the system, describe a reconstruction algorithm for estimating the object from raw data, and propose a classification scheme for identifying the material composition of the object at each location

We examine compressive sensing (CS) systems where the sensing mechanism is based on convolution with a quadratic phase function. The performance of such systems is evaluated as function of the system parameters. Examples of CS application involving optical quadratic phase filters are presented, including three dimensional object reconstructions from two dimensional recorded quadratic phase filtered fields, and reconstruction of objects set behind a partially opaque media.

Distinct texture classes are often sharing several visual concepts. Texture instances from different classes are sharing regions in the feature hyperspace, which results in ill-defined classification configurations. In this work, we detect rotation-covariant visual concepts using steerable Riesz wavelets and bags of visual words. In a first step, K-means clustering is used to detect visual concepts in the hyperspace of the energies of steerable Riesz wavelets. The coordinates of the clusters are used to construct templates from linear combinations of the Riesz components that are corresponding to visual concepts. The visualization of these templates allows verifying the relevance of the concepts modeled. Then, the local orientations of each template are optimized to maximize their response, which is carried out analytically and can still be expressed as a linear combination of the initial steerable Riesz templates. The texture classes are learned in the feature space composed of the concatenation of the maximum responses of each visual concept using support vector machines. An experimental evaluation using the Outex TC 00010 test suite allowed a classification accuracy of 97.5%, which demonstrates the feasibility of the proposed approach. An optimal number K = 20 of clusters is required to model the visual concepts, which was found to be fewer than the number of classes. This shows that higher-level classes are sharing low-level visual concepts. The importance of rotation-covariant visual concept modeling is highlighted by allowing an absolute gain of more than 30% in accuracy. The visual concepts are modeling the local organization of directions at various scales, which is in accordance with the bottom{up visual information processing sequence of the primal sketch in Marr's theory on vision.

In this paper, we investigate how the CS framework can be adapted to biological video microscopy acquisition problems. We first consider a frame-by-frame linear acquisition model in the Fourier domain of the signal, and discuss the relevance of several sparsity models that can be used to drive the reconstruction of the whole video sequence. Then, we switch to a non-linear acquisition model – therefore beyond the “pure” CS framework – in which only the modulus of the Fourier transform of the signal is acquired: by exploiting sparsity properties similar to the one used in the linear acquisition case, we demonstrate the feasibility of a phase retrieval reconstruction procedure applied to video signals.

3D deconvolution in optical wide eld microscopy aims at recovering optical sections through thick objects. Acquiring data from multiple, mutually-tilted directions helps ll the missing cone of information in the optical transfer function, which normally renders the deconvolution problem particularly ill-posed. Here, we propose a fast-converging iterative deconvolution method for multi-angle deconvolution microscopy. Specically, we formulate the imaging problem using a lter-bank structure, and present a multi-channel variation of a thresholded Landweber deconvolution algorithm with wavelet-sparsity regularization. Decomposition of the minimization problem into subband-dependent terms ensures fast convergence. We demonstrate the applicability of the algorithm via simulation results.

Active Range Imaging (ARI) has recently sparked an enthusiastic interest due to the numerous applications that can benefit from the high quality depth maps that ARI systems offer. One of the most successful ARI techniques employs Time-of-Flight (ToF) cameras which emit and subsequently record laser pulses in order to estimate the distance between the camera and objects in a scene. A limitation of this type of ARI is the requirement for a large number of frames that have to be captured in order to generate high resolution depth maps. In this work, we introduce Compressed Gated Range Sensing (CGRS), a novel approach for ToF-based ARI that utilizes the recently proposed framework of Compressed Sensing (CS) to dramatically reduce the number of necessary frames. The CGRS technique employs a random gating function along with state-of-the-art reconstruction in order to estimate the timing of a returning laser pulse and infer the depth map. To validate our method, software simulations were carried out using a realistic system model. Simulated results suggest that low error reconstruction of a depth map is possible using approximately 20% of the frames that traditional ToF cameras require, while 30% sampling rates can achieve very high fidelity reconstruction.

We demonstrate that the phase of randomized complex-valued projections of real-valued signals preserves information about the angle, i.e., the correlation, between those signals. This information can be exploited to design quantized angle-preserving embeddings, which represent such correlations using a nite bit-rate. The proposed embeddings generalize known results on binary embeddings and 1-bit compressive sensing and allow us to explore the trade-o between number of measurements and number of bits per measurement, given the bit rate. The freedom provided by this trade-off, which has also been observed in quantized Johnson-Lindenstrauss embeddings, can improve performance at reduced rate in a number of applications.

In this paper, we introduce a method to stabilize the variance of decimated transforms using one or two variance stabilizing transforms (VST). These VSTs are applied to the 3-D Meyer wavelet pyramidal transform which is the core of the first generation 3D curvelets. This allows us to extend these 3-D curvelets to handle Poisson noise, that we apply to the denoising of a simulated cosmological volume.

The LOFAR Radio Telescope is a radio interferometer with multiple antennas placed throughout Europe. A radio interferometer samples the image of the sky in the Fourier domain; recovering the image from these samples is an inverse problem. In radio astronomy the CLEAN method has been used for many years to find a solution. Recent papers have established a link between radio interferometry and compressed sensing, which supports sparse recovery methods to reconstruct an image from interferometric data. The goal of this paper is to study sparse recovery methods on LOFAR data by comparing the accuracy of CLEAN and compressed sensing when applied to simulated LOFAR observations.

Conventional depth imagers using time-of-flight methods collect hundreds to thousands of detected photons per pixel to form high-quality depth images of a scene. Through spatio-temporal regularization achieved with maximum a posteriori probability estimation under a scene prior and an inhomogeneous Poisson process likelihood function, we form depth images with dramatically higher photon efficiency even as low as one detected photon per pixel. Simulations demonstrate the combination of high accuracy and high photon efficiency of our method, compared to the traditional maximum likelihood estimate of the depth image and other popular denoising algorithms.

In this paper we present a method called local hub screening for detecting hubs in a sparse correlation or partial correlation network over p nodes. The proposed method is related to hub screening¹ where a Poisson-type limit is used to specify p-values on the number of spurious hub nodes found in the network. In this paper we also establish Poisson limits. However, instead of being on the global number of hub nodes found, here the Poisson limit applies to the node degree found at an individual node. This allows us to de ne asymptotic p-values that are local to each node. We will see that the convergence rates for proposed local hub screening method are at least a factor of p faster than those of global correlation and hub screening.

Recent work has begun to develop a theory for the representation, processing, and approximation of signals supported on graphs. For signals supported on graphs, the eigenvectors of the graph Laplacian play a role analogous to the Fourier transform. We discuss recent results which develop uncertainty principles for signals supported on graphs, focusing on the role of the graph topology. We then conduct a series of experiments to explore how characteristics of the graph topology influence the extent to which a signal can have low graph spread and spectral spread, as quantified through the uncertainty curve. Through experiments with small-world random graphs, we find a correlation between the clustering coefficient of the graph, the second largest eigenvalue, and the shape of the uncertainty curve.

A number of new localized, multiscale transforms have recently been introduced to analyze data residing on weighted graphs. In signal processing tasks such as regularization and compression, much of the power of classical wavelets on the real line is derived from their theoretically and empirically proven ability to sparsely represent piecewise-smooth signals, which appear to be locally polynomial at sufficiently small scales. As of yet in the graph setting, there is little mathematical theory relating the sparsity of localized, multiscale transform coefficients to the structures of graph signals and their underlying graphs. In this paper, we begin to explore notions of global and local regularity of graph signals, and analyze the decay of spectral graph wavelet coefficients for regular graph signals.

Epidemic models on networks have long been studied by biologists and social sciences to determine the steady state levels of an infection on a network. Recently, however, several authors have begun considering the more difficult problem of estimating the source of an infection given information about its behavior some time after the initial infection. In this paper, we describe a technique to estimate the source of an infection on a general graph based on observations from a small set of observers during a fixed time window at some unknown time after the initial infection. We describe an alternate representation for the susceptible-infected (SI) infection model based on geodesic distances on a randomly-weighted version of the graph; this representation allows us to exploit fast algorithms to compute geodesic distances to estimate the marginal distributions for each observer and compute a pseudo-likelihood function that is maximized to find the source.

In many areas of imaging science, it is difficult to measure the phase of linear measurements. As such, one often wishes to reconstruct a signal from intensity measurements, that is, perform phase retrieval. In several applications the signal in question is believed to be sparse. In this paper, we use ideas from the recently developed polarization method for phase retrieval and provide an algorithm that is guaranteed to recover a sparse signal from a number of phaseless linear measurements that scales linearly with the sparsity of the signal (up to logarithmic factors). This is particularly remarkable since it is known that a certain popular class of convex methods is not able to perform recovery unless the number of measurements scales with the square of the sparsity of the signal. This is a shorter version of a more complete publication that will appear elsewhere.¹

In recent years, sparsity and compressive sensing have attracted significant attention in parameter estimation tasks, including frequency estimation, delay estimation, and localization. Parametric dictionaries collect observations for a sampling of the parameter space and can yield sparse representations for the signals of interest when the sampling is sufficiently dense. While this dense sampling can lead to high coherence in the dictionary, it is possible to leverage structured sparsity models to prevent highly coherent dictionary elements from appearing simultaneously in a signal representation, alleviating these coherence issues. However, the resulting approaches depend heavily on a careful setting of the maximum allowable coherence; furthermore, their guarantees apply to the coefficient vector recovery and do not translate in general to the parameter estimation task. We propose a new algorithm based on optimal sparse approximation measured by earth mover's distance (EMD). We show that EMD provides a better-suited metric for the performance of parametric dictionary-based parameter estimation. We leverage K-median clustering algorithms to solve the EMD-optimal sparse approximation problem, and show that the resulting compressive parameter estimation algorithms provide satisfactory performance without requiring control of dictionary coherence.

An equiangular tight frame (ETF) is an M x N matrix which has orthogonal equal norm rows, equal norm columns, and the inner products of all pairs of columns have the same modulus. In this paper we study ETFs in which all of the entries are unimodular, and in particular pth roots of unity. A new construction of unimodular ETFs based on resolvable Steiner systems is presented. This construction gives many new examples of unimodular ETFs. In particular, an new infinite class of ETFs with entries in f1;-1g is presented.

Analysis on locally compact abelian groups and local fields has applications in a variety of different fields. Traditional Fourier analysis is based on the characters of Rⁿ, Tⁿ, and Zⁿ. There is a growing body of literature using functions on ρ-adic groups to model quantum phenomena, and ρ-adic wavelets diagonalize certain important pseudo-differential operators. Fourier analysis on local fields comes up in class field theory and in the study of particular zeta functions. This paper will present known results in the field and future directions of research.

We provide a framework of fast iterative algorithms based on null space tuning, thresholding, and feedbacks for signal recovery in sparse representation and compressed sensing. Convergence results are provided. Numerical studies about the effectiveness and the speed of the algorithms are also presented. The algorithms are seen as particularly effective for large scale problems.

Mapping images to a high-dimensional feature space, either by considering patches of images or other features, has lead to state-of-art results in signal processing tasks such as image denoising and imprinting, and in various machine learning and computer vision tasks on images. Understanding the geometry of the embedding of images into high-dimensional feature space is a challenging problem. Finding efficient representations and learning dictionaries for such embeddings is also problematic, often leading to expensive optimization algorithms. Many such algorithms scale poorly with the dimension of the feature space, for example with the size of patches of images if these are chosen as features. This is in contrast with the crucial needs of using a multi-scale approach in the analysis of images, as details at multiple scales are crucial in image understanding, as well as in many signal processing tasks. Here we exploit a recent dictionary learning algorithm based on Geometric Wavelets, and we extend it to perform multi-scale dictionary learning on image patches, with efficient algorithms for both the learning of the dictionary, and the computation of coefficients onto that dictionary. We also discuss how invariances in images may be introduced in the dictionary learning phase, by generalizing the construction of such dictionaries to non-Euclidean spaces.

Frames, which in finite dimensions are spanning sets of vectors, generalize the notion of bases and provide a useful tool for modeling the measurement (or sampling) process in several modern signal processing applications. In the digital era, the measurement process is typically followed by a quantization, or digitization step that allows for storage, transmission, and processing using digital devices. One family of quantization methods, popular for its robustness to errors caused by circuit imperfections and for its ability to act on the measurements progressively, is Sigma-Delta quantization. In the finite frame setting, Sigma-Delta quantization, unlike scalar quantization, has recently been shown to exploit the redundancy in the measurement process leading to a more efficient rate distortion performance. Nevertheless, on its own, it is not known whether Sigma-Delta quantization can provide optimal rate-distortion performance. In this note, we show that a simple post-processing step consisting of a discrete, random Johnson-Lindenstrauss embedding of the resulting bit-stream yields near-optimal rate distortion performance, with high probability. In other words, it near optimally compresses the resulting bitstream. Our result holds for a wide variety of frames, including smooth frames and random frames.

The mathematical study of phase retrieval was started in 2006 in a landmark paper of Balan, Casazza and Edidin. This quickly became a heavily studied topic with implications for many areas of research in both applied mathematics and engineering. Recently there have been developments in a new area of study pertaining to phase retrieval given by projections. We give an extensive overview of the papers regarding projection phase retrieval.

We propose a compressed sensing type of reconstruction method that can handle large amounts of inter-frame motion by including diffeomorphic model-based registration steps within the iterative reconstruction. The method is useful for speeding up imaging of moving structures. It is also suitable for application to a newly proposed type of myocardial perfusion imaging that does not use ECG gating. Such an acquisition is a simpler alternative to conventional ECG gated acquisitions but requires severe undersampling of k-space data and more sophisticated reconstruction methods. The new methods and preliminary results are presented.

In this paper, a novel patch-based signal processing algorithm for motion estimated/compensated compressed sensing dynamic MR imaging is proposed. More specifically, we impose a non-convex patch-based low-rank penalty that exploits self-similarities within the images. This penalty is shown to favor capturing geometric features such as edges rather than reconstructing the background noises. To solve the resulting non-convex optimization problem, we propose a globally convergent concave-convex procedure (CCCP) using convex conju- gate, which has closed form solution at each sub-iteration. Experimental results demonstrate that the proposed algorithm outperforms the existing ones.

L+S matrix decomposition finds the low-rank (L) and sparse (S) components of a matrix M by solving the following convex optimization problem: min‖L‖_*L+S matrix decomposition finds the low-rank (L) and sparse (S) components of a matrix M by solving the following convex optimization problem: ‖L ‖_* + λ‖S‖₁, subject to M=L+S, where ‖L‖_* is the nuclear-norm or sum of singular values of L and ‖S‖₁ is the 1₁-norm| or sum of absolute values of S. This work presents the application of the L+S decomposition to reconstruct incoherently undersampled dynamic MRI data as a superposition of a slowly or coherently changing background and sparse innovations. Feasibility of the method was tested in several accelerated dynamic MRI experiments including cardiac perfusion, time-resolved peripheral angiography and liver perfusion using Cartesian and radial sampling. The high acceleration and background separation enabled by L+S reconstruction promises to enhance spatial and temporal resolution and to enable background suppression without the need of subtraction or modeling.

We propose an acquisition and reconstruction technique for accelerated free-breathing cardiac MRI acquisitions. For the acquisition, a random undersampling pattern, including a fully-sampled center of k-space, is generated prospectively. The k-space lines specified by this undersampling pattern is acquired with respiratory navigating (NAV), where only the central k-space lines are acquired within the prespecified gating window. For the outer k-space lines, if the NAV signal corresponding to a k-space segment is outside the gating window, the segment is rejected, but not re-acquired. The reconstruction approach jointly estimates the underlying image using a compressed-sensing based approach, and the translational motion parameters for each segment for the outer k-space segments acquired outside the gating window. The feasibility of the approach is demonstrated in healthy adult subjects using whole-heart coronary MRI with a 3-fold accelerated random undersampling pattern. The proposed acquisition and reconstruction technique is compared to parallel imaging with uniform undersampling with 3-fold undersampling. The two techniques exhibit similar image quality with a shorter acquisition time for the proposed approach (4:25±0:31 minutes versus 6:52±0:19).

In many clinical MRI applications, not one but a series of images is acquired. Techniques that promote intra- and inter-image sparsity have recently emerged as powerful strategies for accelerating MRI applications; however, sparsity alone cannot always describe the complex relationships that exist between images in these series. In this paper, we will discuss the modeling of higher-dimensional MRI signals as matrices and tensors, and why promoting these signals to be low-rank (and, specifically, locally low-rank) can effectively identify and exploit these complex relationships. Example applications including training-free dynamic and calibrationless parallel MRI will be demonstrated.

We propose a novel sparse dictionary learning frame work to recover dynamic images from under-sampled measurements. Unlike the recent low rank schemes, the proposed scheme models the dynamic signal as a sparse linear combination of temporal basis functions chosen from a large dictionary. Both the basis functions and the sparse coefficients are estimated from the undersampled data. We show that this representation is much more compact compared to the low rank models. We also develop an efficient majorize-minimize algorithm to estimate the sparse model coefficients and the dictionary directly from the measured data. We compare the proposed scheme against low rank models and compressed sensing, and demonstrate improved reconstructions in the context of myocardial perfusion imaging in the presence of motion.

We propose a novel algorithm to adaptively correct head motion during functional magnetic resonance imaging scans. Our method combines a Kalman-filter-like motion tracker and a registration cost function based on a sparse residual image model. Using simulated data, we compare a time series correlation analysis of our prospectively corrected reconstruction against the same analysis using post-scan motion correction provided by standard software. Our experiments demonstrate our prospective correction method is capable of mitigating motion effects and improving the sensitivity and specificity of the correlation analysis, without relying on costly external tracking hardware or separate navigational data that would take extra time to acquire during each time frame.

We present an application of sparse regularization of ill-posed linear inverse problems to the reconstruction of the 3D distribution of dark matter in the Universe. By its very nature dark matter cannot be directly observed. Nevertheless, it can be studied through its gravitational effects can it be studied. In particular, the presence of dark matter induces small deformations to the shapes of background galaxies which is known as weak gravitational lensing. However, reconstructing the 3D distribution of dark matter from tomographic lensing measurements amounts to solving an ill-posed linear inverse problem. Considering that the 3D dark matter density is sparse in an appropriate wavelet based 3D dictionary, we propose an iterative thresholding algorithm to solve a penalized least-squares problem. We present our results on simulated dark matter halos and compare them to state of the art linear reconstruction techniques. We show that thanks to our 3D sparsity constraint the quality of the reconstructed maps can be greatly improved.

A method based on the curvelet transform is introduced for estimating from two-dimensional images the orientation distribution of small anisotropic particles. Orientation of fibers in paper is considered as a particular application of the method. Theoretical aspects of the suitability of this method are discussed and its efficiency is demonstrated with simulated and real images of fibrous systems. Comparison is made with two traditionally used methods of orientation analysis, and the new curvelet-based method is shown to perform clearly better than these traditional methods.

Optical Coherence Tomography (OCT) suffers from speckle noise which causes erroneous interpretation. OCT denoising methods may be studied in "raw image domain" and "sparse representation". Comparison of mentioned denoising strategies in magnitude domain shows that wavelet-thresholding methods had the highest ability, among which wavelets with shift invariant property yielded better results. We chose dictionary learning to improve the performance of available wavelet-thresholding by tailoring adjusted dictionaries instead of using pre-defined bases. Furthermore, in order to take advantage of shift invariant wavelets, we introduce a new scheme in dictionary learning which starts from a dual tree complex wavelet. we investigate the performance of different speckle reduction methods: 2D Conventional Dictionary Learning (2D CDL), Real part of 2D Dictionary Learning with start dictionary of dual-tree Complex Wavelet Transform (2D RCWDL) and Imaginary part of 2D Dictionary Learning with start dictionary of dual-tree Complex Wavelet Transform (2D ICWDL). It can be seen that the performance of the proposed method in 2D R/I CWDL are considerably better than other methods in CNR.

We introduce new 5-band dyadic sibling frames with dense time-frequency grid. Given a lowpass filter satisfying certain conditions, the remaining filters are obtained using spectral factorization. The analysis and synthesis filterbanks share the same lowpass and bandpass filters but have different and oversampled highpass filters. This leads to wavelets approximating shift-invariance. The filters are FIR, have linear phase, and the resulting wavelets have vanishing moments. The filters are designed using spectral factorization method. The proposed method leads to smooth limit functions with higher approximation order, and computationally stable filterbanks.