We provide a characterization of sparse solutions of variational inverse problems with finite dimensional data. We prove the existence of a solution that is represented as a finite combination of the extremal points of the ball of the regularizer. This finding provides a natural notion of sparsity for abstract variational inverse problems. We consider the TV seminorm and the Radon norm of a scalar differential operator as regularizers. In the first case we provide a justification of the so-called staircase effect in imaging and in the second one we obtain a result of Unser, Fageot and Ward under weaker hypotheses.

We study the problem of compressed sensing off the grid in the multivariate and general operator setting. Existing results establish recovery (for Fourier measurements) under a minimum separation condition and a random signs condition on the spike amplitudes. We introduce the Fisher metric as a natural way of encoding the separation distance. This allows for the first time the study of non-translation invariant operators, such as sampling of the Laplace transform. Our main theorem establishes stable recovery of a sparse measure, without the random signs condition, when the number of random measurements scales linearly with sparsity up to log factor.

Cardinality and rank functions are ideal ways of regularizing underdetermined linear systems, but optimization is made difficult since both these penalties are nonconvex and discontinuous. The most common remedy is to instead use the l1-

and nuclear-norms, but they suffer from a shrinking bias that degrades the solution

quality in the presence of noise.

Nonconvex methods based on the quadratic envelope have recently been shown to be unbiased; the global minimizer is the “oracle solution”. We develop a framework in which the two alternatives are extreme points, so the "degree of convexity" can be chosen according to the problem.

The unsupervised alignment (or registration) of point clouds in low-dimensional representations is a fundamental problem at the heart of transfer learning. In particular, we consider the problem of aligning dataset lying in a union of subspaces and apply tools from optimal transport to tackle it. We propose a novel block optimal transport framework that incorporates cluster-based structure, as a way to add robustness against poor local minima. We demonstrate superior empirical results over the baseline Procrustes method and also provide theoretical insights on dataset conditions required for the alignability of such cluster-based methods.

We define new convex distances corresponding to optimal transport of signed measures on the circle, expressed in terms of a finite number of their Fourier coefficients. This makes it possible to deal with measures computationally, without the need to discretize them on a grid of predefined locations.

The sparse spike estimation problem consists in recovering off-the-grid impulsive sources from under-determined linear measurements. Information theoretic results ensure that the minimization of a non-convex functional is able to recover the spikes for adequately chosen measurements (deterministic or random). We study the shape of the global minimum of this non-convex functional: we give an explicit basin of attraction of the global minimum that shows that the problem becomes easier as the number of measurements grows. This has consequences for methods involving descent algorithms and gives insights for potential improvements of such methods, as a potential alternative to convex methods.

Given the popularity of machine learning and largescale data analysis, understanding the convergence properties of the optimization algorithms that constitute the workhorse in these fields is of fundamental theoretical importance. However, existing proofs of convergence consist mostly of ad-hoc arguments and case-by-case analysis. In this paper, we introduce a novel optimization framework for bounding the convergence rates of various important optimization algorithms by means of sum-of-squares certificates. Our approach allows us to recover known convergence bounds for three widely-used first-order algorithms in a unified manner and puts forward a promising framework for unifying convergence analyses of optimization algorithms.

We study an iterative discretization algorithm for solving optimization problems regularized by the total variation norm. Its design relies on ideas from the Frank-Wolfe algorithm, as well as from semi-infinite programming. For smooth regularity terms, we prove an eventual linear convergence rate guarantee.

The study of optimally sparse representations of signal classes has provided a strong theoretical foundation which enables informed choices in practice. Optimal representation systems (e.g. wavelet frames for piecewise smooth functions, curvelet/shearlet frames for cartoon-like functions) have been established in a variety of relevant cases. We develop a notion of 'sparsity w.r.t. ReLU networks', which leads to the intriguing conclusion that any function class is (asymptotically) at least as sparse w.r.t. ReLU network as it is in most conventional representation system (based on translation, dilation, and modulation of some generator functions).

In this talk, we extend recent advances in approximation theory of deep ReLU neural networks in a direction which is most relevant for applications in the numerical analysis of partial differential equations. We analyze to what extent deep ReLU neural networks can efficiently approximate Sobolev regular functions if the approximation error is measured with respect to weaker Sobolev norms. A trade–off between the regularity used in the approximation norm and the complexity of the neural network can be observed in upper and lower complexity bounds.

Variational autoencoders (VAE) represent a popular form of deep generative model that can be stochastically fit to samples from a random process using an information-theoretic variational bound on the underlying distribution. While quite effective in numerous application domains, important aspects of the VAE objective are obscured by non-convexity and intractable integrals. In this regard, we attempt to better quantify VAE properties by analyzing a representative special case. In doing so, we demonstrate that the VAE can be viewed as the natural evolution of robust PCA models, capable of learning nonlinear manifolds of unknown dimension obscured by gross corruptions.

In this work, we study the denoising of piecewise smooth graph signals that exhibit inhomogeneous levels of smoothness over a graph. We extend the graph trend filtering framework to a family of non-convex regularizers that exhibit superior recovery performance over existing convex ones. We present theoretical results in the form of asymptotic error rates for both generic and specialized graph models. We further present an ADMM-based algorithm to solve the proposed optimization problem and analyze its convergence. Numerical performance of the proposed framework with non-convex regularizers on both synthetic and real-world data for denoising, support recovery, and semi-supervised classification.

We propose an algorithm for dynamic filtering of time-varying sparse signals based on the sparse Bayesian learning (SBL) framework. The key idea underlying the algorithm is the incorporation of a signal prediction generated from a dynamics model and estimates of previous time steps into the hyperpriors of the SBL probability model. We interpret the effect of this change to the probability model from several perspectives. Numerical simulations demonstrate that the proposed method converges faster and to more accurate solutions than standard SBL and other dynamic filtering algorithms.

In this work, we present recent results concerning decompositions of tensors and ensembles of matrices in sum of terms that are not necessarily rank-1.

We formulate mathematically the concept of irreducibility, which is the enabling factor that allows these low-rank terms to exist as ``blocks'' without being further factorized into terms of smaller rank. We first demonstrate these results on tensors. Next, we generalize our results to a coupled factorization of several matrices that cannot be written as a single tensor. This coupled factorization is inspired by data fusion, and generalizes independent component analysis in several directions.

Deep learning has emerged as a tool in inverse problems with potential to change the field. However, it has been shown numerically, through instability tests, that deep learning methods for inverse problems typically become unstable. Tiny perturbations in the sampling and image domain cause severe artefacts in the reconstruction.

Moreover, false positives and false negatives may occur. Important details may be washed out and unwanted details may be added to the reconstruction. However, this phenomenon is not yet explained theoretically. We provide a mathematical explanation for the instability phenomenon and demonstrate how standard training in deep learning encourages these instabilities.

In this paper, we propose a novel linear prediction frame- work for accelerating first-order methods. We first discuss the trajectory of the sequence generated by first-order methods, showing that eventually the trajectory obeys certain low-dimensional regularity. Then building on top of such a property, we design a trajectory following linear prediction scheme for accelerating first-order methods. Numerical experiments on problems arising from inverse problems and image processing demon- strate the state-of-the-art performance of the proposed algorithm.

Suppose that we wish to estimate a user's preferences from comparisons between pairs of items (such as in a recommender system), where both the user and items are embedded in a low-dimensional space with distances that reflect user and item similarities. Since such observations can be extremely costly and noisy, we aim to actively choose pairs that are most informative given the results of previous comparisons. We provide new theoretical insights into greedy information maximization and develop two novel strategies that provably approximate information maximization. We use simulated responses from a real-world dataset to validate our strategies over state-of-the-art methods.

This work helps people using proximal methods for CS-acquired MR image analysis reconstruction.

This problem can be framed as an ill-posed inverse problem and therefore solved by algorithms like FISTA or POGM. We tried to update the benchmark done by Fessler in 2019 which didn't feature the newest FISTA enhancements. We worked with simulated non cartesian data. We show that these enhancements allow FISTA to become competitive against POGM. We also confirm that these enhancements improve the performance of the vanilla FISTA.

There is clear empirical evidence that the use of redundant dictionaries instead of orthogonal bases can significantly improve the recovery results in compressed sensing.

The theoretical understanding of this phenomenon is however still partial.

The objective of this work is to better understand the so-called synthesis formulation in the framework of random Gaussian measurements.

We derive new sharp guarantees for robust recovery of coefficient representations and of signals using the machinery of conic Gaussian widths.

In the compressive learning framework, one harshly compresses a whole training dataset into a single vector of generalized random moments, the sketch, from which a learning task can subsequently be performed. We prove that this loss of information can be leveraged to design a differentially private mechanism, and study empirically the privacy-utility trade-off for the k-means clustering problem.

COmpressive PhasE Retrieval (COPER), a novel compression-based phase

retrieval recovery method, is proposed and its recovery performance is

characterized. COPER employs a compression code designed for a class

of structured signals to recover them from their undersampled

phaseless measurements. Using compression codes that are information

theoretically optimal, COPER is shown to recover the signal from a

number of measurements that matches the corresponding information

theoretic lower bounds. Furthermore, to approximate the solution of

COPER, an efficient polynomial-time method based on projective

gradient descent is proposed and its convergence performance is

analyzed.

In this contribution, we introduce a multispectral and hyperspectral

image fusion method in an astrophysical observation context. We

define an observation forward model and solve a approximate regularized

inverse problem in the Fourier domain by a conjugate gradient algorithm.

The fusion model is evaluated on simulated observations of the Orion

Bar by the NIRCam imager and the NIRSpec spectrometer, embedded

on the James Webb Space Telescope.

Traditional inverse problem solvers minimize a cost function consisting of a data-fit term and a regularizer which promotes desirable properties. Recent advances have attempted to learn a regularizer from training data to outperform more traditional regularizers. We present an end-to-end, data-driven method, solving the linear inverse problem directly with a data-driven nonlinear regularizer via a truncated Neumann series. This Neumann network architecture outperforms traditional inverse problem methods, model-free deep learning approaches, and state-of-the-art unrolled iterative methods on standard datasets. When data lies in a union of subspaces, we prove there exists a Neumann network that well-approximates the optimal oracle estimator.

We propose a new formulation for the blind source separation problem for convolutive mixtures. We first exploit the link between the IVA and the SCA through the structured sparsity and then propose a new framework combining the convolutive narrowband approximation and the Windowed-Group-Lasso. Being able to avoid the permutation alignment and to take advantage of the cross-band information during the separation, the proposed approach outperforms the existing methods through numerical evaluations.

An important task in mathematics of information is the reconstruction of signals and images from Fourier coefficients. However, due to the binary nature of Walsh functions, an equally important task is the recovery from Walsh coefficients. This has to be done from a small number of measurements to be efficient, however, the stable and accurate recovery needs to be secured. We analyse the structure and the number of necessary samples to recover signals from binary measurements through sparse regularisation techniques. We show how the number of samples has to scale in terms of the local sparsities for the non-linear reconstruction.

We consider the recovery of low-rank matrices via a convex nuclear-norm minimization problem and present two null space properties (NSP) which characterize the uniform recovery for the case of block-diagonal matrices and block-diagonal positive semidefinite matrices. Moreover, we show that the NSP for block-diagonal positive semidefinite matrices is weaker than the NSP for block-diagonal matrices. As a special case, we obtain a similar NSP for block-sparse and nonnegative vectors, which is again weaker than the known NSP for block-sparse vectors.

In this paper we study the orthogonal low rank approximation

problem of tensors in the general setting in the sense that more than

one matrix factor is required to be mutually orthonormal, which includes

the completely orthogonal low rank approximation and semi-orthogonal

low rank approximation as two special cases. To deal with this question we present

an SVD-based algorithm. Our SVD-based algorithm updates two vectors

simultaneously and maintains the required orthogonality conditions by

means of the polar decomposition. The convergence behavior of our

algorithm is analyzed for both objective function and iterates themselves

and is illustrated by numerical experiments.

We consider image denoising via convolutional sparse coding with weighted \ell-1 penalization, and investigate the rationale behind the weighting scheme based on the reciprocal correlation between the dictionary and the image. We show that this weighting scheme, which has recently been proposed for convolutional sparse coding, yields, in case of orthonormal dictionaries, weights that are very close to the oracle weights in WaveShrink, i.e. the MSE-optimal soft thresholds. Furthermore, our empirical analysis shows that in the convolutional case, both weighting schemes achieve comparable denoising quality, providing a substantial improvement over the standard uniform weights.

In this short note we provide new theoretical analysis of a tractable recovery algorithm for one-bit quantized compressed sensing which is based on minimizing averages of Rectified Linear Units (ReLU) forming a convex relaxation of the Hamming distance. We provide recovery guarantees, which match theoretical state-of-the-art results, as well as comparison to existing methods in numerical simulations.

In this paper, we propose a generative model neural network approach for reconstructing the ground truth signals under sparse outliers. We propose two algorithms for solved the generative-model-based $\ell_1$ minimization for signal recovery. We establish the recovery guarantees and give an upper bound on the number of outliers allowed for recovery. Our results are applicable to both the linear and the nonlinear generators. We conduct extensive experiments using commonly used generative models and the experimental results show that the signals can be successfully reconstructed under outliers using our approaches. Our approach outperforms the traditional Lasso and $\ell_2$ minimization approach.

Electron microscopy has shown to be a powerful tool to analyze chemical composition of samples. However, acquiring a high quality image is hard due to radiation damages which limit the signal-to-noise ratio. One solution, considered in this work, consists in spatially partially

acquiring the multi-band image and reconstructing it afterwards. We propose a reconstruction algorithm, referred to as Fourier sparsity in 3D (FS3D), based on a regularization specifically tailored for atomically resolved images. Experiments show that the proposed FS3D method leads to state-of-the-art results with a significantly lighter computational cost.

In this work we will contribute to the theoretical analysis of one specific dictionary learning algorithm - the Iterative Thresholding and K-residual Means (ITKrM) algorithm. In particular, we extended existing recovery results to a more realistic signal model, allowing to not know the exact sparsity of our data and accordingly decreasing the sensitivity to the sparsity parameter.

The literature on sparse precision matrix estimation is rapidly growing and received significant attention from the research community. Many strong methods are valid only for Gaussian variables. In practice, data may deviate from normality in various ways, outliers and heavy tails frequently occur that can severely degrade the Gaussian models performance. For this purpose, we propose a penalized version of EM-algorithm for distributions that can be seen as Gaussian Scale Mixtures. Using the proposition we state in our work we show that the proposed penalized algorithm for precision matrix reduces simply to solving at each iteration a glasso optimization problem.

We present a variational expectation-maximization (VEM) algorithm to estimate a finite mixture of Student-t distributions from noisy data and denoise that same data. As an illustration, we apply the method to single-image patch-based image denoising.

We study 1D continuous-domain inverse problems for multicomponent signals. The prior assumption on these signals is that each component is sparse in a different dictionary specified by a regularization operators. We introduce a hybrid regularization functional matched to such signals, and prove that corresponding continuous-domain inverse problems have hybrid spline solutions, i.e. they are sums of splines matched to the regularization operators. We then propose a B-spline-based exact discretization method to solve such problems algorithmically.

Although convex losses (e.g., L1-norm for sparsity or nuclear norm for rank) are popular toolbox staples, they do not account for underlying geometry in the support when comparing signals. The optimal transport (OT) distance is a powerful mathematical framework that compares signals by measuring the "effort" required to "push" mass between their configurations. We propose fast numerical approaches that overcome the OT's notorious computational complexity that (i) have comparable time-complexity as entropic-regularized counterparts but are free from approximation-artifacts, (ii) extend variational OT problems to the space of Euclidean signals, and (iii) can easily be extended to recent unbalanced OT formulations.

Magnetic Resonance Imaging (MRI) is considered today the golden-standard modality for soft tissues. The long acquisition times, however, make it more prone to motion artifacts as well as contribute to the relative high costs of this examination. in this work, we propose to learn accelerated MR acquisition schemes (in the form of Cartesian trajectories) jointly with the image reconstruction operator. To this end, we propose an algorithm for training the combined acquisition-reconstruction pipeline end-to-end in a differentiable way. We demonstrate the significance of using the learned Cartesian trajectories at different speed up rates.

In this work we aim at efficiently solving a model-based maximum-a-posterior (MAP) image reconstruction with application to low-dose transmission X-ray Computed tomography. We propose to solve the regularized optimization problem by a randomized second order method called Newton iterative Hessian sketching for the Poisson likelihood function and to design a regularization term for the MAP problem exploiting the denoising score framework. By approximating the Newton step using a partial Hessian sketch only for the data fit term, it is possible to reduce the complexity while retaining the complex prior structure by a data-driven regularizer.

Tensor decomposition has become an important tool for EEG data analysis. Using time-frequency representation, the EEG data are transformed into a nonnegative tensor. By nonnegative tensor decomposition, EEG feature components will be extracted. In most cases, the extracted EEG components are not only nonnegative but also sparse. Therefore, additional sparse regularization are necessary to improve the extracted sparse components. In this study, we developed a model of CANDECOMP/PARAFAC tensor decomposition with both nonnegative constraint and sparse regularization. The experimental results of real EEG data demonstrate that our method is efficient to extract more meaningful sparse EEG components.

In this work, we aim at broadcasting a toolbox dedicated to meta-heuristics. It integrates the mixed grey wolf optimizer and its adaptive version, and other methods such as particle swarm optimization, grey wolf optimizer, tree seed algorithm, multiverse optimizer, and hybrid gravitational search algorithm. The toolbox integrates the possibility of an intense graphics where the search agents are displayed during the iterative process. An application to the joint estimation of image acquisition and processing parameters has been considered to illustrate the abilities of the amixedGWO.

A limitation of Lasso-type estimators is that the regularization parameter depends on the noise level which varies between experiments. Estimators such as the concomitant Lasso address this dependence by jointly estimating the noise level and the regression coefficients. In this work, we propose an estimator that can cope with correlated Gaussian noise by using non-averaged measurements and a concomitant formulation. The resulting optimization problem is convex, so thanks to smoothing theory, it is amenable to state-of-the-art proximal coordinate descent techniques that can leverage the expected sparsity of the solutions. Practical benefits are demonstrated on simulations and on neuroimaging applications.

This paper considers the problem of learning a complete (orthogonal) dictionary from sparsely generated sample signals. Unlike conventional methods that minimize L^1 norm to exploit sparsity and learns the dictionary one column each time, we propose instead to maximize L^4 norm to learn the entire dictionary over the orthogonal group in a holistic fashion. We give a conceptually simple and yet effective algorithm based on matching, stretching, and projection (MSP). We study the expected behaviors of the optimization problem and give a proof for the local convergence of the proposed MSP algorithm, as well as its superlinear (cubic) convergence rate.

We propose a splitting scheme which hybridizes generalized conditional gradient with a proximal step which we call CGALP, for constrained minimization. The minimization is subject to an affine constraint, which we address by the augmented Lagrangian approach, that allows in particular to deal with composite problems having sums of many functions using a product space technique. We show asymptotic feasibility for the affine constraint, weak convergence of the dual variable to an optimum, and convergence of the Lagrangian values to the optimum. We provide (subsequential) rates of convergence for both feasibility and the Lagrangian values. Experimental results also given.

This paper considers the problem of estimating a nonnegative low-rank matrix from noisy Poisson observations of all or a subset of its entries. Specifically, we analyze an estimator defined by a constrained nuclear-norm minimization program. We derive a high-probability upper error bound (in the Frobenius norm metric) that depends on the matrix rank, the fraction of entries observed, and maximal row and column sums of the true rate matrix. We furthermore show that this bound is (within a constant) minimax optimal in classes of matrices with low rank and bounded row and column sums.

We study the problem of subspace tracking (ST) in the presence of missing data (ST-miss). To our knowledge, our result is the first complete guarantee for ST-miss. This means we are able to show that, under assumptions on only the algorithm inputs, the output subspace estimates are close to the true data subspaces at all times. Our guarantees hold under mild and easily interpretable assumptions, and allow the underlying subspace to change. Moreover, our approach provides a provably correct online, fast, and memory-efficient solution to low-rank Matrix Completion (MC).

In this work, we address the following question: Given a single measurement obtained from a real imaging system, what is the best way to use a learnable model and our knowledge about the physics of the modality to solve the inverse problem and reconstruct the latent image? Standard supervised learning based methods approach this problem by collecting datasets of aligned measurements and the corresponding latent images. However, these methods coule be sometimes impractical due to the unavailability of such datasets. We propose a self-supervised learning based framework for inverse problems in medical imaging.

We present a denoiser for hyperspectral data cubes, based on GMM modeling and corresponding MMSE denoising of ``blocks" (3D ``cubicles"). The rationale of this approach is that it exploits simultaneously spatial and inter-band dependencies. Experiments suggest that the proposed method outperforms other state-of-the-art methods.

We consider the problem of learning a function from a sequence of its noisy samples in a continuous-domain hybrid search space. We adopt the generalized total-variation norm as a sparsity-promoting regularization term to make the problem well-posed. We prove that the solution of this problem admits a sparse kernel expansion with adaptive positions. We also show that the sparsity of the solution is upperbounded by the number of data points. This allows for an enlargement of the search space and ensures the well-posedness of the problem.

In sketched clustering, a dataset of T samples is first sketched down to a vector of modest size, from which the centroids are subsequently extracted. Advantages include reduced storage complexity and centroid extraction complexity independent of T. For the sketching methodology recently proposed by Keriven, et al., which can be interpreted as a random sampling of the empirical characteristic function, we propose a sketched clustering algorithm based on approximate message passing. Numerical experiments suggest that our approach is more efficient than the state-of-the-art sketched clustering algorithm “CL-OMPR” (in both computational and sample complexity) and more efficient than k-means++ when T is large.

In sparse linear regression, the SLOPE estimator generalizes LASSO by assigning magnitude-dependent regularizations to different coordinates of the estimate. In this paper, we present a precise asymptotic characterization of the performance of SLOPE in the high-dimensional regime. Our characterization enables us to derive optimal regularization sequences to either minimize the MSE or to maximize the power in variable selection under any given level of Type-I error. Numerical simulations verify our asymptotic predictions as well as the superiority of optimal design over LASSO and a regularization sequence previously proposed in the literature.

(This work has been accepted to ISIT 19)

We study the problem of signal recovery for group-models. We derive model projection complexity results and algorithms for more general group models than the state-of-the-art. We consider the classical Iterative Hard Thresholding algorithm (IHT) and its approximate version (AM-IHT). We apply both variants to group-models and analyse the two cases where the sensing matrix is a Gaussian matrix and a model expander matrix.

Sparse signal reconstruction is performed by minimizing the sum of a least-squares fit regularized with a piecewise rational approximation of l0. We show the benefit of an oracle that yields the sign of the signal when using a recent methodology for global polynomial or semi-algebraic minimization. The computational time and memory cost are both decreased.

Linear Blind Source Separation (BSS) has known a tremendous success in various fields. In this work, we however depart from the usual linear setting and tackle the case in which the sources are mixed by an unknown non-linear function. We propose to use a sequential decomposition of the data enabling its approximation by a linear-by-part function. Beyond separating the sources, the introduced StackedAMCA can further empirically learn in some settings an approximation of the inverse of the unknown non-linear mixing, enabling to reconstruct the sources despite a severely ill-posed problem. The quality of the method is demonstrated experimentally.

Motivated by problems arising in the numerical approximation of the full solution to some elliptic and parametric PDEs, we present an extension of compressed sensing by combining two model-based approaches, namely the group-sparse model with some prior information in the form of weights. By combining both ideas, we are able to prove optimal convergence rate (within log factors) to the full solution map, even in high dimensional parametric spaces.

Current popular methods for Magnetic Resonance Fingerprint (MRF) recovery are bottlenecked by the heavy storage and computation requirements of a dictionary-matching step in multi-parametric quantitative MRI applications. We study a deep learning approach to address this issue and to approximate the (temporal) Bloch response manifold projection. Fed with non-iterated back-projected images, the network alone is unable to fully resolve spatially-correlated artefacts which appear in highly undersampling regimes. We propose an accelerated iterative reconstruction to minimize these artefacts before feeding into the network. This is done through a convex regularization that jointly promotes spatio-temporal regularities of the MRF time-series.

We propose a rate-distortion framework for explaining deep neural network decisions. We formulate the task of determining the most relevant input signal components for a classifier prediction as an optimisation problem. For the special case of binary signals and Boolean classifier functions we show that it is hard to solve as well as hard to approximate. Finally, we present a heuristic solution strategy for deep ReLU (rectified linear unit) neural network classifiers, a widely used type of classifiers, based on assumed density filtering. We present numerical experiments and compare our method to other established methods for explaining neural network decisions.

Max-affine regression refers to a model where the unknown regression function is modeled as a maximum of k affine functions. This generalizes linear regression, phase retrieval and is related to convex regression. We study this problem in high-dimensional setting and focus on estimating the coefficients of the affine functions. We analyze an alternating minimization algorithm for the non-convex least squares objective with random design. We show that the algorithm, initialized suitably, converges at a geometric rate to a small ball around the optimal parameters whose radius is minimax optimal as a function of the dimension, sample size, and noise variance.

Variational-based methods are the state-of-the-art in sparse image deconvolution. Yet, this class of methods might not scale to large dimensions of interest in current high resolution imaging applications. To overcome this limitation, we propose to solve the sparse deconvolution problem through a two-step approach consisting in first solving (approximately and fast) an optimization problem following by a neural network for "Deep Post Processing" (DPP). We illustrate our method in the context of radio astronomy, where scalability of algorithms is paramount. Preliminary results suggest that DPP is able to achieve similar quality to state-of-the-art algorithms in a fraction of the time.

We propose a branch-and-bound algorithm for the global optimization of problems mixing least-squares criteria and the l_0 norm. A specific tree search exploration strategy is built, based on forward selection heuristics. The evaluation of each node is considered through convex optimization problems involving the l_1 norm and box constraints. We propose a dedicated homotopy procedure for such step. The resulting algorithms are shown to outperform the state-of-the-art CPLEX mixed integer programming solver, and enable the exact resolution of problems involving 1000 unknowns in less than 1000 seconds, for which CPLEX mostly fails.

Medical ultrasound (US) is a widespread imaging modality

owing its popularity to cost efficiency, portability, speed, and lack

of harmful ionizing radiation. In this paper, we demonstrate that

replacing the traditional ultrasound processing pipeline with a data-

driven, learnable counterpart leads to significant improvement in image

quality. Moreover, we demonstrate that greater improvement can be

achieved through a learning-based design of the transmitted beam

patterns simultaneously with learning an image reconstruction pipeline.

We present a local convergence analysis for proximal vari- ance reduced stochastic gradient methods: SAGA [4] and Prox-SVRG [6]. Under the assumption that the non-smooth function is partly smooth, we present an analysis for the local convergence behaviours of SAGA/Prox- SVRG: (i) the sequences generated by the methods are able to identify the smooth manifold in a finite number of iterations; (ii) then the sequence enters a local linear convergence regime. The result is illustrated by several concrete examples and supported by numerical experiments.

Deep learning has emerged as a competitive new tool in image reconstruction. However, recent results demonstrate such methods are typically highly unstable - tiny, almost undetectable perturbations cause severe artefacts in the reconstruction, a major concern in practice. This is paradoxical given the existence of stable state-of-the-art methods for these problems. Thus, approximation theoretical results non-constructively imply the existence of stable and accurate neural networks. Hence the fundamental question: Can we explicitly construct/train stable and accurate neural networks for image reconstruction? We prove the answer is yes and construct such networks. Numerical examples of the competitive performance are also provided.

We propose a new smoothed "lp -Over-lq" norm ratio for sparse signal reconstruction. A trust-region Variable Metric Forward-Backward is proposed to solve the resulting non-convex minimization problem. Numerical experiments in the context of mass spectrometry (MS) data processing illustrate the benefits of the novel penalty.

Reweighted l1 minimization has been successfully applied to the task of audio declipping by Weinstein and Wakin (2011). We adapt the reweighting to the audio inpainting problem, for both the synthesis and the analysis models. It is shown that the reweighting provides a significant improvement in terms of SNR, especially in the analysis model.

In this paper we study a partially delocalized probe construction, in which the point probe is replaced with a continuous line, creating a sensor which essentially acquires line integrals of the target image. We show through simulations, rudimentary theoretical analysis, and experiments that these line measurements can image sparse samples far more efficiently than traditional point measurements. Despite this promise, practical reconstruction from line measurements poses additional difficulties: the measurements are partially coherent, and real measurements exhibit nonidealities. We show how to overcome these limitations using natural strategies (reweighting to cope with coherence, blind calibration for nonidealities), culminating in an end-to-end demonstration.

Dictionary learning, paired with sparse coding, aims at providing sparse data representations. When dealing with large datasets, the dictionary obtained by applying unstructured dictionary learning methods may be of considerable size, posing both memory and computational complexity issues. We show how a previously proposed structured dictionary learning model, HO-SuKro, can be used to obtain more compact and readily-applicable dictionaries when the targeted data is a collection of multiway arrays. We introduce an alternating optimization learning algorithm and apply it to a hyperspectral image denoising task.

Recently, the recovery of binary sparse signals from compressed linear systems has received attention due to its several applications. In this contribution, we review the latest results in this framework, that are based on a suitable non-convex polynomial formulation of the problem. Moreover, we propose novel theoretical results. Then, we show numerical results that highlight the enhancement obtained through the non-convex approach with respect to the state-of-the-art methods.

In this paper we present a novel algorithm along with associated recovery guarantees for solving a particular dictionary learning problem. The dictionary in question is a randomly generated, sparse, binary matrix with a fixed number of non-zeros per column, while the latent representation is random, real, k sparse and dissociated. The algorithm presented leverages properties of expander graphs to efficiently recover both the dictionary and latent representation simultaneously.

Unsupervised dictionary learning is applied to vibration signals recorded from six geographically nearby wind turbines. We propose condition indicators based on dictionary distance, which are evaluated on approximately four years of operational data. We find that these indicators assume abnormal values six months before a bearing issue is identified using conventional methods. In addition, we identify a correlation between the bearing kinematical frequency and the activation rate of atoms. The dictionaries learned from signals from healthy turbines are remarkably similar and can be useful to verify the vibration signature of similar new turbines.

Total variation (TV) norm has been widely used in compressed sensing.

In this paper, given multiple measurement vectors (MMVs), we study the alternating direction method of multipliers (ADMM) algorithm to solve the multiple TV (MTV) norm minimization problem.

In ADMM-MTV, we derive the closed-form solutions of all subproblems to ease implementation.

ADMM-MTV is able to reconstruct all image signals simultaneously, which is more efficient than the traditional TV norm minimization problem that conducts sparse recovery individually.

In addition to computation complexity analysis and comparison, we also verify that the MTV norm outperforms TV norm in terms of two applications.

In recent years, there is a significant improvement in the samples produced by generative models such as variational auto-encoders and generative adversarial networks. Yet, the representation capabilities of these methods do not capture the full distribution for complex classes of images, such as human faces. This is clearly observed in regression applications. This work suggests two strategies to make the solutions of inverse problems using pre-trained generative models more faithful to the observations (and thus more accurate), despite the limited representation capabilities of the generators. We empirically demonstrate the advantages of our proposed approach for image super-resolution and compressed sensing.

We present a parallel version of the cut-pursuit algorithm for minimizing functionals involving the graph total variation. We show that the decomposition of the iterate into constant connected components, which is at the center of this method, allows for the seamless parallelization of the otherwise costly graph-cut based refinement stage. We demonstrate experimentally the efficiency of our method, from simple denoising to more complex inverse problems with nondifferentiable penalties. In short, we argue that our approach combines the efficiency of graph-cuts based optimizers with the versatility and ease of parallelization of more traditional proximal splitting methods.

This work proposes a new general mathematical framework for blind two-dimensional super-resolution theory to recover the unknown continuous shifts and amplitudes in a mixture of unknown waveforms upon using the received signal only. We prove that when the number of the observed samples satisfies certain lower bound, the continuous two-dimensional shifts, the attenuation factors, and the unknown waveforms can all be recovered precisely and with high probability via solving a convex atomic norm problem.

Finite Rate of Innovation (FRI) theory considers sampling and reconstruction of classes of non-bandlimited signals, such as streams of Diracs. Widely used FRI reconstruction methods involve Singular Value Decomposition (SVD). When samples are corrupted with noise, they achieve an optimal performance given by the Cramér-Rao bound yet break down at a certain Signal-to-Noise Ratio (SNR) due to the so-called subspace swap problem. In this paper, we investigate a deep neural network approach for FRI signal reconstruction that directly learns a transformation from signal samples to FRI parameters. Simulations show significant improvement on the breakdown SNR over existing FRI methods.

Blind Source Separation has proven to be an efficient tool to recover meaningful information from multivalued data. However, most methods do not take into account spectral variabilities, therefore failing at modeling many real-world data (remote sensing, astrophysics to cite only a few) and leading to estimation errors. To overcome this pitfall, we propose a method that fully accounts for spectral variabilities by using the Perturbated Linear Mixture Model and we exploit sparse modeling to recover spatially variant spectra. Preliminary results show a significant improvement on the detection of spectral variabilities in comparison with State-of-the-Art algorithms.

We consider the challenge of reconstructing jointly sparse vectors from linear measurements. Firstly, we show that by utilizing the rank of the output data matrix we can reduce the problem to a full column rank case. This result reveals a reduction in the computational complexity of the original problem and enables a simple implementation of joint sparse recovery algorithms for full rank setting. Secondly, we propose a new method for joint sparse recovery in the form of a nonconvex optimization problem on a non-compact Steifel manifold.

Short-and-sparse deconvolution (SaSD) is the problem of extracting localized, recurring motifs in natural signals. Variants of this problem arise in image deblurring, microscopy, and other applications. SaSD is challenging in both theory and practice. Natural optimization formulations are nonconvex. Moreover, practical deconvolution problems involve smooth motifs, resulting in poor spectral conditioning and numerical challenges. We develop a practical algorithm by leveraging key ideas from recent theoretical advances in nonconvex optimization, and by applying heuristics to mitigate challenges posed by ill-conditioning of real SaSD problems. Experiments demonstrate both the performance and generality of the proposed method.

We here first analyze the solutions of low-rank

matrix factorization methods for bilinear mixtures of an arbitrary number

of source signals, in terms of estimated sources

(separability properties) and estimated mixing model parameters (identifiability

properties), without requesting non-negative data.

We show that this Bilinear Mixture Matrix Factorization (BMMF) yields an

essentially unique decomposition (i.e. unique up to scale and permutation

indeterminacies) under mild conditions.

Associated practical BMMF algorithms are also discussed.

Test results prove the relevance of the assumptions used in

this separability/identifiability investigation and

show the performance of these algorithms for

multispectral and hyperspectral remote sensing data.

Iterative reweighted methods for sparse recovery and low-rank matrix estimation have been flourished in recent years. As it has been shown, these approaches offer significant merits when it comes both to the recovery performance and the computational efficiency of the derived algorithms. On the other hand, the use of low-rank matrix factorization for encoding low-rankness has been pivotal in numerous machine learning applications that involve big and high dimensional data lately. In this work, a novel iterative reweighted approach for low-rank matrix factorization is presented. The proposed approach gives rise to scalable algorithms for Schatten-$p$ norm minimization with $0<p\leq 1$. The efficiency of the resulting schemes is empirically verified in a matrix completion problem.

Recovering a low-rank matrix from phaseless linear projections of each of its columns finds important applications in phaseless dynamic imaging. This work introduces the first simple and provably correct solution for this problem. Practical advantage of our proposed approach, AltMin-PhaPCA, over existing work is demonstrated via simulations and real-data experiments. Under assumption of denseness of right singular vectors, our guarantee shows that, in the regime of small ranks, r, the sample complexity of AltMin-PhaPCA is much smaller than what standard phase retrieval methods need; and it is only r^3 times the order-optimal complexity for low-rank matrix recovery.

Phase Retrieval aims to recover a signal from its phaseless measurements. Some of the successful methods for solving this problem use a non-convex optimization in which having a good initialization is crucial. The spectral method is one of the well-known methods for such initialization.

Here, we study the spectral method when the measurements matrix is partial Orthonormal. We have observed phase-transition phenomena which can be characterized completely under some mild assumptions on the trimming function used in the spectral method. Moreover, the result surprisingly matches with what obtained via approximate message passing in the other paper of the same authors.

We analyze the proximity operator of the mixed L1,oo matrix norm. We provide a simple expression for its computation that generalizes the well-known soft-thresholding algorithm. By exploiting the duality relationship to the Loo,1 norm we also derive the projection operator onto the Loo,1 ball. From our analysis, we are able to derive efficient algorithms for the computation of the proximal operator of the L1,oo norm that can be orders of magnitude faster than the state of the art. We also apply the Loo,1 norm for biomarker discovery (feature selection) for the problem of cancer classification from gene expression data.

We investigate the recovery of a partially observed high-rank matrix whose columns obey a nonlinear structure. The structures we cover are clusters and algebraic varieties, such as unions of subspaces. Using a nonlinear lifting to a space of features, as proposed by Ongie et al. in 2017, we reduce the problem to a constrained non-convex optimization formulation, which we solve using Riemannian optimization methods. We give theoretical convergence and complexity guarantees and provide encouraging numerical results for the recovery of low dimensional varieties and clusters.

We study a simple spectral method for estimating a low-rank subspace from a collection of nonlinear measurements. In particular, we present an exact asymptotic characterization of the performance of the method, which also reveals a phase transition phenomenon. To illustrate our results, we consider the examples of multiplexed phase retrieval and the learning of two-layer neural networks. In both cases, our analytical predictions accurately match simulation results. Moreover, the theoretical results allow us to derive optimal forms of the spectral method, which lead to further performance improvement.

A novel algorithm for the recovery of low-rank matrices acquired via compressive linear measurements is proposed and analyzed. The algorithm, a variation on the iterative hard thresholding algorithm for low-rank recovery, is designed to succeed in situations where the standard rank-restricted isometry property fails, e.g. in case of subgaussian rank-one measurements. The algorithm is stable, robust, and performs well empirically.

Change point detection and localization is a classical problem in time series analysis, in which we record a series of measurements and wish to determine whether and at what time(s) the underlying generative model has changed. Recent change point detection works have focused on the regression setting in which only noisy, linear projection measurements of the high dimensional vectors are available. In this article, we introduce a novel method for the change point model in the high dimensional regression setting. We will show that both in theory and in simulations, our method consistently outperform the existing state-of-art methods.

In many applications, we face to consider rank minimization problem from quadratic measurements. Motivated by this fact, we introduce three gradient-like approaches starting from a careful initialization for solving this quadratic sensing problem. Moreover, an efficient initialization estimator is proposed for quadratic sensing problem and it can provide high quality initial guess compared with exiting method. Experimental results not only clearly demonstrate the superiority of introduced initialization estimator but also show the advantages of our three gradient-like approaches in terms of both sample complexity and computational complexity.

This paper showcases the Sliding Frank-Wolfe (SFW), which is a novel optimization algorithm to solve the BLASSO sparse spikes super-resolution problem. The BLASSO is a continuous (i.e. off-the-grid or grid-less) counterpart to the well-known $\ell^1$ sparse regularisation method (also known as LASSO or Basis Pursuit). Our algorithm is a variation on the classical Frank-Wolfe (also known as conditional gradient) which follows a recent trend of interleaving convex optimization updates (corresponding to adding new spikes) with non-convex optimization steps (corresponding to moving the spikes). We prove theoretically that this algorithm terminates in a finite number of steps under a mild non-degeneracy hypothesis.

This paper addresses the problem of ultrasound (US) image restoration. In contrast to most of the existing approaches that only take into account fundamental radiofrequency (RF) data, the proposed method also considers harmonic US images. An algorithm based on the alternating direction of multipliers method (ADMM) is proposed to solve the joint deconvolution problem. Simulation results show the interest of the proposed approach when compared to classical US image restoration schemes based only on fundamental data.

Magnetic Resonance Fingerprint (MRF) methods typically rely on dictionary matching to map the temporal MRF signals to quantitative tissue parameters. These methods suffer from heavy storage and computation requirements as the dictionary size grows. To address these issues, we proposed an end to end fully convolutional neural network for MRF reconstruction (MRF-FCNN), in which coupled with a linear dimensionality reduction layer and a fully convolutional neural network, directly project data from the original MRF space into the tissue parameters manifold. Experiments on real data demonstrate the effectiveness of the method.

We analyze the suitability of ReLU neural networks for the approximation of solutions of parametric partial differential equations. Without any concrete knowledge about its shape, we exploit the intrinsic low-dimensionality of the solution manifold established by the theory of reduced bases. To be more precise, for a large variety of parametric PDEs it is possible to construct neural networks that yield approximations of the parameter-dependent maps which avoid a curse of dimension and essentially only depend on the size of the reduced basis. The obtained rates are significantly better than those provided by classical approximation results.

We investigate the convergence rate analysis of the classical inexact augmented Lagrangian method (iALM) for nonlinear-constrained non-convex problems subject to a geometric condition involving the nonlinear operator. We show that when coupled with a first-order method, iALM finds first-order stationary points in $\tilde{\mathcal{O}}(1/\epsilon^3)$ calls to the first-order oracle. In addition, when coupled with a second-order method, iALM finds second-order stationary points in $\tilde{\mathcal{O}}(1/\epsilon^5)$ calls to the second-order oracle. We provide numerical evidence on large-scale signal processing and machine learning problems, modeled typically via semidefinite relaxations, for which we verify the geometric condition.

In image and signal processing, quantities of interest are often reconstructed by means of convex optimization problems. Data driven approaches are motivated by situations where the objective is partially unknown and shall be learned from data. This gives rise to bilevel problems where the original problem appears as constraint and poses the difficulty to differentiate the solution operator. We consider the approach to unroll update steps of the Chambolle-Pock algorithm in order to accomplish the differentiation approximately. We investigate the asymptotic behavior of the gradients and conclude that unrolling ergodic averages can have a positive effect on the learning dynamics.

The learning of models for multi-dimensional signals is a key problem in several machine learning tasks. Similarly, many machine learning problems involve the learning of multidimensional functions. The direct representation of the function suffers from curse of dimensionality. Fortunately, real-world multidimensional signals often have considerable redundancy, which can be exploited by modeling them as points on smooth surfaces. We propose to capitalize this structure by modeling the surfaces as the zero-set of a bandlimited function. We use this model to recover the surface from few measurements. This model also allows us to recover bandlimited functions that live on the surfaces.

Parameter selection is a challenging problem that is crucial in many paradigms of machine learning and variational regularization. Motivated by a recent line of research, we propose

an unsupervised, automated algorithm for the computation of a nearly optimal regularization parameter for non-linear regularization methods and various noise models.

The proposed method shows great performance on several tasks in image denoising and signal recovery with TV and elastic nets.

It is well-known that Orthogonal Matching Pursuit (OMP) recovers the exact support of K-sparse signals under the condition mu<1/(2K-1) where mu denotes the mutual coherence of the dictionary. In this communication, we show that under the same condition and if the unknown K-sparse signal is non-negative, the weights of the atoms selected by OMP are non-negative at any of the first K iterations. Therefore, the generalized version of OMP to the non-negative setting (NNOMP) identifies with OMP, which allows us to establish an exact recovery analysis of NNOMP under the mutual coherence condition.

We propose a novel framework for combining datasets via alignment of their associated intrinsic geometry. Importantly, we do not assume any pointwise correspondence between datasets, but instead rely on correspondence between a subset of features. We leverage this assumption to estimate relations between intrinsic diffusion dimensions, which are computed from graph Fourier coefficients of data features. These relations are used to form an isometric alignment between diffusion maps which can also be used to correct the original data measurements. We demonstrate our method on several datasets, showing its effectiveness in biological applications including data fusion and batch effect removal.

In this paper, we propose a novel method to learn a pair of analysis dictionary and soft-threshold which is used to construct the deep dictionary model for regression tasks. The learned analysis dictionaries together with the corresponding soft-thresholds can simultaneously preserve important information from the previous layer as well as facilitate discrimination of key features. Simulation results show that our proposed deep dictionary model achieves comparable performance with DNNs.

Inexact dual certificates have become a staple of exact recovery studies in compressed sensing, particularly when dealing with structured measurements. Nonetheless, each time a new pair of sparsifying transform and measurement matrix is considered, the characteristics for identifying approximate certificate are re-derived, considering the particulars of whether the measurements are isotropic or the analysis operator is invertible or injective. This paper aims at describing a general recipe for supplying dual certificates that generalizes the existing ones in the literature while keeping constraints on the relevant linear operators to a minimum.

Many machine learning and signal processing applications involve high-dimensional nonsmooth optimization problems. The nonsmoothness is essential as it brings a low-dimensional structure to the optimal solutions, as (block, rank, or variation) sparsity. In this work, we exploit this nonsmoothness to reduce the communication cost of optimization algorithms solving these problems in a distributed setting. We introduce two key ideas: i) a random subspace descent algorithm along sparsity directions; ii) an adaptative subspace selection based on sparsity identification of the proximal operator. We get significant performance improvements in terms of convergence with respect to data exchanged.

We investigate the recovery of partially sparse signals with regularization of the signal part for which no sparsity prior is known, to overcome the complete loss of recoverability by previous approaches without such modifications. For certain mixed $\ell^{1}$-$\ell^{2}$-norms and Luxemburg norms, we present optimality conditions for recovery and some numerical experiments.

We investigate regularization of linear inverse problems by generalized Tikhonov regularization that promotes sparsity. We are interested in penalties on sequence spaces where each coordinate is regularized by an individual penalty function and specifically in the case where these functions are non-convex.

We leverage convex optimization techniques to perform Bayesian uncertainty quantification (UQ) for hyperspectral (HS) inverse imaging problems.The proposed approach generalizes our recent work for single-channel UQ. Similarly, the Bayesian hypothesis test is formulated as a convex minimization problem and solved using a primal-dual algorithm to quantify the uncertainty associated with particular 3D structures appearing in the maximum a posteriori (MAP) estimate of the HS cube. We investigate the interest of the proposed method for wideband radio-interferometric (RI) imaging that consists in inferring the wideband sky image from incomplete and noisy Fourier measurements. We showcase the performance of our approach on realistic simulations.

Auto-encoders (AE) are a particular type of unsupervised neural networks that aim at providing a compact representation of a signal or an image. Such AEs are useful for data compression but most of the time the representations they provide are not appropriate as is for a downstream classification task. This is due to the fact that they are trained to minimize a reconstruction error and not a classification loss. Inspired by label-consistent K- SVD in sparse coding context, we propose a novel supervised version of AEs that integrates class information within the encoded representations.

The variations in many types of data are constrained by natural physical laws and identity-preserving variations are often shared between several classes. In many settings, the within-class variation in a high-dimensional dataset can be modeled as being on a low-dimensional manifold. If the manifold structure shared between classes can be learned, it can be exploited for transfer learning tasks. In this work, we represent the manifold structure using a learned dictionary of generative operators and develop methods for using those operators for few-shot learning and realistic data generation to demonstrate state of the art manifold learning performance in transfer settings.

In this work, we are interested in unmixing complex mixtures based on Nuclear Magnetic Resonance spectroscopy spectra. More precisely, we propose to solve a 2D blind source separation problem where signals (spectra) are highly sparse. The separation is formulated as a nonnegative matrix factorization problem that is solved using a block coordinate proximal gradient algorithm involving various sparse regularizations. An application to 2D NMR HSQC experience is presented and shows the good performances of the proposed method.

We study the problem of image recovery from subsampled Hadamard measurements using Haar wavelet sparsity prior. This problem is appealing in, e.g., computational imaging applications relying on optical multiplexing. While high coherence between the Hadamard and Haar bases hinders the efficacy of such devices, multilevel density sampling strategy solves this issue by adjusting the subsampling process to the local coherence between the two bases; hence allowing for successful image recovery. In this work, we compute an explicit sample-complexity bound for Hadamard-Haar systems; a seemingly missing result in the related literature. The power of this approach is demonstrated on several simulations.

Super resolution (SR) arises in many areas of science and engineering, and various methodologies have been developed. The currently best performing methods are based on neural networks, which rely on large training sets and, in general, lack interpretability and theoretical guarantees. Earlier sparsity-based methods, in contrast, require no training data, which makes them robust. Furthermore, being based on convex optimization, they have strong theoretical foundations. We propose a method that combines both models, leveraging the good performance of neural networks and the robustness of sparsity-based methods. Experiments show that it significantly outperforms state-of-the-art SR algorithms in the quality of reconstruction.

We present our recent work on sampling along spiral-like curves, and discuss the main techniques. As a first result we give a sharp density condition for sampling on spirals in terms of the separation between consecutive branches. We then further show that, below this rate, the numerical stability related to the reconstruction of compressible signals when sampled along spirals is significantly limited by the amount of undersampling.

We focus on signal processing tasks in which the signal is mapped via some integral transform to a higher dimensional space, called phase space, processed there, and synthesized to an output signal. We show how to approximate such methods using a stochastic approach. The stochastic method speeds up computations, since the number of samples required for a certain accuracy is proportional to the dimension of the signal space, and not to the dimension of phase space, which is typically higher. We utilize this property for a new phase-vocoder method (in audio signal processing), based on an enhanced time-frequency space.

In this talk, on a compact Riemmannian manifold M, we discuss construction of tight frames in L2(M) in both the continuous and semi-discrete settings. We show that polynomial-exact quadrature rules on M give a simple way of constructing semi-discrete tight framelets in L2(M). We describe fast framelet filter bank transforms (FMTs) with nearly linear computational complexity and low redundancy rate based on the fast algorithms for discrete Fourier transforms (FFTs) on M. Moreover, We construct framelets on the 2-sphere S2 with two high passes (b1 and b2) and gives numerical examples for the FMT algorithms on S2.

Variable splitting is an old but widely used technique which aims at dividing an initial complicated optimization problem into simpler sub-problems. In this work, we take inspiration from this variable splitting idea to build efficient Markov chain Monte Carlo (MCMC) algorithms. Starting from an initial complex target distribution, auxiliary variables are introduced such that the marginal distribution of interest matches the initial one asymptotically. In addition to have theoretical guarantees, the benefits of such an asymptotically exact data augmentation (AXDA) are fourfold: simpler full conditional distributions, possibility to embed existing MCMC approaches, to distribute the inference and to respect data privacy issues.

Coupled tensor decomposition has become a popular technique for the simultaneous analysis of multiblock tensors in recent years. To achieve group analysis of multiblock tensors, we propose a fast double-coupled nonnegative Canonical Polyadic decomposition (FDC-NCPD) algorithm. It enables the simultaneous extraction of common components and individual components. In addition, its time-consumption is greatly reduced without compromising the decomposition quality when handling large-scale problems. Simulation results demonstrate the superior performance of the proposed algorithm.

We consider approximating a 2D shape contour using discrete graph-assembly systems, which consist of limited sets of node and edge types along with edge length and orientation restrictions. We show that already deciding feasibility of such approximation problems is NP-hard and then devise an algorithmic framework that combines shape sampling with exact L0-/cardinality-minimization to obtain good reconstructions using few graph components within reasonable time, in spite of the problem’s intractability. As a particular (2D) application, we approximate shape contours using the classical Zometool construction kit.

This work introduces the concept of antisparse Blind Source Separation (BSS). Then we propose a suitable criterion based on the duality between L1 and L_infty norms and demonstrate that it effectively provides BSS for antisparse sources. Our proof considers only two sources, but without loss of generality, since our methodology can be extended to more sources in a deflation procedure.

We present a theoretical analysis of the average performance of OMP for sparse approximation.

Our results improve by an order of magnitude over worst case results and show that OMP and its famous competitor Basis Pursuit outperform each other depending on the setting.

Sparse representation over redundant dictionaries constitutes a good model for many classes of signals. However, despite its popularity, little is known about the representation capacity of this model. In this paper, we study how redundant a dictionary must be so as to allow any vector to admit a sparse approximation with a prescribed sparsity and a prescribed level of accuracy. Specifically, we derive lower and upper bounds on the minimal required overcompleteness. Our bounds have simple closed-form expressions that allow to easily deduce the asymptotic behavior in high dimensions.

We present new theoretical results on sparse recovery guarantees for a greedy algorithm, orthogonal matching pursuit (OMP), in the context of continuous parametric dictionaries, i.e., made up of an infinite uncountable number of atoms.

We build up a family of dictionaries for which k-step recovery is possible.