SPARS 2017


Yoram Bresler (University of Illinois, USA)

"Sparse Signal Recovery in Bilinear Inverse Problems"

Slides from the talk

Much less is known about the solution of bilinear inverse problems (BLIPs) than about their linear counterparts. In signal processing, BLIPs arise in blind signal recovery, notably in blind deconvolution, with applications in blind image deblurring, blind channel equalization, speech dereverberation, and seismic data analysis. Another important example, is blind gain and phase calibration (BGPC), arising, e.g., in blind albedo estimation in inverse rendering, in sensor array processing with miscalibrated arrays, in multichannel blind deconvolution, and in multichannel MRI.

In certain cases, low dimensionality or sparsity constraints alleviate the ill-posedness of BLIPs. However, until recently, existing theoretical analysis on uniqueness in these problems was rather limited. We present results on sample complexity that guarantee stable recovery in blind deconvolution and in BGPC under minimal requirements. We complement these theoretical results by practical recovery algorithms: (1) a guaranteed sparse blind deconvolution algorithm with optimal (up to log factors) scaling of the sample complexity, both in theory and in numerical experiments; and (2) a BGPC algorithm that in adversarial conditions improves on competing algorithms.

Based on joint work with Yanjun Li, Kiryung Lee, and Marius Junge

Yoram Bresler received the B.Sc. (cum laude) and M.Sc. degrees from the Technion, Israel Institute of Technology, in 1974 and 1981 respectively, and the Ph.D degree from Stanford University, in 1986, all in Electrical Engineering.

In 1987 he joined the University of Illinois at Urbana-Champaign, where he is currently a Professor at the Departments of Electrical and Computer Engineering and Bioengineering, and Research Professor at the Coordinated Science Laboratory.

His current research interests include compressed sensing and multi-dimensional and statistical signal processing and their applications to inverse problems in imaging, and in particular computed tomography and magnetic resonance imaging.

Dr. Bresler has served on the editorial board of a number of journals, and on various committees of the IEEE. Currently he serves on the editorial boards for the IEEE Journal on Selected Topics in Signal Processing, and the SIAM Journal on Imaging Science. Dr. Bresler is a fellow of the IEEE and of the AIMBE. He received two Senior Paper Awards from the IEEE Signal Processing society, and a paper he coauthored with one of his students received the Young Author Award from the same society in 2002.  He is the recipient of a 1991 NSF Presidential Young Investigator Award, the Technion (Israel Inst. of Technology) Fellowship in 1995, and the Xerox Senior Award for Faculty Research in 1998. He was named a University of Illinois Scholar in 1999, appointed as an Associate at the Center for Advanced Study of the University in 2001-2, and Faculty Fellow at the National Center for Super Computing Applications in 2006.

Dr. Bresler is a co-founder (along with Dr. Munson), president, and chief technology officer of InstaRecon, Inc., a software startup that develops and markets breakthrough image reconstruction technology for CT scanners, originating from his research with students and colleagues at the University.

Gitta Kutyniok (Technische Universität Berlin, Germany)

"Optimal Approximation with Sparse Deep Neural Networks"

Slides from the talk

"Despite the outstanding success of deep neural networks in real-world applications, most of the related research is empirically driven and a mathematical foundation is almost completely missing. One central task of a neural network is to approximate a function, which for instance encodes a classification task. In this talk, we will be concerned with the question, how well a function can be approximated by a deep neural network with sparse connectivity. We will derive fundamental lower bounds on the connectivity and the memory requirements of deep neural networks guaranteeing uniform approximation rates for arbitrary function classes, also including functions on low-dimensional immersed manifolds. Additionally, we prove that our lower bounds are achievable for a broad family of function classes, thereby deriving an optimality result. Finally, we present numerical experiments demonstrating that the standard stochastic gradient descent algorithm generates deep neural networks providing close-to-optimal approximation rates at minimal connectivity. Moreover, surprisingly, these results show that stochastic gradient descent actually learns approximations that are sparse in the representation systems optimally sparsifying the function class the network is trained on.

This is joint work with H. Bölcskei, P. Grohs, and P. Petersen.

Gitta Kutyniok completed her Diploma in Mathematics and Computer Science in 1996 at the Universitat Paderborn in Germany. She received her Ph.D. degree in the area of time-frequency analysis from the same university in 2000. She completed her Habilitation in Mathematics in 2006 and received her venia legendi. In 2007, she was awarded a Heisenberg Fellowship by the DFG-German Research Foundation.

From 2001 to 2008 she held visiting appointments at several US institutions, including Princeton University, Stanford University, Yale University, Georgia Institute of Technology, and Washington University in St. Louis.

After returning to Germany in October 2008, she became a full professor of mathematics at the Universitat Osnabrueck, and headed the Applied Analysis Group. Since October 2011, she has an Einstein Chair at the Technical University of Berlin and is head of the Applied Functional Analysis Group (AFG).

Her research and teaching have been recognized by various awards, including the von Kaven Prize by the German Research Foundation, awards by the University Paderborn and the Justus-Liebig University Giessen for Excellence in Research, as well as the Weierstrass Prize for Outstanding Teaching. She is an Associate Editor and also Corresponding Editor for several journals in the area of applied mathematics. She is also a board member of the Berlin Mathematical School, a member of the council of the MATHEON "Mathematics for key technologies" in Berlin, and the chair of the GAMM activity group on "Mathematical Signal and Image Processing.

Volkan Cevher (EPFL, Switzerland)

Learning-based compressive subsampling

In the past decade, there have been significant advances in methods that directly acquire only the “relevant” information during data acquisition. For instance, compressive sensing (CS) simultaneously performs data acquisition and compression, seeking to directly sample for the relevant information in signals as opposed to acquiring a full signal only to throw most of it away via compression. Despite the tremendous amount of research in CS, there exist severe limitations in this existing theory and methodology that have prevented its widespread use in practical systems. Indeed, many approaches assume an unrealistic amount of knowledge of the system model (e.g., perfect knowledge of the sparsity basis). Moreover, the strongest theoretical results for CS are based on measurement designs that scale poorly due to the computational challenges associated with dense sensing operators, or that rely on randomization methods that are impractical and perhaps not even possible in applications.

In this talk, we will introduce a new paradigm, partially addressing emerging challenges by unifying compressive sensing with statistical learning theory. Our key idea, which is surprisingly simple in retrospect, is that by using training signals and developing combinatorial training procedures, we can efficiently and effectively learn the structure inherent in the data, and accordingly design measurement matrices that directly acquire only the relevant information during acquisition. As a result, we will show how we can not only outperform the existing state-of-the-art compressive sensing techniques on real-world datasets (including neural signal acquisition and magnetic resonance imaging), but can do so with strong theoretical guarantees.

In particular, we will describe how to optimize the samples for the standard linear acquisition model along with the use of a simple linear decoder, and build towards optimizing the samples for non-linear reconstruction algorithms. Overall, the mathematical premise of our approach represents a re-thinking of the data models and dimensionality reduction using continuous optimization algorithms based on convexity, and combinatorial optimization algorithms based on submodularity.

Volkan Cevher received the B.Sc. (valedictorian) in electrical engineering from Bilkent University in Ankara, Turkey, in 1999 and the Ph.D. in electrical and computer engineering from the Georgia Institute of Technology in Atlanta, GA in 2005. He was a Research Scientist with the University of Maryland, College Park from 2006-2007 and also with Rice University in Houston, TX, from 2008-2009. Currently, he is an Associate Professor at the Swiss Federal Institute of Technology Lausanne and a Faculty Fellow in the Electrical and Computer Engineering Department at Rice University. His research interests include signal processing theory, machine learning, convex optimization, and information theory. Dr. Cevher was the (co-) recipient of the IEEE Signal Processing Society Best Paper Award in 2016, a Best Paper Award at CAMSAP in 2015, a Best Paper Award at SPARS in 2009, and an ERC CG in 2016 as well as an ERC StG in 2011.

Jalal Fadili (ENSICAEN, France)

"Exponential weighted aggregation vs penalized estimation: guarantees and algorithms"

Slides from the talk

Two approaches are usually used to solve high-dimensional linear inverse problems: 1) the penalized approach which amounts to solving an optimization problem, and 2) the exponential weighted aggregation (EWA) which solves an integration problem. In this talk, I will present a unified analysis of the performance guarantees of both estimators with a general class of priors which encourage objects which conform to some notion of simplicity/complexity. More precisely, we show that these two estimators satisfy (i) sharp oracle inequalities for prediction, and (ii) estimation error bounds ensuring their good theoretical performances. We also highlight the differences between them. When the noise or the design is random, we provide bounds which holds with high probability under mild assumptions on the underlying distribution. Finally, we propose a framework based on proximal splitting to efficiently implement these estimators. The results are then exemplified on several popular instances in signal/image processing and machine learning.

Jalal M. Fadili graduated from the École Nationale Supérieure d'Ingénieurs (ENSI) de Caen, Caen, France, and received the M.Sc. and Ph.D. degrees in signal and image processing from the University of Caen. He was a Research Associate with the University of Cambridge MacDonnel-Pew Fellow), Cambridge, U.K., from 1999 to 2000. He has been an Associate Professor of signal and image processing since September 2001 at ENSI. He also received an Habilitation from University of Caen in 2010. He was a visitor at several universities (QUT-Australia, Stanford University, CalTech, MIT, EPFL). He is the co-author of a book entitled "Sparse Signal and Image Processing: Wavelets, Curvelets, Morphological Diversity" Cambridge University Press. His research interests include statistical approaches in signal and image processing, inverse problems, computational harmonic analysis, optimization and sparse representations. His areas of application include medical and astronomical imaging.

Eero Simoncelli (New York University, USA)

"Cascaded Gain Control Representations for Images"

Slides from the talk

I’ll describe some recent work on developing models for visual representation based on a cascaded architecture, in which each stage performs convolutions with a set of kernels, nonlinear rectification, and locally adaptive gain control. All three operations are primarily motivated by known functional properties of neural response throughout the visual system, and their parameters can be set by fitting physiological or perceptual data. Alternatively, they can be optimized to capture statistical relationships found in natural images, or to achieve a specific engineering goal, such as restoration, compression, or recognition. I’ll show examples of their use in optimizing the display of photographs (for example, rendering an HDR image on a LDR display), and as the basis of a high-quality image coder that is optimized in terms of its rate-distortion tradeoff.

Dr. Simoncelli is Professor of Neural Science, Mathematics, and Psychology at New York University. He began his higher education as a physics major at Harvard, went to Cambridge University on a Knox Fellowship to study mathematics for a year and a half, and earned a doctorate in electrical engineering and computer science at the Massachusetts Institute of Technology. He then joined the faculty of the Computer and Information Science Department at the University of Pennsylvania. In 1996, he moved to NYU as part of the Sloan Center for Theoretical Visual Neuroscience. In 2000, he became an Investigator of the Howard Hughes Medical Institute. He is a fellow of the IEEE, has received two IEEE Best Paper awards and a Sustained Impact paper award, and received an Engineering Emmy award in 2015.

Anders Hansen (University of Cambridge, UK)

"On Foundational Computational Problems in ℓ1 and Total Variation Regularisation"

Slides from the talk

The use of regularisation techniques such as ℓ1 and Total Variation in Basis Pursuit and Lasso has been a great success in wide areas of mathematics and statistics over the last decades. In this talk we will discuss universal boundaries regarding the existence of algorithms for solving these problems. For example we have the following paradox: it is impossible to design algorithms to solve these general problems accurately when given inaccurate input data, even when the inaccuracies can be made arbitrarily small. As a simple number such as root(2) never comes with an exact numerical representation, inaccurate data input is a daily encounter. The impossibility result implies that for any algorithm designed to solve these problems there will be cases where the algorithm fails in the following way: For fixed dimensions and any small accuracy parameter epsilon > 0, one can choose an arbitrary large time T and find an input such that the algorithm will run for longer than T and still not have reached epsilon accuracy. Moreover, it is impossible to determine when the algorithm should halt to achieve an epsilon accurate solution, and hence the algorithm will never be able to produce an output where one knows that the output is at least epsilon accurate. The largest epsilon for which this failure happens is called the Breakdown-epsilon. For Basis Pursuit and Lasso, the Breakdown-epsilon > 1/3 even when the absolute value of the input is bounded by one and is well conditioned.

The paradox opens up for a new classification theory to determine the boundaries of what computers can achieve in regularisation, and to explain why empirically many modern algorithms for solving regularisation problem in real-world scenarios perform very well. We will discuss positive classification results showing that sparse problems can be computed accurately. However, this is delicate; e.g. given standard assumptions from sparse recovery, there are algorithms that can compute a solution to Basis Pursuit accurately, however, this is impossible for Lasso and Basis Pursuit with noise parameter delta > 0. However, one can compute a solution accurately up to the Breakdown-epsilon that tends to zero when delta tends to zero, and coincides with the error bound provided in the theory of sparse recovery. This helps explaining the success of many modern algorithms applied in numerous real-world scenarios, and also explains the cases where algorithms will fail and why.

Anders Hansen leads the Applied Functional and Harmonic Analysis group within the Cambridge Centre for Analysis at DAMTP. He is a Lecturer at the Department of Applied Mathematics and Theoretical Physics, Professor of Mathematics at the University of Oslo, a Royal Society University Research Fellow, and a Fellow of Peterhouse. He received an M.A. from the University of California, Berkeley, and a PhD from the University of Cambridge, both in mathematics. His research interests are: applied functional analysis, operator/spectral theory, complexity theory, foundations of computational mathematics, compressed sensing, mathematical signal processing, computational harmonic analysis, inverse problems, medical imaging, geometric integration, numerical analysis, C* algebras. He is on the editorial board of the Proceedings of the Royal Society (Series A).

Phil Schniter (Ohio State University, USA)

"Recent Advances in Approximate Message Passing"

Slides from the talk

The approximate message passing (AMP) algorithm proposed in 2009 by Donoho, Maleki, and Montanari is a computationally efficient iterative approach to sparse reconstruction and related problems. AMP has a remarkable property: for large i.i.d. sub-Gaussian measurement matrices, its per-iteration behavior is rigorously characterized by a scalar state-evolution whose fixed points, when unique, are Bayes optimal. However, AMP is fragile in that even small deviations from the i.i.d. sub-Gaussian model can cause the algorithm to diverge. In this talk, I will describe a "vector AMP" (VAMP) algorithm, which also has a rigorous scalar state-evolution. VAMP's state-evolution, however, holds under a much broader class of large random measurement matrices, those that are right-rotationally invariant. I will also discuss non-parametric versions of VAMP that can cope with unknown prior and/or likelihood, connections between VAMP and convex optimization algorithms, plug-and-play extensions of VAMP, and connections between VAMP and deep neural networks.

Philip Schniter received the B.S. and M.S. degrees in Electrical Engineering from the University of Illinois at Urbana-Champaign in 1992 and 1993, respectively. From 1993 to 1996 he was employed by Tektronix Inc. in Beaverton, OR as a systems engineer. In 2000, he received the Ph.D. degree in Electrical Engineering from Cornell University in Ithaca, NY. Subsequently, he joined the Department of Electrical and Computer Engineering at The Ohio State University in Columbus, OH, where he is now a Professor and a member of the Information Processing Systems (IPS) Lab. He held visiting professor positions at Eurecom (Sophia Antipolis, France) from October 2008 through February 2009, and at Supelec (Gif sur Yvette, France) from March 2009 through August 2009. He is currently (August 2016 to June 2017) a visiting professor at Duke University (Durham, NC).

Philip Schniter is an IEEE Fellow and a member of the IEEE Signal Processing Society and IEEE Information Theory Society. Since 2013 he has been elected to serve on the IEEE Sensor Array and Multichannel (SAM) Technical Committee, and from 2005-2010 he was elected to serve on the IEEE Signal Processing for Communications and Networking (SPCOM) Technical Committee.

While pursuing his Ph.D. degree, Dr. Schniter received a Schlumberger Fellowship and an Intel Foundation Fellowship. He was awarded the 1999 Prize Paper Award from the IEEE Energy Development and Power Generation Committee for work relating to his M.S. thesis. In 2003, he received the National Science Foundation CAREER Award and, in 2005, the OSU College of Engineering Lumley Research Award. With graduate student Jason Parker and Volkan Cevher, he won the 2016 IEEE Signal Processing Society Best Paper Award.

Dr. Schniter's areas of research include signal processing, machine learning, information theory, communication theory, compressed sensing, and sensor networks. His recent sources of funding include the National Science Foundation, the Defense Advanced Research Projects Agency, the Air Force Research Laboratory, MIT Lincoln Labs, the Office of Naval Research, Sandia National Labs, and Motorola Labs.

Rebecca Willett (University of Wisconsin, USA)

"Nonlinear Models for Matrix Completion"

Slides from the talk

The past decade of research on matrix completion has shown it is possible to leverage linear dependencies to impute missing values in a low-rank matrix. However, the corresponding assumption that the data lies in or near a low-dimensional linear subspace is not always met in practice. Extending matrix completion theory and algorithms to exploit low-dimensional nonlinear structure in data will allow missing data imputation in a far richer class of problems. In this talk, I will describe several models of low-dimensional nonlinear structure and how these models can be used for matrix completion. In particular, we will explore matrix completion in the context of three different nonlinear models: single index models, in which a latent subspace model is transformed by a nonlinear mapping; unions of subspaces, in which data points lie in or near one of several subspaces; and nonlinear algebraic varieties, a polynomial generalization of classical linear subspaces. In these settings, we will explore novel and efficient algorithms for imputing missing values and new bounds on the amount of missing data that can be accurately imputed. The proposed algorithms are able to recover synthetically generated data up to predicted sample complexity bounds and outperform standard low-rank matrix completion in experiments with real recommender system and motion capture data.

Rebecca Willett is an Associate Professor of Electrical and Computer Engineering, Harvey D. Spangler Faculty Scholar, and Fellow of the Wisconsin Institutes for Discovery at the University of Wisconsin-Madison. She completed her PhD in Electrical and Computer Engineering at Rice University in 2005 and was an Assistant then tenured Associate Professor of Electrical and Computer Engineering at Duke University from 2005 to 2013. Willett received the National Science Foundation CAREER Award in 2007, is a member of the DARPA Computer Science Study Group, and received an Air Force Office of Scientific Research Young Investigator Program award in 2010. Willett has also held visiting researcher or faculty positions at the University of Nice in 2015, the Institute for Pure and Applied Mathematics at UCLA in 2004, the University of Wisconsin-Madison 2003-2005, the French National Institute for Research in Computer Science and Control (INRIA) in 2003, and the Applied Science Research and Development Laboratory at GE Healthcare in 2002.