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:30amRegistration + coffee
Hall C 
9:30am - 9:40amIntroduction
Amphi B00 
9:40am - 10:40amPlenary 1: Lenka Zdeborova(CNRS)

Are generative models the new sparsity?
Amphi B00 
10:40am - 11:10amCoffee Break
C101 - C103 
11:10am - 12:10pmOral session 1 (3 talks)
Amphi B00 

Sparsity of solutions for variational inverse problems with finite-dimensional data

Kristian BREDIES, Marcello CARIONI

Karl-Franzens-Universitä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 so-called 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 Off-the-grid

Clarice POON1, Nicolas KERIVEN2, Gabriel PEYRE2

1University of Bath, United Kingdom; 2Ecole 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 non-translation invariant operators, such as sampling of the Laplace transform. Our main theorem establishes stable recovery of a sparse measure, without the random signs condition, when the number of random measurements scales linearly with sparsity up to log factor.


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 nuclear-norms, but they suffer from a shrinking bias that degrades the solution

quality in the presence of noise.

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

12:10pm - 2:30pmLunch + Poster session 1
C101 - C103 

Nonsparsity influence on reconstruction time-frequency signals with sparsity constraint


Grenoble INP, University of Grenoble Alpes, France


On instabilities of deep learning in image reconstruction

Vegard ANTUN1, Francesco RENNA2, Clarice POON3, Ben ADCOCK4, Anders HANSEN5,1

1University of Oslo, Norway; 2Faculdade de Ciências da Universidade do Porto, Portugal; 3University of Bath, UK; 4Simon Fraser University, Canada; 5University of Cambridge, UK


Density evolution of Orthogonal Matching Pursuit

Claude PETIT1, Aline ROUMY2, Giulio COLUCCIA3, Enrico MAGLI3

1Insee, France; 2Inria, France; 3Politecnico di Torino, Italy


Negative Binomial Matrix Factorization for Recommender Systems


IRIT, Université de Toulouse, CNRS


Closed-form Marginal Likelihood in Gamma-Poisson Matrix Factorization


1IRIT, Université de Toulouse, CNRS, France; 2Criteo AI Lab


Bandlimited Signal Reconstruction from Nonuniform Samples


Georgia Institute of Technology, United States of America


A Faceted Prior for Scalable Wideband Computational Imaging

Abdullah ABDULAZIZ1, Pierre-Antoine THOUVENIN1, Ming JIANG2, Yves WIAUX1

1Heriot-Watt University, United Kingdom; 2École Polytechnique Fédérale de Lausanne, Switzerland


A scalable estimator of space varying blurs - application in super-resolution

Valentin DEBARNOT1, Thomas MANGEAT2, Pierre WEISS1

1ITAV, CNRS, France; 2CBI, CNRS, France


Deep Recurrent Brain Source Imaging

Ali HASHEMI1,2,3, Hector Andrade LOARCA1, Stefan HAUFE3, Klaus-Robert MÜLLER2,4,5,6,7, Gitta KUTYNIOK1,2

1Institut für Mathematik, Technische Universität Berlin, Germany; 2Electrical Engineering and Computer Science, Technische Universität Berlin, Germany; 3Berlin Center for Advanced Neuroimaging (BCAN), Charite Universitätsmedizin Berlin, Germany; 4Berlin Big Data Center, 10587 Berlin, Germany.; 5Berliner Zentrum für Maschinelles Lernen, 10587 Berlin, Germany.; 6Department of Brain and Cognitive Engineering, Korea University, Seoul 02841, South Korea,; 7Max Planck Institute for Informatics, Stuhlsatzenhausweg, Saarbrucken, Germany.


Exploiting regularity in sparse Generalized Linear Models

Mathurin MASSIAS1, Samuel VAITER2, Alexandre GRAMFORT1, Joseph SALMON3

1INRIA, Université Paris-Saclay, Palaiseau, France; 2CNRS & Institut de Mathématiques de Bourgogne, Dijon, France; 3IMAG, Univ Montpellier, CNRS, Montpellier, France


FeTa: Fast and Efficient Pruning of Deep Neural Networks

Konstantinos PITAS1, Mike DAVIES2, Pierre VANDERGHEYSNT1

1EPFl, Switzerland; 2University of Edinburgh, UK


Iterative low-rank and rotating sparsity promotion for circumstellar disks imaging

Benoît PAIRET1, Faustine CANTALLOUBE2, Laurent JACQUES1

1ISPGroup, ICTEAM, UCLouvain, Belgium; 2Max Planck Institute for Astronomy, Germany


On the Local Minimizers of the CEL0 Relaxation

Emmanuel SOUBIES1, Laure BLANC-FÉRAUD2, Gilles AUBERT3

1IRIT, University of Toulouse, CNRS, France; 2University Côte d'Azur, CNRS, INRIA, i3S, France; 3University Côte d'Azur, INS, LJAD, France


The Adaptive Dictionary Learning Toolbox

Cristian RUSU1, Karin SCHNASS2

1IIT, Italy; 2University of Innsbruck, Austria


Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization

Cong MA1, Yuling YAN1, Yuejie CHI2, Jianqing FAN1, Yuxin CHEN1

1Princeton University, United States of America; 2Carnegie Mellon University, United States of America


An L0 solution to sparse approximation problems with continuous dictionaries


1IRAP, Université de Toulouse/CNRS/CNES, France; 2LS2N, École Centrale de Nantes/CNRS, France


Distributed sparse BSS for large-scale datasets

Tobias Ignacio LIAUDAT, Jérôme BOBIN, Christophe KERVAZO

CEA, France


Learning to unmix from Poisson measurements with application to γ-spectroscopy

Jerome BOBIN1, Jiaxin XU2, Anne DE VISMES2, Christophe BOBIN3



Linear convergence and support recovery for non-convex multi-penalty regularisation

Zeljko KERETA1, Johannes MALY2, Valeriya NAUMOVA1

1Simula Research Laboratory, Norway; 2RWTH Aachen University


Magnetic Resonance and Ultrasound Image Fusion Using a PALM Algorithm

Oumaima EL MANSOURI1, Adrian BASARB1, Fabien VIDAL1,2, Denis KAOUME1, Jean-yves TOURNERET1

1University of Toulouse, IRIT, CNRS, INP-ENSEEIHT, Université Paul Sabatier Toulouse 3, France; 2CHU Toulouse, Obstetrics Gynecology Department, Paule de viguier Hospital Toulouse F-31059, France

Abstract164-EL MANSOURI-164.pdf

Spatially-filtered temporal dictionary learning for calciumimaging analysis


1Yale University, United States of America; 2Technion, Israel Institute of Technology, Israel; 3Princeton University, United States of America


Tensor-Free Algorithms for Convex Liftings of Bilinear Inverse Problems with Applications to Masked Phase Retrieval

Robert BEINERT, Kristian BREDIES

University of Graz, Austria


A New Perspective on L1-Analysis Recovery

Martin GENZEL, Gitta KUTYNIOK, Maximilian MÄRZ

Technische Universität Berlin, Germany


Compressed Diffusion


1Yale University, United States of America; 2Utah State University, United States of America; 3Université de Montréal, Canada


Towards Theoretically-Founded Learning-Based Denoising

Wenda ZHOU1, Shirin JALALI2

1Columbia University, United States of America; 2Nokia Bell Labs


Graph Based Trajectory Mining

Francesco GRASSI, Nauman SHAHID

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

Ali SHAFAHI1, Ronny HUANG1, Christoph STUDER2, Soheil FEIZI1, Tom GOLDSTEIN1

1University of Maryland; 2Cornell University


Linear Simplex Support Vector Regression


1Institut Mathématiques de Bourgogne, France; 2CNRS, France

2:30pm - 3:30pmPlenary 2: Pier Luigi Dragotti (Imperial College London)

Timing is everything: Sparse sampling based on time-encoding machines
Amphi B00 
3:30pm - 4:10pmOral session 2 (2 talks)
Amphi B00 

Cluster-based Optimal Transport Alignment

John LEE, Eva DYER, Christopher J. ROZELL

Georgia Institute of Technology, United States of America

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


Optimal Transport of Measures in Frequency Domain

Laurent CONDAT

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:40pmCoffee Break
C101 - C103 
4:40pm - 5:40pmOral session 3 (3 talks)
Amphi B00 

On the non-convex sparse spike estimation problem: explicit basins of attractions of global minimizers

Yann TRAONMILIN1,3, Jean-François AUJOL2,3

1CNRS; 2Université de Bordeaux; 3Institut de mathématiques de Bordeaux

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


A Unified Framework for the Convergence Analysis of Optimization Algorithms via Sum-of-Squares

Sandra S. Y. TAN, Antonios VARVITSIOTIS, Vincent Y. F. TAN

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 ad-hoc arguments and case-by-case analysis. In this paper, we introduce a novel optimization framework for bounding the convergence rates of various important optimization algorithms by means of sum-of-squares certificates. Our approach allows us to recover known convergence bounds for three widely-used first-order algorithms in a unified manner and puts forward a promising framework for unifying convergence analyses of optimization algorithms.


Eventual linear convergence rate of an exchange algorithm for superresolution.

Axel FLINTH1, Fréderic DE GOURNAY1, Pierre WEISS2,3

1Université de Toulouse, France; 2CNRS; 3Institut 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 Frank-Wolfe algorithm, as well as from semi-infinite programming. For smooth regularity terms, we prove an eventual linear convergence rate guarantee.

7:30pm - 9:30pmWelcoming reception
Le Moaï restaurant 
Date: Tuesday, 02/Jul/2019
9:00am - 10:00amPlenary 3: Mark Davenport (Georgia Institute of Technology)

Subspaces and sparsity on the continuum
Amphi B00 
10:00am - 10:40amOral session 4 (2 talks)
Amphi B00 

Matrix “Desketching”: Unlifted but Convex

Sohail BAHMANI1, Kiryung LEE2

1Georgia Institute of Technology, United States of America; 2Ohio State University, United States of America


Matrix rigidity and the ill-posedness of Robust PCA and matrix completion

Jared TANNER1,3, Andrew THOMPSON2, Simon VARY1

1University of Oxford, United Kingdom; 2National Physical Laboratory, United Kingdom; 3The Alan Turing Institute, United Kingdom

10:40am - 11:10amCoffee Break
C101 - C103 
11:10am - 12:10pmOral session 5 (3 talks)
Amphi B00 

Universal sparsity of deep ReLU networks


1University of Vienna, Austria; 2ETH 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 cartoon-like functions) have been established in a variety of relevant cases. We develop a notion of 'sparsity w.r.t. ReLU networks', which leads to the intriguing conclusion that any function class is (asymptotically) at least as sparse w.r.t. ReLU network as it is in most conventional representation system (based on translation, dilation, and modulation of some generator functions).


Error bounds for approximations with deep ReLU neural networks in Sobolev norms


1Technische Universität Berlin, Germany; 2University 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

Bin DAI1, David WIPF2

1Tsinghua University, China, People's Republic of; 2Microsoft 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 information-theoretic variational bound on the underlying distribution. While quite effective in numerous application domains, important aspects of the VAE objective are obscured by non-convexity and intractable integrals. In this regard, we attempt to better quantify VAE properties by analyzing a representative special case. In doing so, we demonstrate that the VAE can be viewed as the natural evolution of robust PCA models, capable of learning nonlinear manifolds of unknown dimension obscured by gross corruptions.

12:10pm - 2:30pmLunch + Poster session 2
C101 - C103 

Improving Graph Trend Filtering with Non-Convex Penalties

Rohan VARMA1, Harlin LEE1, Yuejie CHI1, Jelena KOVAČEVIĆ2

1Dept. of Electrical and Computer Engineering, Carnegie Mellon University, United States of America; 2Tandon 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 non-convex regularizers that exhibit superior recovery performance over existing convex ones. We present theoretical results in the form of asymptotic error rates for both generic and specialized graph models. We further present an ADMM-based algorithm to solve the proposed optimization problem and analyze its convergence. Numerical performance of the proposed framework with non-convex regularizers on both synthetic and real-world data for denoising, support recovery, and semi-supervised classification.


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


Tensor and Coupled Decompositions in Block Terms: Uniqueness and Irreducibility

Dana LAHAT1,2,3, Christian JUTTEN4,1,5,6

1CNRS, France; 2IRIT, France; 3Université de Toulouse, France; 4Univ. Grenoble Alpes, France; 5Grenoble INP, France; 6GIPSA-lab, France

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

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


Why deep learning methods for inverse problems typically become unstable

Nina Maria GOTTSCHLING, Anders Christian HANSEN

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 First-Order Methods via Linear Prediction

Clarice POON1, Jingwei LIANG2

1University of Bath, United Kingdom; 2University of Cambridge, United Kingdom

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


Active embedding search via noisy paired comparisons

Gregory Humberto CANAL, Andrew Kenneth MASSIMINO, Mark Andrew DAVENPORT, Christopher John ROZELL

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 low-dimensional space with distances that reflect user and item similarities. Since such observations can be extremely costly and noisy, we aim to actively choose pairs that are most informative given the results of previous comparisons. We provide new theoretical insights into greedy information maximization and develop two novel strategies that provably approximate information maximization. We use simulated responses from a real-world dataset to validate our strategies over state-of-the-art methods.


Benchmarking proximal methods acceleration enhancements for CS-acquired MR image analysis reconstruction

Zaccharie RAMZI1,2,3, Philippe CIUCIU1,2, Jean-Luc STARCK3

1CEA - Neurospin, Gif-sur-Yvette, France; 2INRIA - Parietal, Gif-sur-Yvette, France; 3CEA - Cosmostat, Gif-sur-Yvette, France

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

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


Compressed sensing and the synthesis formulation

Claire BOYER1, Jonas KAHN2, Maximilian MARZ3, Pierre WEISS2

1Sorbonne Université; 2CNRS, Université de Toulouse; 3Technische 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 so-called synthesis formulation in the framework of random Gaussian measurements.

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


Compressive k-Means with Differential Privacy

Vincent SCHELLEKENS1, Antoine CHATALIC2, Florimond HOUSSIAU3, Yves-Alexandre DE MONTJOYE3, Laurent JACQUES1, Rémi GRIBONVAL2

1ICTEAM/ELEN, UCLouvain; 2Univ Rennes, Inria, CNRS, IRISA; 3Imperial 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 privacy-utility trade-off for the k-means clustering problem.


Compressive Phase Retrieval of Structured Signal


1Columbia University, United States of America; 2Nokia-Bell labs

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

retrieval recovery method, is proposed and its recovery performance is

characterized. COPER employs a compression code designed for a class

of structured signals to recover them from their undersampled

phaseless measurements. Using compression codes that are information

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

number of measurements that matches the corresponding information

theoretic lower bounds. Furthermore, to approximate the solution of

COPER, an efficient polynomial-time method based on projective

gradient descent is proposed and its convergence performance is



Fusion of hyperspectral and multispectral infrared astronomical images

Claire GUILLOTEAU1,2, Thomas OBERLIN1, Olivier BERNE2, Nicolas DOBIGEON1

1IRIT-ENSEEIHT, France; 2IRAP, 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

Davis GILTON1, Greg ONGIE2, Rebecca WILLETT2

1University of Wisconsin-Madison; 2University of Chicago

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


Local Convolutive Independent Vector Analysis for Reverberant Blind Source Separation

Fangchen FENG1, Matthieu KOWALSKI2

1APC, Univ. Paris Diderot, CNRS/IN2P3 CEA/Irfu, Obs. de Paris, Sorbonne Paris Cité; 2Laboratoire des signaux et systèmes, Univ Paris-Sud, 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 Windowed-Group-Lasso. Being able to avoid the permutation alignment and to take advantage of the cross-band information during the separation, the proposed approach outperforms the existing methods through numerical evaluations.


Non-uniform recovery guarantees for binary measurements

Laura THESING, Anders Christian HANSEN

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 non-linear reconstruction.


Nullspace Conditions for Block-Sparse Semidefinite Systems

Janin HEUER1, Frederic MATTER2, Marc E. PFETSCH2, Thorsten THEOBALD3

1TU Braunschweig, Germany; 2TU Darmstadt Germany; 3Goethe-Universität Frankfurt am Main, Germany

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


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 semi-orthogonal

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

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

simultaneously and maintains the required orthogonality conditions by

means of the polar decomposition. The convergence behavior of our

algorithm is analyzed for both objective function and iterates themselves

and is illustrated by numerical experiments.


On the Weighting for Convolutional Sparse Coding

Diego CARRERA1, Alessandro FOI2, Giacomo BORACCHI3, Brendt WOHLBERG4

1STMicroelectronics, Italy; 2Tampere University, Finland; 3Politecnico di Milano, Italy; 4Los Alamos National Laboratory, USA

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


One-Bit Compressed Sensing by Convex Relaxation of the Hamming Distance

Hans Christian JUNG1, Johannes MALY1, Lars PALZER2, Alexander STOLLENWERK1

1RWTH Aachen University, Germany; 2Technical University of Munich, Germany

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


Outlier Detection Using Generative Models with Theoretical Performance Guarantees

Jirong YI1, Duc Anh LE1, Tianming WANG2, Xiaodong WU1, Weiyu XU1

1Department of Electrical and Computer Engineering, University of Iowa, United States of America; 2Institute 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 generative-model-based $\ell_1$ minimization for signal recovery. We establish the recovery guarantees and give an upper bound on the number of outliers allowed for recovery. Our results are applicable to both the linear and the nonlinear generators. We conduct extensive experiments using commonly used generative models and the experimental results show that the signals can be successfully reconstructed under outliers using our approaches. Our approach outperforms the traditional Lasso and $\ell_2$ minimization approach.


Reconstruction of partially sampled STEM-EELS images with atomic resolution

Etienne MONIER1, Thomas OBERLIN1, Nathalie BRUN2, Nicolas DOBIGEON1

1University of Toulouse, IRIT/INP-ENSEEIHT, Toulouse; 2Laboratoire de Physique des Solides, CNRS UMR 8502, Univ. Paris-Sud, Univ. Paris-Saclay

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

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


Relaxed contractivity conditions for dictionary learning via Iterative Thresholding and K residual Means

Marie-Christine PALI1, Karin SCHNASS1, Alexander STEINICKE2

1University of Innsbruck, Austria; 2University of Leoben, Austria

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


Robust penalized inference for Gaussian Scale Mixtures

Karina ASHURBEKOVA1,2,3, Sophie ACHARD1,2,4, Florence FORBES1,3,4

1Univ. Grenoble Alpes, France; 2GIPSA-lab; 3INRIA; 4CNRS

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


Simultaneous Inference and Denoising of Student-t Mixtures from Noisy Observations


Instituto de Telecomunicações and Instituto Superior Técnico, University of Lisbon, Portugal

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


Sparse Dictionaries for Continuous-Domain Inverse Problems


EPFL, Switzerland

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


Fast Numerical Methods for Convex Problems with Optimal Transport Regularization

John LEE, Christopher J. ROZELL

Georgia Institute of Technology, United States of America

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


Learning Fast Magnetic Resonance Imaging


1Technion, Israel; 2University of Waterloo, Canada

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


Regularized Newton Sketch by Denoising Score Matching for Computed Tomography Reconstruction

Alessandro PERELLI, Martin S. ANDERSEN

Technical University of Denmark - DTU, Denmark

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


Sparse Nonnegative Tensor Decomposition for EEG Data

Deqing WANG1,2, Fengyu CONG1,2, Tapani RISTANIEMI2

1School of Biomedical Engineering, Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024, China; 2Faculty of Information Technology, University of Jyväskylä, Jyväskylä 40100, Finland

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


Adaptive mixed grey wolf optimizer: toolbox for illustration and comparative study

Julien MAROT

Institut Fresnel, Aix Marseille Universite, France

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

2:30pm - 3:30pmPlenary 4: Simon Thorpe (CNRS)

Ultra-Sparse Representations in Neural Networks : Biological Inspiration for Artificial Intelligence?
Amphi B00 
3:30pm - 4:10pmOral session 6 - Student Contest (2 talks)
Amphi B00 

Concomitant Lasso with Repetitions (CLaR): beyond averaging multiple realizations of heteroscedastic noise

Quentin BERTRAND1, Mathurin MASSIAS1, Alexandre GRAMFORT1, Joseph SALMON2

1INRIA Saclay, France; 2IMAG,Univ Montpellier, CNRS, Montpellier, France

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


A Fast Holistic Algorithm for Complete Dictionary Learning via L^4 Norm Maximization

Yuexiang ZHAI1,2, Zitong YANG1, Zhenyu LIAO2, John WRIGHT3, Yi MA1

1UC Berkeley; 2ByteDance Research Lab; 3Columbia 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:40pmCoffee Break
C101 - C103 
4:40pm - 5:40pmOral session 7 - Student Contest (3 talks)
Amphi B00 

Generalized Conditional Gradient with Augmented Lagrangian for Composite Optimization



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.


Low-rank matrix completion and denoising under Poisson noise


Georgia Institute of Technology, United States of America

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


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

Date: Wednesday, 03/Jul/2019
9:00am - 10:00amPlenary 5: Bhaskar Rao (UC San Diego)

Sparse Bayesian Learning: A Beamforming and Toeplitz Approximation Perspective
Amphi B00 
10:00am - 10:40amOral session 8 (2 talks)
Amphi B00 

Self-supervised learning of inverse problem solvers in medical imaging


1Technion, Israel; 2University 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 self-supervised learning based framework for inverse problems in medical imaging.


Block-Gaussian-Mixture 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 inter-band dependencies. Experiments suggest that the proposed method outperforms other state-of-the-art methods.

10:40am - 11:10amCoffee Break
C101 - C103 
11:10am - 12:10pmOral session 9 (3 talks)
Amphi B00 

Multiple-Kernel 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 continuous-domain hybrid search space. We adopt the generalized total-variation norm as a sparsity-promoting regularization term to make the problem well-posed. We prove that the solution of this problem admits a sparse kernel expansion with adaptive positions. We also show that the sparsity of the solution is upperbounded by the number of data points. This allows for an enlargement of the search space and ensures the well-posedness of the problem.


Sketched Clustering via Hybrid GAMP


1The Ohio State University, United States of America; 2Univ. 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 state-of-the-art sketched clustering algorithm “CL-OMPR” (in both computational and sample complexity) and more efficient than k-means++ when T is large.


SLOPE for Sparse Linear Regression: Exact Asymptotics and Optimal Sequence Designs

Hong HU, Yue M. LU

Harvard University

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

(This work has been accepted to ISIT 19)

12:10pm - 2:30pmLunch + Poster session 3
C101 - C103 

Sparse Group Model Selection

Bubacarr BAH1, Jannis KURTZ2, Oliver SCHAUDT3

1AIMS South Africa, & Stellenbosch University; 2RWTH Aachen University, Germany; 3Research and Development, ZF Group, Germany

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


Sparse Signal Reconstruction with a Sign Oracle

Arthur MARMIN1, Marc CASTELLA2, Jean-Christophe PESQUET1

1Center for Visual Computing, CentraleSupélec, INRIA, Université Paris-Saclay, France; 2SAMOVAR, Télécom SudParis, CNRS, Université Paris-Saclay, CNRS, France

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


Stacked Sparse Non-Linear Blind Source Separation

Christophe KERVAZO, Jérôme BOBIN

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 non-linear function. We propose to use a sequential decomposition of the data enabling its approximation by a linear-by-part function. Beyond separating the sources, the introduced StackedAMCA can further empirically learn in some settings an approximation of the inverse of the unknown non-linear mixing, enabling to reconstruct the sources despite a severely ill-posed problem. The quality of the method is demonstrated experimentally.


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 model-based approaches, namely the group-sparse model with some prior information in the form of weights. By combining both ideas, we are able to prove optimal convergence rate (within log factors) to the full solution map, even in high dimensional parametric spaces.


Deep learning for Magnetic Resonance Fingerprinting

Mohammad GOLBABAEE1, Dongdong CHEN2, Mike DAVIES2, Carolin M. PIRKL3, Marion MENZEL3, Pedro A. GOMEZ3

1University of Bath, United Kingdom; 2University of Edinburgh, United Kingdom; 3Technical 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 dictionary-matching step in multi-parametric quantitative MRI applications. We study a deep learning approach to address this issue and to approximate the (temporal) Bloch response manifold projection. Fed with non-iterated back-projected images, the network alone is unable to fully resolve spatially-correlated artefacts which appear in highly undersampling regimes. We propose an accelerated iterative reconstruction to minimize these artefacts before feeding into the network. This is done through a convex regularization that jointly promotes spatio-temporal regularities of the MRF time-series.


A Rate-Distortion Framework for Explaining Deep Neural Network Decisions


Technische Universität Berlin, Germany

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


Alternating Minimization for Max-Affine Regression


University of California, Berkeley, United States of America

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


Deep Post-Processing for Sparse Image Deconvolution

Matthieu TERRIS1, Abdullah ABDULLAZIZ1, Arwa DABBECH1, Ming JIANG2, Audrey REPETTI1, Jean-Christophe PESQUET3, Yves WIAUX1

1Heriot Watt University, United Kingdom; 2Ecole Polytechnique Fédérale de Lausanne; 3CentraleSupélec, Université Paris Saclay, Inria

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


Global optimization of L0-norm-based sparse approximation criteria with a branch-and-bound algorithm

Ramzi BEN MHENNI1, Sébastien BOURGUIGNON1, Jordan NININ2

1LS2N, Ecole Centrale de Nantes, Nantes, France; 2Lab-STICC, ENSTA Bretagne, Brest, France

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

Abstract219-BEN MHENNI-219.pdf

Learning beamforming in ultrasound imaging


1Technion, Israel; 2University 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 learning-based 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

Clarice POON1, Jingwei LIANG2, Carola-Bibiane SCHÖNLIEB3

1University of Bath, United Kingdom; 2University of Cambridge, United Kingdom; 3University of Cambridge, United Kingdom

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


On the existence of stable and accurate neural networks for image reconstruction

Matthew John COLBROOK, Vegard ANTUN, Anders Christian HANSEN

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 state-of-the-art methods for these problems. Thus, approximation theoretical results non-constructively imply the existence of stable and accurate neural networks. Hence the fundamental question: Can we explicitly construct/train stable and accurate neural networks for image reconstruction? We prove the answer is yes and construct such networks. Numerical examples of the competitive performance are also provided.


A Novel Smoothed Norm Ratio for Sparse Signal Restoration: Application to Mass Spectrometry

Afef CHERNI1, Emilie CHOUZENOUX2, Laurent DUVAL3, Jean-Christophe PESQUET2

1Aix Marseille Univ., CNRS, Centrale Marseille, I2M, Marseille, France.; 2CVN, CentraleSupélec, INRIA Saclay and Univ. Paris Saclay.; 3IFP Energies nouvelles, 1 et 4 avenue de Bois-Préau, 92852 Rueil-Malmaison Cedex

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


Reweighted l1 minimization for audio inpainting

Ondřej MOKRÝ, Pavel RAJMIC

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

Han-Wen KUO, Anna Elisabeth DORFI, Daniel ESPOSITO, John WRIGHT

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 end-to-end demonstration.


Tensor-structured 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, HO-SuKro, can be used to obtain more compact and readily-applicable dictionaries when the targeted data is a collection of multiway arrays. We introduce an alternating optimization learning algorithm and apply it to a hyperspectral image denoising task.


Advances in the recovery of binary sparse signals

Sophie M. FOSSON

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 non-convex polynomial formulation of the problem. Moreover, we propose novel theoretical results. Then, we show numerical results that highlight the enhancement obtained through the non-convex approach with respect to the state-of-the-art methods.


An algorithm with recovery guarantees for Expander Dictionary Learning

Michael James MURRAY1,2, Jared Tanner TANNER1,2

1University of Oxford, United Kingdom; 2The 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 non-zeros per column, while the latent representation is random, real, k sparse and dissociated. The algorithm presented leverages properties of expander graphs to efficiently recover both the dictionary and latent representation simultaneously.


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

Shih-Wei HU, Gang-Xuan LIN, Sung-Hsien HSIEH, Chun-Shien LU

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 ADMM-MTV, we derive the closed-form solutions of all subproblems to ease implementation.

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

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


Image Recovery by Generative Models and Back-Projections


1Tel Aviv University, Israel; 2Tel Aviv University, Israel

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


Parallel Cut Pursuit For Minimization of the Graph Total-Variation


1INSA Centre Val-de-Loire, Université de Tours, LIFAT, France; 2Université Paris-Est, LASTIG, MATIS, IGN, ENSG, France

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


Precise Recovery in Two-Dimensional Blind Super-Resolution via Convex Optimization

Mohamed Abdalla Elhag SULIMAN, Wei DAI

Imperial College London, United Kingdom

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


Reconstruction of FRI Signals using Deep Neural Networks

Vincent Chi Hang LEUNG, Jun-Jie HUANG, Pier Luigi DRAGOTTI

Imperial College London, United Kingdom

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


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 real-world data (remote sensing, astrophysics to cite only a few) and leading to estimation errors. To overcome this pitfall, we propose a method that fully accounts for spectral variabilities by using the Perturbated Linear Mixture Model and we exploit sparse modeling to recover spatially variant spectra. Preliminary results show a significant improvement on the detection of spectral variabilities in comparison with State-of-the-Art algorithms.

Abstract204-EL HAMZAOUI-204.pdf

Jointly sparse recovery via manifold optimization

Armenak PETROSYAN, Hoang TRAN, Clayton WEBSTER

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 non-compact Steifel manifold.


Short-and-Sparse Deconvolution - A Geometric Approach

Yenson LAU1, Qing QU2, Han-Wen KUO1, Pengcheng ZHOU3, Yuqian ZHANG4, John WRIGHT1,5

1Department of Electrical Engineering and Data Science Institute, Columbia University; 2Center for Data Science, New York University; 3Center for Neurocience, Columbia University; 4Department of Computer Science, Cornell University; 5Department of Applied Physics and Applied Mathematics, Columbia University

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


Separability/identifiability properties of low-rank matrix factorization methods for bilinear mixtures of source signals


University of Toulouse, France

We here first analyze the solutions of low-rank

matrix factorization methods for bilinear mixtures of an arbitrary number

of source signals, in terms of estimated sources

(separability properties) and estimated mixing model parameters (identifiability

properties), without requesting non-negative data.

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

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

indeterminacies) under mild conditions.

Associated practical BMMF algorithms are also discussed.

Test results prove the relevance of the assumptions used in

this separability/identifiability investigation and

show the performance of these algorithms for

multispectral and hyperspectral remote sensing data.


An IRLS Approach for Low-Rank Matrix Factorization


National Observatory of Athens, Greece

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

2:30pm - 3:30pmPlenary 6: Yuejie Chi (Carnegie Mellon University)

Geometry and Regularization in Nonconvex Low-Rank Estimation
Amphi B00 
3:30pm - 4:10pmOral session 10 (2 talks)
Amphi B00 

Phaseless PCA: Low-Rank Matrix Recovery from Column-wise Phaseless Measurements

Seyedehsara NAYER, Praneeth NARAYANAMURTHY, Namrata VASWANI

Iowa State University, United States of America

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


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 non-convex optimization in which having a good initialization is crucial. The spectral method is one of the well-known methods for such initialization.

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

4:10pm - 4:40pmCoffee Break
C101 - C103 
4:40pm - 6:00pmSpecial Talk : Michael Jordan (UC Berkeley)

Machine Learning: Dynamical, Statistical and Economic Perspectives
Amphi B00 
8:00pm - 11:00pmSPARS Banquet
Hôtel Dieu 
Date: Thursday, 04/Jul/2019
9:00am - 10:00amPlenary 7: Emilie Chouzenoux (University Paris-Est)

Proximal approaches for matrix optimization problems
Amphi B00 
10:00am - 10:40amOral session 11 (2 talks)
Amphi B00 

The fastest L1,oo prox in the west

Benjamin BEJAR1, Ivan DOKMANIC2, Rene VIDAL1

1The Johns Hopkins University, United States of America; 2University 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 well-known soft-thresholding algorithm. By exploiting the duality relationship to the Loo,1 norm we also derive the projection operator onto the Loo,1 ball. From our analysis, we are able to derive efficient algorithms for the computation of the proximal operator of the L1,oo norm that can be orders of magnitude faster than the state of the art. We also apply the Loo,1 norm for biomarker discovery (feature selection) for the problem of cancer classification from gene expression data.


Nonlinear matrix recovery

Florentin GOYENS1, Coralia CARTIS1, Armin EFTEKHARI2, Greg ONGIE3

1University of Oxford, United Kingdom; 2EPFL, Lausanne; 3University of Chicago

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

10:40am - 11:10amCoffee Break
C101 - C103 
11:10am - 12:10pmOral session 12 (3 talks)
Amphi B00 

A Spectral Method for Estimating Low-Rank Subspaces from Nonlinear Measurements

Wangyu LUO, Yue M. LU

Harvard University, United States of America

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


Iterative Hard Thresholding for Low-Rank Recovery from Rank-One Projections


Texas A&M University, United States of America

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


High-dimensional change point localization from noisy linear projections

Daren WANG1, Kevin LIN2, Rebecca WILLETT3

1Department of Statistics,University of Chicago; 2Department of Statistics and Data Science, Carnegie Mellon University; 3Department 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 state-of-art methods.

12:10pm - 2:30pmLunch + Poster session 4
C101 - C103 

Structured Signal Recovery from Quadratic Measurements

Kaihui LIU1, Feiyu WANG2, Liangtian WAN3

1University of Electronic Science and Technology of China; 2University of Electronic Science and Technology of China; 3Dalian University of Technology

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


The Sliding Frank-Wolfe Algorithm for the BLASSO

Quentin DENOYELLE1, Vincent DUVAL2, Gabriel PEYRE3, Emmanuel SOUBIES4


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


Tissue Reflectivity Function Restoration from Fundamental and Harmonic Ultrasound Images

Mohamad HOURANI1, Adrian BASARAB2, Denis KOUAME2, Jean-Yves TOURNERET1

1University of Toulouse, INP-ENSEEIHT, IRIT, CNRS UMR 5505; 2University 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

Dongdong CHEN1, Mohammad GOLBABAEE2, Pedro A. GOMEZ3,4, Marion I. MENZEL3, Mike E. DAVIES1

1The University of Edinburgh, United Kingdom; 2University of Bath, United Kingdom; 3Technical University of Munich, Germany; 4GE 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 (MRF-FCNN), in which coupled with a linear dimensionality reduction layer and a fully convolutional neural network, directly project data from the original MRF space into the tissue parameters manifold. Experiments on real data demonstrate the effectiveness of the method.


Efficient Approximation of Solutions of Parametric PDEs by ReLU Neural Networks

Gitta KUTYNIOK1, Philipp PETERSEN2, Mones RASLAN1, Reinhold SCHNEIDER1

1Technische Universität Berlin, Germany; 2University 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 low-dimensionality of the solution manifold established by the theory of reduced bases. To be more precise, for a large variety of parametric PDEs it is possible to construct neural networks that yield approximations of the parameter-dependent maps which avoid a curse of dimension and essentially only depend on the size of the reduced basis. The obtained rates are significantly better than those provided by classical approximation results.


An Inexact Augmented Lagrangian Framework for Non-Convex Optimization with Nonlinear Constraints


EPFL, Switzerland

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


Ergodic bilevel optimization

Christoph BRAUER, Dirk LORENZ

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 Chambolle-Pock algorithm in order to accomplish the differentiation approximately. We investigate the asymptotic behavior of the gradients and conclude that unrolling ergodic averages can have a positive effect on the learning dynamics.


Learning low-dimensional surfaces and functions

Qing ZOU, Mathews JACOB

University of Iowa, United States of America

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


Unsupervised parameter selection in variational regularization

Zeljko KERETA1, Ernesto DE VITO2, Valeriya NAUMOVA1

1Simula Research Laboratory, Norway; 2Universita 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 non-linear regularization methods and various noise models.

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


Exact recovery analysis of non-negative orthogonal matching pursuit

Thanh T. NGUYEN1, Charles SOUSSEN2, Jerome IDIER3, El-Hadi DJERMOUNE1

1CRAN, Universite de Lorraine, France; 2L2S, CentraleSupelec, France; 3LS2N, CNRS, France

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


Manifold Alignment by Feature Correspondence


1Yale University, United States of America; 2Université 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.

Abstract243-STANLEY III-243.pdf

A Deep Analysis Dictionary Model

Jun-Jie HUANG, Pier Luigi DRAGOTTI

Imperial College London, United Kingdom

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


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 re-derived, considering the particulars of whether the measurements are isotropic or the analysis operator is invertible or injective. This paper aims at describing a general recipe for supplying dual certificates that generalizes the existing ones in the literature while keeping constraints on the relevant linear operators to a minimum.


Distributed First-Order Optimization with Tamed Communications


1University Grenoble Alpes; 2CNRS

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


Exact recovery of partially sparse vectors

Christoph BRAUER1, Dirk LORENZ1, Andreas TILLMANN2

1TU Braunschweig, Germany; 2RWTH 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 non-convex penalties


1TU Braunschweig, Germany; 2Alpen-Adria 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 non-convex.


Hyperspectral Uncertainty Quantification by Optimization


Heriot-Watt 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 single-channel UQ. Similarly, the Bayesian hypothesis test is formulated as a convex minimization problem and solved using a primal-dual algorithm to quantify the uncertainty associated with particular 3D structures appearing in the maximum a posteriori (MAP) estimate of the HS cube. We investigate the interest of the proposed method for wideband radio-interferometric (RI) imaging that consists in inferring the wideband sky image from incomplete and noisy Fourier measurements. We showcase the performance of our approach on realistic simulations.


Label-consistent sparse auto-encoders

Thomas ROLLAND1,2, Adrian BASARAB1, Thomas PELLEGRINI1

1IRIT, Université Paul Sabatier, CNRS; 2INESC-ID

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


Natural Variation Transfer using Learned Manifold Operators

Marissa CONNOR1, Benjamin CULPEPPER2, Huy NGUYEN2, Christopher ROZELL1

1Georgia Institute of Technology, United States of America; 2Yahoo! Research, United State of America

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


NMF-based sparse unmixing of complex mixtures.

Afef CHERNI1, Elena PIERSANTI2, Caroline CHAUX1

1Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille, France.; 2Aix 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 Hadamard-Haar Systems


1ISPGroup, ICTEAM/ELEN, UCLouvain, Belgium; 2IT, 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 sample-complexity bound for Hadamard-Haar systems; a seemingly missing result in the related literature. The power of this approach is demonstrated on several simulations.


Robust Super-Resolution via Deep Learning and TV Priors

Marija VELLA, Colin RICKMAN, Joao F.C. MOTA

Heriot-Watt 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 sparsity-based methods, in contrast, require no training data, which makes them robust. Furthermore, being based on convex optimization, they have strong theoretical foundations. We propose a method that combines both models, leveraging the good performance of neural networks and the robustness of sparsity-based methods. Experiments show that it significantly outperforms state-of-the-art SR algorithms in the quality of reconstruction.


Sampling over spiraling curves

Felipe NEGREIRA1, Philippe JAMING1, José Luis ROMERO2,3

1Université de Bordeaux, France; 2Faculty of Mathematitcs, University of Vienna; 3Acoustics Research Institute, Austrian Academy of Science

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


Stochastic Signal Processing in Phase Space


1Technische Universität Berlin, Germany; 2Tel 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 phase-vocoder method (in audio signal processing), based on an enhanced time-frequency space.


Tight Framelets and Fast Framelet Filter Bank Transforms on Manifolds

Yu Guang WANG1, Xiaosheng ZHUANG2

1The University of New South Wales, Sydney, Australia; 2City 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 semi-discrete settings. We show that polynomial-exact quadrature rules on M give a simple way of constructing semi-discrete tight framelets in L2(M). We describe fast framelet filter bank transforms (FMTs) with nearly linear computational complexity and low redundancy rate based on the fast algorithms for discrete Fourier transforms (FFTs) on M. Moreover, We construct framelets on the 2-sphere S2 with two high passes (b1 and b2) and gives numerical examples for the FMT algorithms on S2.


On variable splitting for Markov chain Monte Carlo

Maxime VONO1, Nicolas DOBIGEON1, Pierre CHAINAIS2

1University of Toulouse - INP/ENSEEIHT (IRIT), France; 2Ecole 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 sub-problems. In this work, we take inspiration from this variable splitting idea to build efficient Markov chain Monte Carlo (MCMC) algorithms. Starting from an initial complex target distribution, auxiliary variables are introduced such that the marginal distribution of interest matches the initial one asymptotically. In addition to have theoretical guarantees, the benefits of such an asymptotically exact data augmentation (AXDA) are fourfold: simpler full conditional distributions, possibility to embed existing MCMC approaches, to distribute the inference and to respect data privacy issues.


Fast Double-coupled Nonnegative Tensor Decomposition

Xiulin WANG1,2, Tapani RISTANIEMI2, Fengyu CONG1,2

1Dalian University of Technology, China, People's Republic of; 2University 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 double-coupled nonnegative Canonical Polyadic decomposition (FDC-NCPD) algorithm. It enables the simultaneous extraction of common components and individual components. In addition, its time-consumption is greatly reduced without compromising the decomposition quality when handling large-scale problems. Simulation results demonstrate the superior performance of the proposed algorithm.


Structured Discrete Shape Approximation

Andreas Michael TILLMANN, Leif KOBBELT

RWTH Aachen University, Germany

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


Antisparse Blind Source Separation

Renan Del Buono BROTTO1, Kenji NOSE-FILHO2, João Marcos Travassos ROMANO1

1University of Campinas, Brazil; 2Federal 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:30pmPlenary 8: Monika Dörfler (University of Vienna)

Pre-processing data for deep learning? The balance between discriminability and invariance
Amphi B00 
3:30pm - 4:30pmOral 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 closed-form expressions that allow to easily deduce the asymptotic behavior in high dimensions.


Uniform k-step recovery with CMF dictionaries

Clément ELVIRA1, Rémi GRIBONVAL1, Charles SOUSSEN2, Cédric HERZET1

1Univ Rennes, Inria, CNRS, IRISA; 2L2S, CentraleSupélec-CNRS-Université Paris-Saclay

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

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

4:30pm - 4:40pmClosing remarks
Amphi B00 

Contact and Legal Notice · Contact Address:
Privacy Statement · Conference: SPARS 2019
Conference Software - ConfTool Pro 2.6.127+TC+CC
© 2001 - 2019 by Dr. H. Weinreich, Hamburg, Germany