EPFL-Idiap-ETH Sparsity Workshop 2015

The Sparsity workshop is one-day event taking place on March 25, 2015 at EPFL, Auditoire BC 420.

This workshop brings together researchers from Swiss Federal Institute of Technology in Lausanne (EPFL), Swiss Federal Institute of Technology in Zurich (ETHZ) and Idiap Research Institute, Martigny in collegial setting to share ideas and discuss problems of interest in sparsity modelling. The key objective is to foster the cross-disciplinary collaborations.

This workshop features a keynote speech by Prof. Massimiliano Pontil from Centre for Computational Statistics and Machine Learning, University College London (UCL).
The invited talks will address recent theoretical developments and highlight applications in various signal processing disciplines, among which image, speech and brain data processing problems.

Morning Session 1

Morning Session 2

Afternoon Session 1

Afternoon Session 2

Contact Afsaneh Asaei and Luca Baldassarre for any question.

Abstracts

A totally unimodular view of structured sparsity - Marwa El-Halabi (EPFL)

This talk describes a simple framework for structured sparse recovery based on convex optimization. I show that many structured sparsity models can be naturally represented by linear matrix inequalities on the support of the unknown parameters, where the constraint matrix has a totally unimodular (TU) structure. For such structured models, tight convex relaxations can be obtained in polynomial time via linear programming. Our modeling framework unifies the prevalent structured sparsity norms in the literature, introduces new interesting ones, and renders their tightness and tractability arguments transparent.

Scalable optimization for mixture of regularizers - Baran Gözcü (EPFL)

In Compressive Imaging, mixtures of different sparsity-imposing regularizers are known to improve the reconstruction quality. We propose a primal-dual framework that is scalable to high resolution images and work with provable theoretical guarantees.

From MAP to Marginals: Variational inference in Bayesian submodular models - Josip Djolonga (ETH)

Submodular optimization has found many applications in machine learning and beyond. We carry out the first systematic investigation of inference in probabilistic models defined through submodular functions, generalizing regular pairwise MRFs and Determinantal Point Processes. In particular, we present L-Field, a variational approach to general log-submodular and log-supermodular distributions based on sub- and supergradients. We obtain both lower and upper bounds on the log-partition function, which enables us to compute probability intervals for marginals, conditionals and marginal likelihoods. We also obtain fully factorized approximate posteriors, at the same computational cost as ordinary submodular optimization. Our framework results in convex problems for optimizing over differentials of submodular functions, which we show how to optimally solve. We provide theoretical guarantees of the approximation quality with respect to the curvature of the function. We further establish natural relations between our variational approach and the classical mean-field method. Lastly, we empirically demonstrate the accuracy of our inference scheme on several submodular models.

Learning parametric dictionaries for signals on graphs - Dorina Thanou (EPFL)

In sparse signal representation, the choice of a dictionary often involves a tradeoff between two desirable properties -- the ability to adapt to specific signal data and a fast implementation of the dictionary. To sparsely represent signals residing on weighted graphs, an additional design challenge is to incorporate the intrinsic geometric structure of the irregular data domain into the atoms of the dictionary. In this work, we propose a parametric dictionary learning algorithm to design data-adapted, structured dictionaries that sparsely represent graph signals. In particular, we model graph signals as combinations of overlapping local patterns. We impose the constraint that each dictionary is a concatenation of subdictionaries, with each subdictionary being a polynomial of the graph Laplacian matrix, representing a single pattern translated to different areas of the graph. The learning algorithm adapts the patterns to a training set of graph signals. Experimental results on both synthetic and real datasets demonstrate that the dictionaries learned by the proposed algorithm are competitive with and often better than unstructured dictionaries learned by state-of-the-art numerical learning algorithms in terms of sparse approximation of graph signals. In contrast to the unstructured dictionaries, however, the dictionaries learned by the proposed algorithm feature localized atoms and can be implemented in a computationally efficient manner in signal processing tasks.

A compressive sensing perspective of linguistic information recovery - Pranay Dighe (Idiap)

Perceptual modeling through an auditory-inspired sparse representation- Raphael Ullmann (Idiap)

In the evolution of our sensory systems, encoding environmental stimuli efficiently has been emphasized as a key aspect. For the case of neural sound coding, sparse approximations of sound waveforms have been proposed as a computational model of efficient coding (E. C. Smith and M. S. Lewicki, “Efficient Auditory Coding”, Nature 439(7079), 2006). It was shown that this model could predict cochlear filter shapes as efficient kernels for a diverse range of sound classes. In this talk, I will discuss how a similar model can be used to also evaluate perceptual properties of sound. In particular, we seek to evaluate the perceived intrusiveness of background noises in speech recordings. Such an automatic evaluation is useful to measure the quality of telephone speech recorded in noisy environments. We approach this problem with the efficient auditory coding model to obtain an alternate representation of the noise signal. Specifically, the signal is approximated as a sparse linear combination of kernels that resemble cochlear filter shapes. In this perceptually motivated representation, the number of elements directly correlates with the perceived intrusiveness of noise. I will provide several examples that show how the model accounts for different acoustic factors in the perception of noise. On a dataset of subjectively evaluated telephone speech, our model compares to or outperforms more traditional indicators, such as weighted noise level or loudness.

Super-resolution radar, Reinhard Heckel (ETH)

In this talk, we study the identification of a time-varying linear system whose response is a weighted superposition of time and frequency shifted versions of the input signal. This problem arises in a multitude of applications such as wireless communications and radar imaging. Due to practical constraints, the input signal has finite bandwidth B, and the received signal is observed over a finite time interval of length T only. This gives rise to a time and frequency resolution of 1/B and 1/T. We show that this resolution limit can be overcome, i.e., we can recover the exact (continuous) time-frequency shifts and the corresponding attenuation factors, by essentially solving a simple convex optimization problem. This result holds provided that the distance between the time-frequency shifts is at least 2.37/B and 2.37/T, in time and frequency. Furthermore, this result allows the total number of time-frequency shifts to be linear (up to a log-factor) in BT, the dimensionality of the response of the system. More generally, we show that we can estimate the time-frequency components of a signal that is S-sparse in the continuous dictionary of time-frequency shifts of a random (window) function, from a number of measurements, that is linear (up to a log-factor) in S.

Regularization with the Spectral k-Support Norm, Andrew McDonald (UCL)

The k-support norm enjoys good estimation properties in sparse vector learning problems, with strong empirical performance compared to the Lasso method on a number of datasets. We discuss how it can be extended to an orthogonally invariant matrix norm which can be used as an alternative to the trace norm in low rank matrix completion problems. Furthermore we show that it is closely related to a regularizer used in clustered multitask learning. The unit ball of the k-support norm is characterized by vectors of small support and unit Euclidean norm. We discuss how the norm can be generalized by alternatively imposing an Lp-norm constraint. The resulting norm allows us to better match the decay of the spectrum of the underlying model and can lead to improved learning. We show how the norms can be computed and how to solve the associated regularization problems using proximal-gradient methods and the Frank-Wolfe method. Finally, we provide empirical results which demonstrate the performance of the regularizers on collaborative filtering and user modelling applications.

A convex solution to disparity estimation from light fields via the primal-dual method- Mahdad Hosseini Kamal (EPFL)

I present a novel approach to the reconstruction of depth from light field data. Our method uses dictionary representations and group sparsity constraints to derive a convex formulation. Although our solution results in an increase of the problem dimensionality, we keep numerical complexity at bay by restricting the space of solutions and by exploiting an efficient Primal-Dual formulation. Comparisons with state of the art techniques, on both synthetic and real data, show promising performances.

Structured sparsity through reweighting and application to diffusion MRI - Anna Auría Rasclosa (EPFL)

We consider the problem of multiple sparse signal reconstruction and propose a new implementation of structured sparsity, inspired by joint sparsity and social sparsity ideas. We present a particular application for diffusion Magnetic Resonance Imaging (dMRI) data and show how this procedure can be used for fibre orientation reconstruction in the white matter of the brain. In that framework, our structured sparsity prior can be used to exploit the fundamental coherence between fibre directions in neighbour voxels. Through the definition of meaningful weights, our method leverages a reweighted $\ell_1$ minimisation scheme to impose spatial coherence of the solution, promoting sparsity and conveying spatial information simultaneously.

Near-optimal sensor placement for linear inverse problem, Juri Ranieri (EPFL)

A classic problem is the estimation of a set of parameters from measurements collected by a set of sensors. The number of sensors is often limited by physical or economical constraints and their placement is of fundamental importance to obtain accurate estimates. Unfortunately, the selection of the optimal sensor locations is intrinsically combinatorial and the available approximation algorithms are not guaranteed to generate always a good solution. In this talk, we present SmartSense, a greedy algorithm for the selection of optimal sensor locations based on the frame potential, a scalar property of matrices that measures the orthogonality of its rows. We show that SmartSense is near-optimal w.r.t. the mean square error of the estimated parameters, meaning that the solution is always guaranteed to be close to the optimal one. We conclude the talk with an extensive set of numerical experiments showing that SmartSense achieves the state-of-the-art performance while having the lowest computational cost, when compared to other greedy methods.