Signal Processing with Adaptive
Sparse Structured Representations (SPARS)
Workshop 2019
July 14, 2019  Toulouse, France
Conference Agenda
Overview and details of the sessions of this conference. Please select a date or location to show only sessions at that day or location. Please select a single session for detailed view (with abstracts and downloads if available).

Session Overview 
Date: Monday, 01/Jul/2019  
8:30am  9:30am  Registration + coffee  
Hall C  
9:30am  9:40am  Introduction  
Amphi B00  
9:40am  10:40am  Plenary 1: Lenka Zdeborova(CNRS) Are generative models the new sparsity?  
Amphi B00  
10:40am  11:10am  Coffee Break  
C101  C103  
11:10am  12:10pm  Oral session 1 (3 talks)  
Amphi B00  

Sparsity of solutions for variational inverse problems with finitedimensional data KarlFranzensUniversität Graz, Austria 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 socalled staircase effect in imaging and in the second one we obtain a result of Unser, Fageot and Ward under weaker hypotheses.
Optimal Sampling Rates for Compressed Sensing Offthegrid ^{1}University of Bath, United Kingdom; ^{2}Ecole Normale Superieure 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 nontranslation 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.
Bias versus Convexity in Compressed Sensing Lund University, Sweden 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 nuclearnorms, 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.
 
12:10pm  2:30pm  Lunch + Poster session 1  
C101  C103  

Nonsparsity influence on reconstruction timefrequency signals with sparsity constraint Grenoble INP, University of Grenoble Alpes, France
On instabilities of deep learning in image reconstruction ^{1}University of Oslo, Norway; ^{2}Faculdade de Ciências da Universidade do Porto, Portugal; ^{3}University of Bath, UK; ^{4}Simon Fraser University, Canada; ^{5}University of Cambridge, UK
Density evolution of Orthogonal Matching Pursuit ^{1}Insee, France; ^{2}Inria, France; ^{3}Politecnico di Torino, Italy
Negative Binomial Matrix Factorization for Recommender Systems IRIT, Université de Toulouse, CNRS
Closedform Marginal Likelihood in GammaPoisson Matrix Factorization ^{1}IRIT, Université de Toulouse, CNRS, France; ^{2}Criteo AI Lab
Bandlimited Signal Reconstruction from Nonuniform Samples Georgia Institute of Technology, United States of America
A Faceted Prior for Scalable Wideband Computational Imaging ^{1}HeriotWatt University, United Kingdom; ^{2}École Polytechnique Fédérale de Lausanne, Switzerland
A scalable estimator of space varying blurs  application in superresolution ^{1}ITAV, CNRS, France; ^{2}CBI, CNRS, France
Deep Recurrent Brain Source Imaging ^{1}Institut für Mathematik, Technische Universität Berlin, Germany; ^{2}Electrical Engineering and Computer Science, Technische Universität Berlin, Germany; ^{3}Berlin Center for Advanced Neuroimaging (BCAN), Charite Universitätsmedizin Berlin, Germany; ^{4}Berlin Big Data Center, 10587 Berlin, Germany.; ^{5}Berliner Zentrum für Maschinelles Lernen, 10587 Berlin, Germany.; ^{6}Department of Brain and Cognitive Engineering, Korea University, Seoul 02841, South Korea,; ^{7}Max Planck Institute for Informatics, Stuhlsatzenhausweg, Saarbrucken, Germany.
Exploiting regularity in sparse Generalized Linear Models ^{1}INRIA, Université ParisSaclay, Palaiseau, France; ^{2}CNRS & Institut de Mathématiques de Bourgogne, Dijon, France; ^{3}IMAG, Univ Montpellier, CNRS, Montpellier, France
FeTa: Fast and Efficient Pruning of Deep Neural Networks ^{1}EPFl, Switzerland; ^{2}University of Edinburgh, UK
Iterative lowrank and rotating sparsity promotion for circumstellar disks imaging ^{1}ISPGroup, ICTEAM, UCLouvain, Belgium; ^{2}Max Planck Institute for Astronomy, Germany
On the Local Minimizers of the CEL0 Relaxation ^{1}IRIT, University of Toulouse, CNRS, France; ^{2}University Côte d'Azur, CNRS, INRIA, i3S, France; ^{3}University Côte d'Azur, INS, LJAD, France
The Adaptive Dictionary Learning Toolbox ^{1}IIT, Italy; ^{2}University of Innsbruck, Austria
Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization ^{1}Princeton University, United States of America; ^{2}Carnegie Mellon University, United States of America
An L0 solution to sparse approximation problems with continuous dictionaries ^{1}IRAP, Université de Toulouse/CNRS/CNES, France; ^{2}LS2N, École Centrale de Nantes/CNRS, France
Distributed sparse BSS for largescale datasets CEA, France
Learning to unmix from Poisson measurements with application to γspectroscopy ^{1}CEADRF/IRFU, France; ^{2}IRSNLMRE; ^{3}CEADRT/LIST, France
Linear convergence and support recovery for nonconvex multipenalty regularisation ^{1}Simula Research Laboratory, Norway; ^{2}RWTH Aachen University
Magnetic Resonance and Ultrasound Image Fusion Using a PALM Algorithm ^{1}University of Toulouse, IRIT, CNRS, INPENSEEIHT, Université Paul Sabatier Toulouse 3, France; ^{2}CHU Toulouse, Obstetrics Gynecology Department, Paule de viguier Hospital Toulouse F31059, France
Spatiallyfiltered temporal dictionary learning for calciumimaging analysis ^{1}Yale University, United States of America; ^{2}Technion, Israel Institute of Technology, Israel; ^{3}Princeton University, United States of America
TensorFree Algorithms for Convex Liftings of Bilinear Inverse Problems with Applications to Masked Phase Retrieval University of Graz, Austria
A New Perspective on L1Analysis Recovery Technische Universität Berlin, Germany
Compressed Diffusion ^{1}Yale University, United States of America; ^{2}Utah State University, United States of America; ^{3}Université de Montréal, Canada
Towards TheoreticallyFounded LearningBased Denoising ^{1}Columbia University, United States of America; ^{2}Nokia Bell Labs
Graph Based Trajectory Mining United Technologies Research Center, Ireland
Learned Matching Pursuit: a Deep Neural Network for Sparse Approximation University of Edinburgh, United Kingdom
A Theoretical Study of Adversarial Examples ^{1}University of Maryland; ^{2}Cornell University
Linear Simplex Support Vector Regression ^{1}Institut Mathématiques de Bourgogne, France; ^{2}CNRS, France
 
2:30pm  3:30pm  Plenary 2: Pier Luigi Dragotti (Imperial College London) Timing is everything: Sparse sampling based on timeencoding machines  
Amphi B00  
3:30pm  4:10pm  Oral session 2 (2 talks)  
Amphi B00  

Clusterbased Optimal Transport Alignment Georgia Institute of Technology, United States of America The unsupervised alignment (or registration) of point clouds in lowdimensional 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 clusterbased 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 clusterbased methods.
Optimal Transport of Measures in Frequency Domain CNRS and Univ. Grenoble Alpes, France 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.
 
4:10pm  4:40pm  Coffee Break  
C101  C103  
4:40pm  5:40pm  Oral session 3 (3 talks)  
Amphi B00  

On the nonconvex sparse spike estimation problem: explicit basins of attractions of global minimizers ^{1}CNRS; ^{2}Université de Bordeaux; ^{3}Institut de mathématiques de Bordeaux The sparse spike estimation problem consists in recovering offthegrid impulsive sources from underdetermined linear measurements. Information theoretic results ensure that the minimization of a nonconvex functional is able to recover the spikes for adequately chosen measurements (deterministic or random). We study the shape of the global minimum of this nonconvex 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.
A Unified Framework for the Convergence Analysis of Optimization Algorithms via SumofSquares National University of Singapore, Singapore 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 adhoc arguments and casebycase analysis. In this paper, we introduce a novel optimization framework for bounding the convergence rates of various important optimization algorithms by means of sumofsquares certificates. Our approach allows us to recover known convergence bounds for three widelyused firstorder algorithms in a unified manner and puts forward a promising framework for unifying convergence analyses of optimization algorithms.
Eventual linear convergence rate of an exchange algorithm for superresolution. ^{1}Université de Toulouse, France; ^{2}CNRS; ^{3}Institut des Technologies Avancées du Vivant We study an iterative discretization algorithm for solving optimization problems regularized by the total variation norm. Its design relies on ideas from the FrankWolfe algorithm, as well as from semiinfinite programming. For smooth regularity terms, we prove an eventual linear convergence rate guarantee.
 
7:30pm  9:30pm  Welcoming reception  
Le Moaï restaurant 
Date: Tuesday, 02/Jul/2019  
9:00am  10:00am  Plenary 3: Mark Davenport (Georgia Institute of Technology) Subspaces and sparsity on the continuum  
Amphi B00  
10:00am  10:40am  Oral session 4 (2 talks)  
Amphi B00  

Matrix “Desketching”: Unlifted but Convex ^{1}Georgia Institute of Technology, United States of America; ^{2}Ohio State University, United States of America
Matrix rigidity and the illposedness of Robust PCA and matrix completion ^{1}University of Oxford, United Kingdom; ^{2}National Physical Laboratory, United Kingdom; ^{3}The Alan Turing Institute, United Kingdom
 
10:40am  11:10am  Coffee Break  
C101  C103  
11:10am  12:10pm  Oral session 5 (3 talks)  
Amphi B00  

Universal sparsity of deep ReLU networks ^{1}University of Vienna, Austria; ^{2}ETH Zurich, Switzerland 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 cartoonlike 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).
Error bounds for approximations with deep ReLU neural networks in Sobolev norms ^{1}Technische Universität Berlin, Germany; ^{2}University of Oxford, United Kingdom 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.
Emergent Sparsity in Variational Autoencoder Models ^{1}Tsinghua University, China, People's Republic of; ^{2}Microsoft Research, China, People's Republic of Variational autoencoders (VAE) represent a popular form of deep generative model that can be stochastically fit to samples from a random process using an informationtheoretic variational bound on the underlying distribution. While quite effective in numerous application domains, important aspects of the VAE objective are obscured by nonconvexity 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.
 
12:10pm  2:30pm  Lunch + Poster session 2  
C101  C103  

Improving Graph Trend Filtering with NonConvex Penalties ^{1}Dept. of Electrical and Computer Engineering, Carnegie Mellon University, United States of America; ^{2}Tandon School of Engineering, New York University, United States of America 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 nonconvex 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 ADMMbased algorithm to solve the proposed optimization problem and analyze its convergence. Numerical performance of the proposed framework with nonconvex regularizers on both synthetic and realworld data for denoising, support recovery, and semisupervised classification.
Robust Incorporation of Signal Predictions into the Sparse Bayesian Learning Framework Georgia Institute of Technology, United States We propose an algorithm for dynamic filtering of timevarying 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.
Tensor and Coupled Decompositions in Block Terms: Uniqueness and Irreducibility ^{1}CNRS, France; ^{2}IRIT, France; ^{3}Université de Toulouse, France; ^{4}Univ. Grenoble Alpes, France; ^{5}Grenoble INP, France; ^{6}GIPSAlab, France In this work, we present recent results concerning decompositions of tensors and ensembles of matrices in sum of terms that are not necessarily rank1. We formulate mathematically the concept of irreducibility, which is the enabling factor that allows these lowrank 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.
Why deep learning methods for inverse problems typically become unstable University of Cambridge, United Kingdom 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.
Accelerating FirstOrder Methods via Linear Prediction ^{1}University of Bath, United Kingdom; ^{2}University of Cambridge, United Kingdom In this paper, we propose a novel linear prediction frame work for accelerating firstorder methods. We first discuss the trajectory of the sequence generated by firstorder methods, showing that eventually the trajectory obeys certain lowdimensional regularity. Then building on top of such a property, we design a trajectory following linear prediction scheme for accelerating firstorder methods. Numerical experiments on problems arising from inverse problems and image processing demon strate the stateoftheart performance of the proposed algorithm.
Active embedding search via noisy paired comparisons Georgia Institute of Technology, United States of America 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 lowdimensional 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 realworld dataset to validate our strategies over stateoftheart methods.
Benchmarking proximal methods acceleration enhancements for CSacquired MR image analysis reconstruction ^{1}CEA  Neurospin, GifsurYvette, France; ^{2}INRIA  Parietal, GifsurYvette, France; ^{3}CEA  Cosmostat, GifsurYvette, France This work helps people using proximal methods for CSacquired MR image analysis reconstruction. This problem can be framed as an illposed 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.
Compressed sensing and the synthesis formulation ^{1}Sorbonne Université; ^{2}CNRS, Université de Toulouse; ^{3}Technische Universitat Berlin 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 socalled 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.
Compressive kMeans with Differential Privacy ^{1}ICTEAM/ELEN, UCLouvain; ^{2}Univ Rennes, Inria, CNRS, IRISA; ^{3}Imperial College London 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 privacyutility tradeoff for the kmeans clustering problem.
Compressive Phase Retrieval of Structured Signal ^{1}Columbia University, United States of America; ^{2}NokiaBell labs COmpressive PhasE Retrieval (COPER), a novel compressionbased 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 polynomialtime method based on projective gradient descent is proposed and its convergence performance is analyzed.
Fusion of hyperspectral and multispectral infrared astronomical images ^{1}IRITENSEEIHT, France; ^{2}IRAP, France 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.
Learning to Solve Inverse Problems with Neumann Networks ^{1}University of WisconsinMadison; ^{2}University of Chicago Traditional inverse problem solvers minimize a cost function consisting of a datafit 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 endtoend, datadriven method, solving the linear inverse problem directly with a datadriven nonlinear regularizer via a truncated Neumann series. This Neumann network architecture outperforms traditional inverse problem methods, modelfree deep learning approaches, and stateoftheart unrolled iterative methods on standard datasets. When data lies in a union of subspaces, we prove there exists a Neumann network that wellapproximates the optimal oracle estimator.
Local Convolutive Independent Vector Analysis for Reverberant Blind Source Separation ^{1}APC, Univ. Paris Diderot, CNRS/IN2P3 CEA/Irfu, Obs. de Paris, Sorbonne Paris Cité; ^{2}Laboratoire des signaux et systèmes, Univ ParisSud, CNRS, CentraleSupélec, France 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 WindowedGroupLasso. Being able to avoid the permutation alignment and to take advantage of the crossband information during the separation, the proposed approach outperforms the existing methods through numerical evaluations.
Nonuniform recovery guarantees for binary measurements University of Cambridge, United Kingdom 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 nonlinear reconstruction.
Nullspace Conditions for BlockSparse Semidefinite Systems ^{1}TU Braunschweig, Germany; ^{2}TU Darmstadt Germany; ^{3}GoetheUniversität Frankfurt am Main, Germany We consider the recovery of lowrank matrices via a convex nuclearnorm minimization problem and present two null space properties (NSP) which characterize the uniform recovery for the case of blockdiagonal matrices and blockdiagonal positive semidefinite matrices. Moreover, we show that the NSP for blockdiagonal positive semidefinite matrices is weaker than the NSP for blockdiagonal matrices. As a special case, we obtain a similar NSP for blocksparse and nonnegative vectors, which is again weaker than the known NSP for blocksparse vectors.
Numerical Computation for Orthogonal Low Rank Approximation of Tensors Université catholique de Louvain 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 semiorthogonal low rank approximation as two special cases. To deal with this question we present an SVDbased algorithm. Our SVDbased 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.
On the Weighting for Convolutional Sparse Coding ^{1}STMicroelectronics, Italy; ^{2}Tampere University, Finland; ^{3}Politecnico di Milano, Italy; ^{4}Los Alamos National Laboratory, USA We consider image denoising via convolutional sparse coding with weighted \ell1 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 MSEoptimal 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.
OneBit Compressed Sensing by Convex Relaxation of the Hamming Distance ^{1}RWTH Aachen University, Germany; ^{2}Technical University of Munich, Germany In this short note we provide new theoretical analysis of a tractable recovery algorithm for onebit 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 stateoftheart results, as well as comparison to existing methods in numerical simulations.
Outlier Detection Using Generative Models with Theoretical Performance Guarantees ^{1}Department of Electrical and Computer Engineering, University of Iowa, United States of America; ^{2}Institute of Computational Engineering and Science, University of Texas, United States of America 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 generativemodelbased $\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.
Reconstruction of partially sampled STEMEELS images with atomic resolution ^{1}University of Toulouse, IRIT/INPENSEEIHT, Toulouse; ^{2}Laboratoire de Physique des Solides, CNRS UMR 8502, Univ. ParisSud, Univ. ParisSaclay 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 signaltonoise ratio. One solution, considered in this work, consists in spatially partially acquiring the multiband 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 stateoftheart results with a significantly lighter computational cost.
Relaxed contractivity conditions for dictionary learning via Iterative Thresholding and K residual Means ^{1}University of Innsbruck, Austria; ^{2}University of Leoben, Austria In this work we will contribute to the theoretical analysis of one specific dictionary learning algorithm  the Iterative Thresholding and Kresidual 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.
Robust penalized inference for Gaussian Scale Mixtures ^{1}Univ. Grenoble Alpes, France; ^{2}GIPSAlab; ^{3}INRIA; ^{4}CNRS 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 EMalgorithm 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.
Simultaneous Inference and Denoising of Studentt Mixtures from Noisy Observations Instituto de Telecomunicações and Instituto Superior Técnico, University of Lisbon, Portugal We present a variational expectationmaximization (VEM) algorithm to estimate a finite mixture of Studentt distributions from noisy data and denoise that same data. As an illustration, we apply the method to singleimage patchbased image denoising.
Sparse Dictionaries for ContinuousDomain Inverse Problems EPFL, Switzerland We study 1D continuousdomain 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 continuousdomain inverse problems have hybrid spline solutions, i.e. they are sums of splines matched to the regularization operators. We then propose a Bsplinebased exact discretization method to solve such problems algorithmically.
Fast Numerical Methods for Convex Problems with Optimal Transport Regularization Georgia Institute of Technology, United States of America Although convex losses (e.g., L1norm 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 timecomplexity as entropicregularized counterparts but are free from approximationartifacts, (ii) extend variational OT problems to the space of Euclidean signals, and (iii) can easily be extended to recent unbalanced OT formulations.
Learning Fast Magnetic Resonance Imaging ^{1}Technion, Israel; ^{2}University of Waterloo, Canada Magnetic Resonance Imaging (MRI) is considered today the goldenstandard 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 acquisitionreconstruction pipeline endtoend in a differentiable way. We demonstrate the significance of using the learned Cartesian trajectories at different speed up rates.
Regularized Newton Sketch by Denoising Score Matching for Computed Tomography Reconstruction Technical University of Denmark  DTU, Denmark In this work we aim at efficiently solving a modelbased maximumaposterior (MAP) image reconstruction with application to lowdose transmission Xray 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 datadriven regularizer.
Sparse Nonnegative Tensor Decomposition for EEG Data ^{1}School of Biomedical Engineering, Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024, China; ^{2}Faculty of Information Technology, University of Jyväskylä, Jyväskylä 40100, Finland Tensor decomposition has become an important tool for EEG data analysis. Using timefrequency 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.
Adaptive mixed grey wolf optimizer: toolbox for illustration and comparative study Institut Fresnel, Aix Marseille Universite, France In this work, we aim at broadcasting a toolbox dedicated to metaheuristics. 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.
 
2:30pm  3:30pm  Plenary 4: Simon Thorpe (CNRS) UltraSparse Representations in Neural Networks : Biological Inspiration for Artificial Intelligence?  
Amphi B00  
3:30pm  4:10pm  Oral session 6  Student Contest (2 talks)  
Amphi B00  

Concomitant Lasso with Repetitions (CLaR): beyond averaging multiple realizations of heteroscedastic noise ^{1}INRIA Saclay, France; ^{2}IMAG,Univ Montpellier, CNRS, Montpellier, France A limitation of Lassotype 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 nonaveraged measurements and a concomitant formulation. The resulting optimization problem is convex, so thanks to smoothing theory, it is amenable to stateoftheart proximal coordinate descent techniques that can leverage the expected sparsity of the solutions. Practical benefits are demonstrated on simulations and on neuroimaging applications.
A Fast Holistic Algorithm for Complete Dictionary Learning via L^4 Norm Maximization ^{1}UC Berkeley; ^{2}ByteDance Research Lab; ^{3}Columbia University 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.
 
4:10pm  4:40pm  Coffee Break  
C101  C103  
4:40pm  5:40pm  Oral session 7  Student Contest (3 talks)  
Amphi B00  

Generalized Conditional Gradient with Augmented Lagrangian for Composite Optimization ENSICAEN, France 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.
Lowrank matrix completion and denoising under Poisson noise Georgia Institute of Technology, United States of America This paper considers the problem of estimating a nonnegative lowrank matrix from noisy Poisson observations of all or a subset of its entries. Specifically, we analyze an estimator defined by a constrained nuclearnorm minimization program. We derive a highprobability 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.
Subspace Tracking with Missing Data and Matrix Completion Iowa State University, United States of America We study the problem of subspace tracking (ST) in the presence of missing data (STmiss). To our knowledge, our result is the first complete guarantee for STmiss. 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 memoryefficient solution to lowrank Matrix Completion (MC).

Date: Wednesday, 03/Jul/2019  
9:00am  10:00am  Plenary 5: Bhaskar Rao (UC San Diego) Sparse Bayesian Learning: A Beamforming and Toeplitz Approximation Perspective  
Amphi B00  
10:00am  10:40am  Oral session 8 (2 talks)  
Amphi B00  

Selfsupervised learning of inverse problem solvers in medical imaging ^{1}Technion, Israel; ^{2}University of Waterloo, Canada 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 selfsupervised learning based framework for inverse problems in medical imaging.
BlockGaussianMixture Priors for Hyperspectral Denoising Instituto de Telecomunicações and Instituto Superior Técnico, University of Lisbon, Portugal 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 interband dependencies. Experiments suggest that the proposed method outperforms other stateoftheart methods.
 
10:40am  11:10am  Coffee Break  
C101  C103  
11:10am  12:10pm  Oral session 9 (3 talks)  
Amphi B00  

MultipleKernel Regression with Sparsity Constraints Ecole Polytechnique Federale de Lausanne, Switzerland We consider the problem of learning a function from a sequence of its noisy samples in a continuousdomain hybrid search space. We adopt the generalized totalvariation norm as a sparsitypromoting regularization term to make the problem wellposed. 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 wellposedness of the problem.
Sketched Clustering via Hybrid GAMP ^{1}The Ohio State University, United States of America; ^{2}Univ. Rennes, Inria, CNRS, IRISA, France 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 stateoftheart sketched clustering algorithm “CLOMPR” (in both computational and sample complexity) and more efficient than kmeans++ when T is large.
SLOPE for Sparse Linear Regression: Exact Asymptotics and Optimal Sequence Designs Harvard University In sparse linear regression, the SLOPE estimator generalizes LASSO by assigning magnitudedependent regularizations to different coordinates of the estimate. In this paper, we present a precise asymptotic characterization of the performance of SLOPE in the highdimensional 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 TypeI 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)
 
12:10pm  2:30pm  Lunch + Poster session 3  
C101  C103  

Sparse Group Model Selection ^{1}AIMS South Africa, & Stellenbosch University; ^{2}RWTH Aachen University, Germany; ^{3}Research and Development, ZF Group, Germany We study the problem of signal recovery for groupmodels. We derive model projection complexity results and algorithms for more general group models than the stateoftheart. We consider the classical Iterative Hard Thresholding algorithm (IHT) and its approximate version (AMIHT). We apply both variants to groupmodels and analyse the two cases where the sensing matrix is a Gaussian matrix and a model expander matrix.
Sparse Signal Reconstruction with a Sign Oracle ^{1}Center for Visual Computing, CentraleSupélec, INRIA, Université ParisSaclay, France; ^{2}SAMOVAR, Télécom SudParis, CNRS, Université ParisSaclay, CNRS, France Sparse signal reconstruction is performed by minimizing the sum of a leastsquares 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 semialgebraic minimization. The computational time and memory cost are both decreased.
Stacked Sparse NonLinear Blind Source Separation CEA Saclay, France 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 nonlinear function. We propose to use a sequential decomposition of the data enabling its approximation by a linearbypart function. Beyond separating the sources, the introduced StackedAMCA can further empirically learn in some settings an approximation of the inverse of the unknown nonlinear mixing, enabling to reconstruct the sources despite a severely illposed problem. The quality of the method is demonstrated experimentally.
Weighted group sparse compressed sensing for parametric function approximation Beijing Institute of Technology, China, People's Republic of 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 modelbased approaches, namely the groupsparse 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.
Deep learning for Magnetic Resonance Fingerprinting ^{1}University of Bath, United Kingdom; ^{2}University of Edinburgh, United Kingdom; ^{3}Technical University of Munich (TUM), GE Healthcare Current popular methods for Magnetic Resonance Fingerprint (MRF) recovery are bottlenecked by the heavy storage and computation requirements of a dictionarymatching step in multiparametric quantitative MRI applications. We study a deep learning approach to address this issue and to approximate the (temporal) Bloch response manifold projection. Fed with noniterated backprojected images, the network alone is unable to fully resolve spatiallycorrelated 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 spatiotemporal regularities of the MRF timeseries.
A RateDistortion Framework for Explaining Deep Neural Network Decisions Technische Universität Berlin, Germany We propose a ratedistortion 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.
Alternating Minimization for MaxAffine Regression University of California, Berkeley, United States of America Maxaffine 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 highdimensional setting and focus on estimating the coefficients of the affine functions. We analyze an alternating minimization algorithm for the nonconvex 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.
Deep PostProcessing for Sparse Image Deconvolution ^{1}Heriot Watt University, United Kingdom; ^{2}Ecole Polytechnique Fédérale de Lausanne; ^{3}CentraleSupélec, Université Paris Saclay, Inria Variationalbased methods are the stateoftheart 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 twostep 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 stateoftheart algorithms in a fraction of the time.
Global optimization of L0normbased sparse approximation criteria with a branchandbound algorithm ^{1}LS2N, Ecole Centrale de Nantes, Nantes, France; ^{2}LabSTICC, ENSTA Bretagne, Brest, France We propose a branchandbound algorithm for the global optimization of problems mixing leastsquares 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 stateoftheart 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.
Learning beamforming in ultrasound imaging ^{1}Technion, Israel; ^{2}University of Waterloo, Canada 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 learningbased design of the transmitted beam patterns simultaneously with learning an image reconstruction pipeline.
Local Linear Convergence of Variance Reduced Stochastic Gradient Methods for Low Complexity Regularization ^{1}University of Bath, United Kingdom; ^{2}University of Cambridge, United Kingdom; ^{3}University of Cambridge, United Kingdom We present a local convergence analysis for proximal vari ance reduced stochastic gradient methods: SAGA [4] and ProxSVRG [6]. Under the assumption that the nonsmooth 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.
On the existence of stable and accurate neural networks for image reconstruction University of Cambridge, United Kingdom 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 stateoftheart methods for these problems. Thus, approximation theoretical results nonconstructively 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.
A Novel Smoothed Norm Ratio for Sparse Signal Restoration: Application to Mass Spectrometry ^{1}Aix Marseille Univ., CNRS, Centrale Marseille, I2M, Marseille, France.; ^{2}CVN, CentraleSupélec, INRIA Saclay and Univ. Paris Saclay.; ^{3}IFP Energies nouvelles, 1 et 4 avenue de BoisPréau, 92852 RueilMalmaison Cedex We propose a new smoothed "lp Overlq" norm ratio for sparse signal reconstruction. A trustregion Variable Metric ForwardBackward is proposed to solve the resulting nonconvex minimization problem. Numerical experiments in the context of mass spectrometry (MS) data processing illustrate the benefits of the novel penalty.
Reweighted l1 minimization for audio inpainting Brno University of Technology, Czech Republic 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.
Scanning Probe Microscopy with Continuous Line Probe Columbia University, United States of America 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 endtoend demonstration.
Tensorstructured Dictionaries for Hyperspectral Imaging Univ Rennes, Inria, CNRS, IRISA 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, HOSuKro, can be used to obtain more compact and readilyapplicable 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.
Advances in the recovery of binary sparse signals Politecnico di Torino, Italy 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 nonconvex polynomial formulation of the problem. Moreover, we propose novel theoretical results. Then, we show numerical results that highlight the enhancement obtained through the nonconvex approach with respect to the stateoftheart methods.
An algorithm with recovery guarantees for Expander Dictionary Learning ^{1}University of Oxford, United Kingdom; ^{2}The Alan Turing Institute 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 nonzeros 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.
Anomaly Detection in Wind Turbine Drivetrain Bearings using Sparse Coding with Dictionary Learning Luleå University of Technology, Sweden 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.
Compressed Sensing of Image Sequences via Multiple Total Variation Academia Sinica, Taiwan 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 ADMMMTV, we derive the closedform solutions of all subproblems to ease implementation. ADMMMTV 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.
Image Recovery by Generative Models and BackProjections ^{1}Tel Aviv University, Israel; ^{2}Tel Aviv University, Israel In recent years, there is a significant improvement in the samples produced by generative models such as variational autoencoders 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 pretrained 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 superresolution and compressed sensing.
Parallel Cut Pursuit For Minimization of the Graph TotalVariation ^{1}INSA Centre ValdeLoire, Université de Tours, LIFAT, France; ^{2}Université ParisEst, LASTIG, MATIS, IGN, ENSG, France We present a parallel version of the cutpursuit 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 graphcut 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 graphcuts based optimizers with the versatility and ease of parallelization of more traditional proximal splitting methods.
Precise Recovery in TwoDimensional Blind SuperResolution via Convex Optimization Imperial College London, United Kingdom This work proposes a new general mathematical framework for blind twodimensional superresolution 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 twodimensional shifts, the attenuation factors, and the unknown waveforms can all be recovered precisely and with high probability via solving a convex atomic norm problem.
Reconstruction of FRI Signals using Deep Neural Networks Imperial College London, United Kingdom Finite Rate of Innovation (FRI) theory considers sampling and reconstruction of classes of nonbandlimited 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érRao bound yet break down at a certain SignaltoNoise Ratio (SNR) due to the socalled 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.
Sparse BSS with spectral variabilities CEA, France 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 realworld 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 StateoftheArt algorithms.
Jointly sparse recovery via manifold optimization Oak Ridge National Laboratory, United States of America 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 noncompact Steifel manifold.
ShortandSparse Deconvolution  A Geometric Approach ^{1}Department of Electrical Engineering and Data Science Institute, Columbia University; ^{2}Center for Data Science, New York University; ^{3}Center for Neurocience, Columbia University; ^{4}Department of Computer Science, Cornell University; ^{5}Department of Applied Physics and Applied Mathematics, Columbia University Shortandsparse 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 illconditioning of real SaSD problems. Experiments demonstrate both the performance and generality of the proposed method.
Separability/identifiability properties of lowrank matrix factorization methods for bilinear mixtures of source signals University of Toulouse, France We here first analyze the solutions of lowrank 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 nonnegative 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.
An IRLS Approach for LowRank Matrix Factorization National Observatory of Athens, Greece Iterative reweighted methods for sparse recovery and lowrank 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 lowrank matrix factorization for encoding lowrankness 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 lowrank 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.
 
2:30pm  3:30pm  Plenary 6: Yuejie Chi (Carnegie Mellon University) Geometry and Regularization in Nonconvex LowRank Estimation  
Amphi B00  
3:30pm  4:10pm  Oral session 10 (2 talks)  
Amphi B00  

Phaseless PCA: LowRank Matrix Recovery from Columnwise Phaseless Measurements Iowa State University, United States of America Recovering a lowrank 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, AltMinPhaPCA, over existing work is demonstrated via simulations and realdata experiments. Under assumption of denseness of right singular vectors, our guarantee shows that, in the regime of small ranks, r, the sample complexity of AltMinPhaPCA is much smaller than what standard phase retrieval methods need; and it is only r^3 times the orderoptimal complexity for lowrank matrix recovery.
The Analysis of Spectral Initialization for Phase Retrieval with Random Orthogonal Matrices Columbia University, United States of America Phase Retrieval aims to recover a signal from its phaseless measurements. Some of the successful methods for solving this problem use a nonconvex optimization in which having a good initialization is crucial. The spectral method is one of the wellknown methods for such initialization. Here, we study the spectral method when the measurements matrix is partial Orthonormal. We have observed phasetransition 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.
 
4:10pm  4:40pm  Coffee Break  
C101  C103  
4:40pm  6:00pm  Special Talk : Michael Jordan (UC Berkeley) Machine Learning: Dynamical, Statistical and Economic Perspectives  
Amphi B00  
8:00pm  11:00pm  SPARS Banquet  
Hôtel Dieu 
Date: Thursday, 04/Jul/2019  
9:00am  10:00am  Plenary 7: Emilie Chouzenoux (University ParisEst) Proximal approaches for matrix optimization problems  
Amphi B00  
10:00am  10:40am  Oral session 11 (2 talks)  
Amphi B00  

The fastest L1,oo prox in the west ^{1}The Johns Hopkins University, United States of America; ^{2}University of Illinois at Urbana Champaign, United States of America We analyze the proximity operator of the mixed L1,oo matrix norm. We provide a simple expression for its computation that generalizes the wellknown softthresholding 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.
Nonlinear matrix recovery ^{1}University of Oxford, United Kingdom; ^{2}EPFL, Lausanne; ^{3}University of Chicago We investigate the recovery of a partially observed highrank 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 nonconvex 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.
 
10:40am  11:10am  Coffee Break  
C101  C103  
11:10am  12:10pm  Oral session 12 (3 talks)  
Amphi B00  

A Spectral Method for Estimating LowRank Subspaces from Nonlinear Measurements Harvard University, United States of America We study a simple spectral method for estimating a lowrank 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 twolayer 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.
Iterative Hard Thresholding for LowRank Recovery from RankOne Projections Texas A&M University, United States of America A novel algorithm for the recovery of lowrank matrices acquired via compressive linear measurements is proposed and analyzed. The algorithm, a variation on the iterative hard thresholding algorithm for lowrank recovery, is designed to succeed in situations where the standard rankrestricted isometry property fails, e.g. in case of subgaussian rankone measurements. The algorithm is stable, robust, and performs well empirically.
Highdimensional change point localization from noisy linear projections ^{1}Department of Statistics,University of Chicago; ^{2}Department of Statistics and Data Science, Carnegie Mellon University; ^{3}Department of Computer Science and Statistics, University of Chicago 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 stateofart methods.
 
12:10pm  2:30pm  Lunch + Poster session 4  
C101  C103  

Structured Signal Recovery from Quadratic Measurements ^{1}University of Electronic Science and Technology of China; ^{2}University of Electronic Science and Technology of China; ^{3}Dalian University of Technology In many applications, we face to consider rank minimization problem from quadratic measurements. Motivated by this fact, we introduce three gradientlike 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 gradientlike approaches in terms of both sample complexity and computational complexity.
The Sliding FrankWolfe Algorithm for the BLASSO ^{1}EPFL, BIG; ^{2}INRIA Paris, MOKAPLAN; ^{3}CNRS, ENS; ^{4}CNRS, IRIT This paper showcases the Sliding FrankWolfe (SFW), which is a novel optimization algorithm to solve the BLASSO sparse spikes superresolution problem. The BLASSO is a continuous (i.e. offthegrid or gridless) counterpart to the wellknown $\ell^1$ sparse regularisation method (also known as LASSO or Basis Pursuit). Our algorithm is a variation on the classical FrankWolfe (also known as conditional gradient) which follows a recent trend of interleaving convex optimization updates (corresponding to adding new spikes) with nonconvex optimization steps (corresponding to moving the spikes). We prove theoretically that this algorithm terminates in a finite number of steps under a mild nondegeneracy hypothesis.
Tissue Reflectivity Function Restoration from Fundamental and Harmonic Ultrasound Images ^{1}University of Toulouse, INPENSEEIHT, IRIT, CNRS UMR 5505; ^{2}University of Toulouse, Université Paul Sabatier,IRIT, CNRS UMR 5505 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.
A Fully Convolutional Network for MR Fingerprinting ^{1}The University of Edinburgh, United Kingdom; ^{2}University of Bath, United Kingdom; ^{3}Technical University of Munich, Germany; ^{4}GE Healthcare, Germany 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 (MRFFCNN), 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.
Efficient Approximation of Solutions of Parametric PDEs by ReLU Neural Networks ^{1}Technische Universität Berlin, Germany; ^{2}University of Oxford, United Kingdom 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 lowdimensionality 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 parameterdependent 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.
An Inexact Augmented Lagrangian Framework for NonConvex Optimization with Nonlinear Constraints EPFL, Switzerland We investigate the convergence rate analysis of the classical inexact augmented Lagrangian method (iALM) for nonlinearconstrained nonconvex problems subject to a geometric condition involving the nonlinear operator. We show that when coupled with a firstorder method, iALM finds firstorder stationary points in $\tilde{\mathcal{O}}(1/\epsilon^3)$ calls to the firstorder oracle. In addition, when coupled with a secondorder method, iALM finds secondorder stationary points in $\tilde{\mathcal{O}}(1/\epsilon^5)$ calls to the secondorder oracle. We provide numerical evidence on largescale signal processing and machine learning problems, modeled typically via semidefinite relaxations, for which we verify the geometric condition.
Ergodic bilevel optimization TU Braunschweig, Germany 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 ChambollePock 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.
Learning lowdimensional surfaces and functions University of Iowa, United States of America The learning of models for multidimensional 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, realworld 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 zeroset 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.
Unsupervised parameter selection in variational regularization ^{1}Simula Research Laboratory, Norway; ^{2}Universita di Genova, DIMA, Italy 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 nonlinear 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.
Exact recovery analysis of nonnegative orthogonal matching pursuit ^{1}CRAN, Universite de Lorraine, France; ^{2}L2S, CentraleSupelec, France; ^{3}LS2N, CNRS, France It is wellknown that Orthogonal Matching Pursuit (OMP) recovers the exact support of Ksparse signals under the condition mu<1/(2K1) where mu denotes the mutual coherence of the dictionary. In this communication, we show that under the same condition and if the unknown Ksparse signal is nonnegative, the weights of the atoms selected by OMP are nonnegative at any of the first K iterations. Therefore, the generalized version of OMP to the nonnegative setting (NNOMP) identifies with OMP, which allows us to establish an exact recovery analysis of NNOMP under the mutual coherence condition.
Manifold Alignment by Feature Correspondence ^{1}Yale University, United States of America; ^{2}Université de Montréal, Canada 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.
A Deep Analysis Dictionary Model Imperial College London, United Kingdom In this paper, we propose a novel method to learn a pair of analysis dictionary and softthreshold which is used to construct the deep dictionary model for regression tasks. The learned analysis dictionaries together with the corresponding softthresholds 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.
A recipe for inexact certificates in $\ell_1$analysis interpolation EPFL, Switzerland 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 rederived, 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.
Distributed FirstOrder Optimization with Tamed Communications ^{1}University Grenoble Alpes; ^{2}CNRS Many machine learning and signal processing applications involve highdimensional nonsmooth optimization problems. The nonsmoothness is essential as it brings a lowdimensional 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.
Exact recovery of partially sparse vectors ^{1}TU Braunschweig, Germany; ^{2}RWTH Aachen University, Germany 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.
Flexible sparse regularization with general nonconvex penalties ^{1}TU Braunschweig, Germany; ^{2}AlpenAdria Universität Klagenfurt, Austria 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 nonconvex.
Hyperspectral Uncertainty Quantification by Optimization HeriotWatt University, United Kingdom 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 singlechannel UQ. Similarly, the Bayesian hypothesis test is formulated as a convex minimization problem and solved using a primaldual 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 radiointerferometric (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.
Labelconsistent sparse autoencoders ^{1}IRIT, Université Paul Sabatier, CNRS; ^{2}INESCID Autoencoders (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 labelconsistent K SVD in sparse coding context, we propose a novel supervised version of AEs that integrates class information within the encoded representations.
Natural Variation Transfer using Learned Manifold Operators ^{1}Georgia Institute of Technology, United States of America; ^{2}Yahoo! Research, United State of America The variations in many types of data are constrained by natural physical laws and identitypreserving variations are often shared between several classes. In many settings, the withinclass variation in a highdimensional dataset can be modeled as being on a lowdimensional 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 fewshot learning and realistic data generation to demonstrate state of the art manifold learning performance in transfer settings.
NMFbased sparse unmixing of complex mixtures. ^{1}Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille, France.; ^{2}Aix Marseille Univ, CNRS, Centrale Marseille, iSM2, Marseille, France. 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.
Performance of Compressive Sensing for HadamardHaar Systems ^{1}ISPGroup, ICTEAM/ELEN, UCLouvain, Belgium; ^{2}IT, IST, Universidade de Lisboa, Portugal 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 samplecomplexity bound for HadamardHaar systems; a seemingly missing result in the related literature. The power of this approach is demonstrated on several simulations.
Robust SuperResolution via Deep Learning and TV Priors HeriotWatt University, United Kingdom 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 sparsitybased 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 sparsitybased methods. Experiments show that it significantly outperforms stateoftheart SR algorithms in the quality of reconstruction.
Sampling over spiraling curves ^{1}Université de Bordeaux, France; ^{2}Faculty of Mathematitcs, University of Vienna; ^{3}Acoustics Research Institute, Austrian Academy of Science We present our recent work on sampling along spirallike 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.
Stochastic Signal Processing in Phase Space ^{1}Technische Universität Berlin, Germany; ^{2}Tel Aviv University, Israel 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 phasevocoder method (in audio signal processing), based on an enhanced timefrequency space.
Tight Framelets and Fast Framelet Filter Bank Transforms on Manifolds ^{1}The University of New South Wales, Sydney, Australia; ^{2}City University of Hong Kong, Hong Kong S.A.R. (China) In this talk, on a compact Riemmannian manifold M, we discuss construction of tight frames in L2(M) in both the continuous and semidiscrete settings. We show that polynomialexact quadrature rules on M give a simple way of constructing semidiscrete 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 2sphere S2 with two high passes (b1 and b2) and gives numerical examples for the FMT algorithms on S2.
On variable splitting for Markov chain Monte Carlo ^{1}University of Toulouse  INP/ENSEEIHT (IRIT), France; ^{2}Ecole Centrale de Lille (CRIStAL), France Variable splitting is an old but widely used technique which aims at dividing an initial complicated optimization problem into simpler subproblems. 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.
Fast Doublecoupled Nonnegative Tensor Decomposition ^{1}Dalian University of Technology, China, People's Republic of; ^{2}University of Jyväskylä, Finland 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 doublecoupled nonnegative Canonical Polyadic decomposition (FDCNCPD) algorithm. It enables the simultaneous extraction of common components and individual components. In addition, its timeconsumption is greatly reduced without compromising the decomposition quality when handling largescale problems. Simulation results demonstrate the superior performance of the proposed algorithm.
Structured Discrete Shape Approximation RWTH Aachen University, Germany We consider approximating a 2D shape contour using discrete graphassembly 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 NPhard and then devise an algorithmic framework that combines shape sampling with exact L0/cardinalityminimization 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.
Antisparse Blind Source Separation ^{1}University of Campinas, Brazil; ^{2}Federal University of ABC 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.
 
2:30pm  3:30pm  Plenary 8: Monika Dörfler (University of Vienna) Preprocessing data for deep learning? The balance between discriminability and invariance  
Amphi B00  
3:30pm  4:30pm  Oral session 13 (3 talks)  
Amphi B00  

A good reason for using OMP: average case results University of Innsbruck, Austria 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.
Universal Sparse Representation Technion, Israel 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 closedform expressions that allow to easily deduce the asymptotic behavior in high dimensions.
Uniform kstep recovery with CMF dictionaries ^{1}Univ Rennes, Inria, CNRS, IRISA; ^{2}L2S, CentraleSupélecCNRSUniversité ParisSaclay 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 kstep recovery is possible.
 
4:30pm  4:40pm  Closing remarks  
Amphi B00 
Contact and Legal Notice · Contact Address: Privacy Statement · Conference: SPARS 2019 
Conference Software  ConfTool Pro 2.6.130+TC+CC © 2001  2020 by Dr. H. Weinreich, Hamburg, Germany 