Videos: IMA Computational Imaging Workshop, October 14 - 18, 2019

** Nuit Blanche is now on Twitter: @NuitBlog ** 

Stanley Chan, Jeff Fessler, Justin Haldar, Ulugbek Kamilov, Saiprasad Ravishankar, Rebecca Willett, Brendt Wohlberg just organized a workshop at IMA on computational imaging. Short story as this blog just passed the 8 million page views. Understanding of Compressed sensing was in large part, at least by looking at the stats:hits on this blog, due to an IMA meeting on the subject and the fact that people could watch the videos afterward. Hoping for this workshop to follow the same path. Given the amount of ML in it, I wonder if it shouldn't have been called TheGreatConvergence meeting:-)

This workshop will serve as a venue for presenting and discussing recent advances and trends in the growing field of computational imaging, where computation is a major component of the imaging system. Research on all aspects of the computational imaging pipeline from data acquisition (including non-traditional sensing methods) to system modeling and optimization to image reconstruction, processing, and analytics will be discussed, with talks addressing theory, algorithms and mathematical techniques, and computational hardware approaches for imaging problems and applications including MRI, tomography, ultrasound, microscopy, optics, computational photography, radar, lidar, astronomical imaging, hybrid imaging modalities, and novel and extreme imaging systems. The expanding role of computational imaging in industrial imaging applications will also be explored.
Given the rapidly growing interest in data-driven, machine learning, and large-scale optimization based methods in computational imaging, the workshop will partly focus on some of the key recent and new theoretical, algorithmic, or hardware (for efficient/optimized computation) developments and challenges in these areas. Several talks will focus on analyzing, incorporating, or learning various models including sparse and low-rank models, kernel and nonlinear models, plug-and-play models, graphical, manifold, tensor, and deep convolutional or filterbank models in computational imaging problems. Research and discussion of methods and theory for new sensing techniques including data-driven sensing, task-driven imaging optimization, and online/real-time imaging optimization will be encouraged. Discussion sessions during the workshop will explore the theoretical and practical impact of various presented methods and brainstorm the main challenges and open problems.
The workshop aims to encourage close interactions between mathematical and applied computational imaging researchers and practitioners, and bring together experts in academia and industry working in computational imaging theory and applications, with focus on data and system modeling, signal processing, machine learning, inverse problems, compressed sensing, data acquisition, image analysis, optimization, neuroscience, computation-driven hardware design, and related areas, and facilitate substantive and cross-disciplinary interactions on cutting-edge computational imaging methods and systems.

•  Morning Theme: Optics/Photography
• Welcome to the IMA  Saiprasad Ravishankar (Michigan State University), Brendt Wohlberg (Los Alamos National Laboratory) 
• Computational Microscopy Laura Waller (University of California, Berkeley) 
•  Interpreting Photon and Electron Detections to Form Images Vivek Goyal (Boston University) 
• Q&A / Coffee  
• Tutorial on Julia Programming for Computational Imaging Jeff Fessler (University of Michigan) 
•  Surfing the Technology Wave 2019 and Algorithm-Hardware Co-Design - Industry Perspective + Q&A Sergio Goma (QUALCOMM) 
•  Afternoon Theme: Optimization for Computational Imaging (CI)
• Dictionary and model-based methods in quantitative MRI reconstruction Mariya Doneva (Philips Research Laboratory) 
• A simple 2D graphing tool for the convergence of fixed-point iterations and plug-and-play methods Wotao Yin (University of California, Los Angeles) 
•  Data Compression in Distributed Learning Ming Yan (Michigan State University) 
• Morning Theme: Novel Imaging Domains Rebecca Willett (University of Chicago) 
• Cryo-Electron Microscopy Image Analysis with Multi-Frequency Vector Diffusion Maps Zhizhen (Jane) Zhao (University of Illinois at Urbana-Champaign)
•  Imaging the Unseen: Taking the First Picture of a Black Hole Katie Bouman (California Institute of Technology) 
•  Q&A 
• Computational Methods for Large-scale Inverse Problems: Data-driven VS Physics-driven or Combined? Youzuo Lin (Los Alamos National Laboratory) 
• Affiliated Data Science Seminar: Simple Approaches to Complicated Data Analysis Deanna Needell (University of California, Los Angeles) 
•  Afternoon Theme: Perspectives on Machine Learning and Artificial Intelligence for CI
• Tutorial on Python Programming for Computational Imaging Frank Ong (Stanford University) 
•  Tutorial Part II 
•  Computational Imaging with Deep Learning Orazio Gallo (NVIDIA Corporation) 
• Poster Session and Reception 
• Morning Theme: Perspectives on Machine Learning and Artificial Intelligence for CI
• Jeff Fessler (University of Michigan)
• Coherent Optical Processing with Machine Learning Charles Bouman (Purdue University) 
• Faster Guaranteed GAN-based recovery in Linear Inverse Problems Yoram Bresler (University of Illinois at Urbana-Champaign) 
•  Q&A 
•  Geometry of Convolutional Neural Networks for Computational Imaging Jong Chul Ye (Korea Advanced Institute of Science and Technology (KAIST))  
• Afternoon Theme: X-Ray Computed Tomography Imaging 
• Novel CT Data Acquisition and Processing Joseph Stayman (Johns Hopkins University) 
•  Machine Learning for Tomographic Imaging Ge Wang (Rensselaer Polytechnic Institute) 
•  Q&A/Coffee Break 
•  Data and Image Domain Deep Learning for Tomographic Computational Imaging W. Clem Karl (Boston University) 
•  Q&A 
•  IEEE Computational Imaging Technical Committee Meeting (open to all) 
• Morning Theme: Signal Processing for CI Stanley Chan (Purdue University), Justin Haldar (University of Southern California) 
• Three Short Stories About Image Denoising Mario Figueiredo (Instituto Superior Tecnico)  
• Fourier Multispectral Imaging Keigo Hirakawa (University of Dayton) 
• Q&A 
• Modeling and removal of correlated noise using nonlocal patch-based collaborative filters, with applications to direct and inverse imaging Alessandro Foi (Tampere University of Technology) 
•  Afternoon Theme: Magnetic Resonance Imaging
• Computational Imaging: Beyond the limits imposed by lenses Ashok Veeraraghavan (Rice University)  
• Q&A / Coffee 
• Computational Imaging: From structured low-rank methods to model based deep learning. Mathews Jacob (The University of Iowa) 
• Q&A/Coffee Break 
•  Rise of the machines (in MR image reconstruction) Florian Knoll (NYU Langone Medical Center) 
• Q&A 
• Theme: Broad CI Modalities Ulugbek Kamilov (Washington University) 
• Computational Radar Imaging Mujdat Cetin (University of Rochester) 
•  Q&A 
• Challenges and Opportunities in Magnetic Resonance Fingerprinting Nicole Seiberlich (University of Michigan) 
•  Q&A/Closing Remarks Brendt Wohlberg (Los Alamos National Laboratory)

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn  or the Advanced Matrix Factorization group on LinkedIn

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email.

Other links:
Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup< br/> About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog
About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

Saturday Morning Videos: Bridging Continuous and Discrete Optimization Boot Camp, Simons Institute at Berkeley, August 21-25, 2017

Nikhil Bansal, Pablo Parrilo and Ben Recht organized a boot camp this week on "Bridging Continuous and Discrete Optimization" at the Simons Institute at Berkeley. The videos are already on the site, awesome !

Here are the abstracts and attendant videos:

 Duality 1

Duality 1

Speaker: Michel Goemans, MIT

In this tutorial, we will start by discussing some of the basic ideas and techniques that allow a discrete optimization problem to be relaxed or immersed into a continuous optimization problem. Typically, the resulting continuous optimization problem is convex, implying strong properties of duality and efficiency. As part of the first lecture, we will review convexification ideas and strong duality in the context of cone optimization problems. The second and third lectures will focus on many approaches for going back from the continuous problem to the discrete problem, i.e. rounding a solution from the larger, continuous problem into a solution to the discrete problem. This is a very rich area, and we will survey a variety of techniques.

Duality 2

Duality 2

Speaker: Michel Goemans, MIT

In this tutorial, we will start by discussing some of the basic ideas and techniques that allow a discrete optimization problem to be relaxed or immersed into a continuous optimization problem. Typically, the resulting continuous optimization problem is convex, implying strong properties of duality and efficiency. As part of the first lecture, we will review convexification ideas and strong duality in the context of cone optimization problems. The second and third lectures will focus on many approaches for going back from the continuous problem to the discrete problem, i.e. rounding a solution from the larger, continuous problem into a solution to the discrete problem. This is a very rich area, and we will survey a variety of techniques.

 LP/SDP Hierarchies and Sum of Squares Proofs 1

LP/SDP Hierarchies and Sum of Squares Proofs 1

Speaker: Pablo Parrilo, MIT and Ankur Moitra, MIT

In these introductory lectures we will present a unified introduction to Semidefinite Programming hierarchies and Sum of Squares techniques for continuous/discrete optimization, highlighting their many different and complementary interpretations (Lagrangian/algebraic duality, geometric embeddings, proof systems, probabilistic, etc). We will concisely summarize the state of the art in both positive and negative results (e.g., planted clique, tensor completion, constraint satisfaction), as well as current algorithmic approaches.

 LP/SDP Hierarchies and Sum of Squares Proofs 2

LP/SDP Hierarchies and Sum of Squares Proofs 2

Speaker: Pablo Parrilo, MIT and Ankur Moitra, MIT

In these introductory lectures we will present a unified introduction to Semidefinite Programming hierarchies and Sum of Squares techniques for continuous/discrete optimization, highlighting their many different and complementary interpretations (Lagrangian/algebraic duality, geometric embeddings, proof systems, probabilistic, etc). We will concisely summarize the state of the art in both positive and negative results (e.g., planted clique, tensor completion, constraint satisfaction), as well as current algorithmic approaches.

 Duality 3

Duality 3

Speaker: Michel Goemans, MIT

In this tutorial, we will start by discussing some of the basic ideas and techniques that allow a discrete optimization problem to be relaxed or immersed into a continuous optimization problem. Typically, the resulting continuous optimization problem is convex, implying strong properties of duality and efficiency. As part of the first lecture, we will review convexification ideas and strong duality in the context of cone optimization problems. The second and third lectures will focus on many approaches for going back from the continuous problem to the discrete problem, i.e. rounding a solution from the larger, continuous problem into a solution to the discrete problem. This is a very rich area, and we will survey a variety of techniques.

 Continuous Methods 1

Continuous Methods 1

Speaker: Lorenzo Orecchia, Boston University; Maryam Fazel, University of Washington; and Stefanie Jegelka, MIT

Techniques and insights from convex optimization play an important role in the design of algorithms for discrete optimization, as evidenced by the success of convex relaxations in providing a framework for constructing and analyzing approximation algorithms. In the last decade, iterative methods from convex optimization have served as a springboard to a number of algorithmic advances for many discrete optimization tasks, including fundamental ones such as submodular optimization and maximum flow problems.
In this bootcamp series, we will provide a walk-through of the continuous approach to algorithm design in discrete optimization. We will consider the algorithmic challenges that arise in the choice of formulation and iterative algorithm by casting first-order methods as discretizations of continuous-time dynamics. We will see that the non-smooth nature of discrete optimization problems leads us to smoothen our objectives via regularization and discuss how different choices of regularizers arise in different settings. We will then put these principles to work in the contexts of submodular optimization and competitive analysis of online algorithms.

 Continuous Methods 2

Continuous Methods 2

Speaker: Lorenzo Orecchia, Boston University; Maryam Fazel, University of Washington; and Stefanie Jegelka, MIT

Techniques and insights from convex optimization play an important role in the design of algorithms for discrete optimization, as evidenced by the success of convex relaxations in providing a framework for constructing and analyzing approximation algorithms. In the last decade, iterative methods from convex optimization have served as a springboard to a number of algorithmic advances for many discrete optimization tasks, including fundamental ones such as submodular optimization and maximum flow problems.
In this bootcamp series, we will provide a walk-through of the continuous approach to algorithm design in discrete optimization. We will consider the algorithmic challenges that arise in the choice of formulation and iterative algorithm by casting first-order methods as discretizations of continuous-time dynamics. We will see that the non-smooth nature of discrete optimization problems leads us to smoothen our objectives via regularization and discuss how different choices of regularizers arise in different settings. We will then put these principles to work in the contexts of submodular optimization and competitive analysis of online algorithms.

 Robustness, Stochastics, Uncertainty 1

Robustness, Stochastics, Uncertainty 1

Speaker: Sasha Rakhlin, University of Pennsylvania; Ben Recht, UC Berkeley; and Laurent El Ghaoui, UC Berkeley

In this session, we will provide an overview of stochastic and robust optimization, with problems in statistics and machine learning providing a motivating focus. We will discuss connections between convex optimization and regret minimization, both with stochastic and deterministic feedback. We will view these problems through the minimax lens and show how algorithms emerge as approximate dynamic programming solutions. Finally, we will review robust optimization and explore the interactions between robustness and regularization.

 Robustness, Stochastics, Uncertainty 2

Robustness, Stochastics, Uncertainty 2

Speaker: Sasha Rakhlin, University of Pennsylvania; Ben Recht, UC Berkeley; and Laurent El Ghaoui, UC Berkeley

In this session, we will provide an overview of stochastic and robust optimization, with problems in statistics and machine learning providing a motivating focus. We will discuss connections between convex optimization and regret minimization, both with stochastic and deterministic feedback. We will view these problems through the minimax lens and show how algorithms emerge as approximate dynamic programming solutions. Finally, we will review robust optimization and explore the interactions between robustness and regularization.

 LP/SDP Hierarchies and Sum of Squares Proofs 3

LP/SDP Hierarchies and Sum of Squares Proofs 3

Speaker: Pablo Parrilo, MIT and Ankur Moitra, MIT

In these introductory lectures we will present a unified introduction to Semidefinite Programming hierarchies and Sum of Squares techniques for continuous/discrete optimization, highlighting their many different and complementary interpretations (Lagrangian/algebraic duality, geometric embeddings, proof systems, probabilistic, etc). We will concisely summarize the state of the art in both positive and negative results (e.g., planted clique, tensor completion, constraint satisfaction), as well as current algorithmic approaches.

 LP/SDP Hierarchies and Sum of Squares Proofs 4

LP/SDP Hierarchies and Sum of Squares Proofs 4

Speaker: Pablo Parrilo, MIT and Ankur Moitra, MIT

In these introductory lectures we will present a unified introduction to Semidefinite Programming hierarchies and Sum of Squares techniques for continuous/discrete optimization, highlighting their many different and complementary interpretations (Lagrangian/algebraic duality, geometric embeddings, proof systems, probabilistic, etc). We will concisely summarize the state of the art in both positive and negative results (e.g., planted clique, tensor completion, constraint satisfaction), as well as current algorithmic approaches.

 Extended Formulations 1

Extended Formulations 1

Speaker: Thomas Rothvoß, University of Washington; Prasad Raghavendra, UC Berkeley; and Hamza Fawzi, University of Cambridge

In this tutorial we will cover the recent progress on lower bounds on the size of linear programs and semidefinite programs for combinatorial optimization problems. We will present the definition and motivation of extension complexity and the relation to communication complexity. Then we will discuss the lower bound of Fiorini et al for the TSP and correlation polytope. We will also review SDP extension complexity with related concept such as the SDP rank of matrices. Finally, we will discuss lower bounds based on Fourier-methods by CLRS and LRS for both the LP model and the SDP model.

 Extended Formulations 2

Extended Formulations 2

3:00 pm – 4:00 pm

Speaker: Thomas Rothvoß, University of Washington; Prasad Raghavendra, UC Berkeley; and Hamza Fawzi, University of Cambridge

In this tutorial we will cover the recent progress on lower bounds on the size of linear programs and semidefinite programs for combinatorial optimization problems. We will present the definition and motivation of extension complexity and the relation to communication complexity. Then we will discuss the lower bound of Fiorini et al for the TSP and correlation polytope. We will also review SDP extension complexity with related concept such as the SDP rank of matrices. Finally, we will discuss lower bounds based on Fourier-methods by CLRS and LRS for both the LP model and the SDP model.

 Robustness, Stochastics, Uncertainty 3

Robustness, Stochastics, Uncertainty 3

Speaker: Sasha Rakhlin, University of Pennsylvania; Ben Recht, UC Berkeley; and Laurent El Ghaoui, UC Berkeley

In this session, we will provide an overview of stochastic and robust optimization, with problems in statistics and machine learning providing a motivating focus. We will discuss connections between convex optimization and regret minimization, both with stochastic and deterministic feedback. We will view these problems through the minimax lens and show how algorithms emerge as approximate dynamic programming solutions. Finally, we will review robust optimization and explore the interactions between robustness and regularization.

 Extended Formulations 3

Extended Formulations 3

Speaker: Thomas Rothvoß, University of Washington; Prasad Raghavendra, UC Berkeley; and Hamza Fawzi, University of Cambridge

In this tutorial we will cover the recent progress on lower bounds on the size of linear programs and semidefinite programs for combinatorial optimization problems. We will present the definition and motivation of extension complexity and the relation to communication complexity. Then we will discuss the lower bound of Fiorini et al for the TSP and correlation polytope. We will also review SDP extension complexity with related concept such as the SDP rank of matrices. Finally, we will discuss lower bounds based on Fourier-methods by CLRS and LRS for both the LP model and the SDP model.

 Extended Formulations 4

Extended Formulations 4

Speaker: Thomas Rothvoß, University of Washington; Prasad Raghavendra, UC Berkeley; and Hamza Fawzi, University of Cambridge

In this tutorial we will cover the recent progress on lower bounds on the size of linear programs and semidefinite programs for combinatorial optimization problems. We will present the definition and motivation of extension complexity and the relation to communication complexity. Then we will discuss the lower bound of Fiorini et al for the TSP and correlation polytope. We will also review SDP extension complexity with related concept such as the SDP rank of matrices. Finally, we will discuss lower bounds based on Fourier-methods by CLRS and LRS for both the LP model and the SDP model.

 Interior Point Methods 1

Interior Point Methods 1

Speaker: Steve Wright, University of Wisconsin-Madison; Aaron Sidford, Stanford University; and Aleksander Mądry, MIT

Interior point methods are one of the key approaches to solving linear programming formulations as well as other convex programs. They give rise to algorithms that not only are the fastest ones known from asymptotic analysis point of view but also are often superior in practice.
This series of four lectures will present fundamentals of interior point methods as well as touch on the key ideas and concepts behind some of the recent developments. The topics we plan to cover include: (1) background on linear programming optimality conditions, the central path and its neighborhoods, and Newton's method; (2) complete analysis of a primal-dual path-following algorithm for linear programming and its relationship to a basic primal barrier method; (3) how to perturb central path to speed up convergence of an interior point method; and (4) a variant of interior point method that achieves running times that scales with the intrinsic dimension of the problem (rather than its possibly larger standard representation).
No previous experience with interior point methods is required.

 Interior Point Methods 2

Interior Point Methods 2

Speaker: Steve Wright, University of Wisconsin-Madison; Aaron Sidford, Stanford University; and Aleksander Mądry, MIT

Interior point methods are one of the key approaches to solving linear programming formulations as well as other convex programs. They give rise to algorithms that not only are the fastest ones known from asymptotic analysis point of view but also are often superior in practice.
This series of four lectures will present fundamentals of interior point methods as well as touch on the key ideas and concepts behind some of the recent developments. The topics we plan to cover include: (1) background on linear programming optimality conditions, the central path and its neighborhoods, and Newton's method; (2) complete analysis of a primal-dual path-following algorithm for linear programming and its relationship to a basic primal barrier method; (3) how to perturb central path to speed up convergence of an interior point method; and (4) a variant of interior point method that achieves running times that scales with the intrinsic dimension of the problem (rather than its possibly larger standard representation).
No previous experience with interior point methods is required.

 Interior Point Methods 3

Interior Point Methods 3

Speaker: Steve Wright, University of Wisconsin-Madison; Aaron Sidford, Stanford University; and Aleksander Mądry, MIT

Interior point methods are one of the key approaches to solving linear programming formulations as well as other convex programs. They give rise to algorithms that not only are the fastest ones known from asymptotic analysis point of view but also are often superior in practice.
This series of four lectures will present fundamentals of interior point methods as well as touch on the key ideas and concepts behind some of the recent developments. The topics we plan to cover include: (1) background on linear programming optimality conditions, the central path and its neighborhoods, and Newton's method; (2) complete analysis of a primal-dual path-following algorithm for linear programming and its relationship to a basic primal barrier method; (3) how to perturb central path to speed up convergence of an interior point method; and (4) a variant of interior point method that achieves running times that scales with the intrinsic dimension of the problem (rather than its possibly larger standard representation).
No previous experience with interior point methods is required.

 Continuous Methods 3

Continuous Methods 3

Speaker: Lorenzo Orecchia, Boston University; Maryam Fazel, University of Washington; and Stefanie Jegelka, MIT

Techniques and insights from convex optimization play an important role in the design of algorithms for discrete optimization, as evidenced by the success of convex relaxations in providing a framework for constructing and analyzing approximation algorithms. In the last decade, iterative methods from convex optimization have served as a springboard to a number of algorithmic advances for many discrete optimization tasks, including fundamental ones such as submodular optimization and maximum flow problems.
In this bootcamp series, we will provide a walk-through of the continuous approach to algorithm design in discrete optimization. We will consider the algorithmic challenges that arise in the choice of formulation and iterative algorithm by casting first-order methods as discretizations of continuous-time dynamics. We will see that the non-smooth nature of discrete optimization problems leads us to smoothen our objectives via regularization and discuss how different choices of regularizers arise in different settings. We will then put these principles to work in the contexts of submodular optimization and competitive analysis of online algorithms.

 Continuous Methods 4

Continuous Methods 4

Speaker: Lorenzo Orecchia, Boston University; Maryam Fazel, University of Washington; and Stefanie Jegelka, MIT

Techniques and insights from convex optimization play an important role in the design of algorithms for discrete optimization, as evidenced by the success of convex relaxations in providing a framework for constructing and analyzing approximation algorithms. In the last decade, iterative methods from convex optimization have served as a springboard to a number of algorithmic advances for many discrete optimization tasks, including fundamental ones such as submodular optimization and maximum flow problems.
In this bootcamp series, we will provide a walk-through of the continuous approach to algorithm design in discrete optimization. We will consider the algorithmic challenges that arise in the choice of formulation and iterative algorithm by casting first-order methods as discretizations of continuous-time dynamics. We will see that the non-smooth nature of discrete optimization problems leads us to smoothen our objectives via regularization and discuss how different choices of regularizers arise in different settings. We will then put these principles to work in the contexts of submodular optimization and competitive analysis of online algorithms.

 Interior Point Methods 4

Interior Point Methods 4

Speaker: Steve Wright, University of Wisconsin-Madison; Aaron Sidford, Stanford University; and Aleksander Mądry, MIT

Interior point methods are one of the key approaches to solving linear programming formulations as well as other convex programs. They give rise to algorithms that not only are the fastest ones known from asymptotic analysis point of view but also are often superior in practice.
This series of four lectures will present fundamentals of interior point methods as well as touch on the key ideas and concepts behind some of the recent developments. The topics we plan to cover include: (1) background on linear programming optimality conditions, the central path and its neighborhoods, and Newton's method; (2) complete analysis of a primal-dual path-following algorithm for linear programming and its relationship to a basic primal barrier method; (3) how to perturb central path to speed up convergence of an interior point method; and (4) a variant of interior point method that achieves running times that scales with the intrinsic dimension of the problem (rather than its possibly larger standard representation).
No previous experience with interior point methods is required.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Videos: Structured Regularization for High-Dimensional Data Analysis: Submodular Functions,computing the Non-computable via sparsity, the SDP approach to graph clustering, the hidden clique problem, robust deconvolution

The Summer School "Structured Regularization for High-Dimensional Data Analysis" is on-going in Paris right now at IHP Paris. Here are some of the videos of the second and third day (Tuesday and Wednesday) with Anders Hansen , Andrea Montanari, Francis Bach and Carlos Fernandez-Granda

On foundational computation problems in l1 and TV regularization
A.Hansen - 3/4 - 20/06/2017



Computing the Non-computable via sparsity
On foundational computation barriers in l1 and TV regularization
A.Hansen - 4/4 - 20/06/2017

Submodular Functions: from Discrete to Continuous Domains , Francis Bach (INRIA)

Abstract: Submodular set-functions have many applications in combinatorial optimization, as they can be minimized and approximately maximized in polynomial time. A key element in many of the algorithms and analyses is the possibility of extending the submodular set-function to a convex function, which opens up tools from convex optimization. Submodularity goes beyond set-functions and has naturally been considered for problems with multiple labels or for functions defined on continuous domains, where it corresponds essentially to cross second-derivatives being nonpositive. In this talk, I will show that most results relating submodularity and convexity for set-functions can be extended to all submodular functions. In particular, (a) I will naturally define a continuous extension in a set of probability measures, (b) show that the extension is convex if and only if the original function is submodular, (c) prove that the problem of minimizing a submodular function is equivalent to a typically non-smooth convex optimization problem. Most of these extensions from the set-function situation are obtained by drawing links with the theory of multi-marginal optimal transport, which provides also a new interpretation of existing results for set-functions. I will then provide practical algorithms to minimize generic submodular functions on discrete domains, with associated convergence rates, and an application to proximal operators for non-convex penalty functions. Preprint available here.

Andrea Montanari (Stanford): The semidefinite programming approach to graph clustering.

Andrea Montanari (Stanford): Local algorithms and graphical models. The hidden clique problem.

Carlos Fernandez-Granda (NYU): A sampling theorem for robust deconvolution

Abstract: In the 70s and 80s geophysicists proposed using l1-norm regularization for deconvolution problem in the context of reflection seismology. Since then such methods have had a great impact in high-dimensional statistics and in signal-processing applications, but until recently their performance on the original deconvolution problem was not well understood theoretically. In this talk we provide an analysis of optimization-based methods for the deconvolution problem, including results on irregular sampling and sparse corruptions that highlight the modeling flexibility of these techniques.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Videos: Structured Regularization for High-Dimensional Data Analysis: Compressed Sensing: Structure and Imaging & Matrix and graph estimation

The Summer School "Structured Regularization for High-Dimensional Data Analysis" is on-going in Paris right now at IHP Paris. Here are some of the videos of the first day (Monday) with Anders Hansen and Andrea Montanari

Lectures 1: Compressed Sensing: Structure and Imaging

   

 Lectures 2: Compressed Sensing: Structure and Imaging Anders Hansen (Cambridge) 

Lectures 1 and 2: Compressed Sensing: Structure and Imaging Abstract: The above heading is the title of a new book to be published by Cambridge University Press. In these lectures I will cover some of the main issues discussed in this monograph/textbook. In particular, we will discuss how the key to the success of compressed sensing applied in imaging lies in the structure. For example images are not just sparse in an X-let expansion, they have a very specific sparsity structure in levels according to the X-let scales. Similarly, when considering Total Variation, the gradient coefficients are also highly structured. Moreover, in most realistic sampling scenarios, the sampling operator combined with any X-let transform yields a matrix with a very specific coherence structure. The key to successfully use compressed sensing is therefore to understand how to utilise these structures in an optimal way, in particular in the sampling procedure. In addition, as the coherence and sparsity structures have very particular asymptotic behaviour, the performance of compressed sensing varies greatly with dimension, and so does the optimal way of sampling. Fortunately, there is now a developed theory that can guide the user in detail on how to optimise the use of compressed sensing in inverse and imaging problems. I will cover several of the key aspects of the theory accompanied with real-world examples from Magnetic Resonance Imaging (MRI), Nuclear Magnetic Resonance (NMR), Surface Scattering, Electron Microscopy, Fluorescence Microscopy etc. Recommended readings: (lectures 1 and 2) Chapter 4, 6 and 12 in “A mathematical introduction to compressed sensing” (Foucard/Rauhut) Breaking the coherence barrier: A new theory for compressed sensing On asymptotic structure in compressed sensing Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames

   

Andrea Montanari (Stanford): Matrix and graph estimation 

 Abstract: Many statistics and unsupervised learning problems can be formalized as estimating a structured matrix or a graph from noisy or incomplete observations. These problems present a large variety of challenges, and an intriguing interplay between computational and statistical barriers. I will provide an introduction to recent work in the area, with an emphasis on general methods and unifying themes. 1) Random matrix theory and spectral methods. 2) The semidefinite programming approach to graph clustering. 3) Local algorithms and graphical models. The hidden clique problem. 4) Non-negative matrix factorization.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Saturday Morning Video: Randomized Algorithms in Linear Algebra, Ravi Kannan @ COLT2016

 

As Sebastien pointed out the COLT 2016 videos are out. Here is one: Ravi Kannan on Randomized Algorithms in Linear Algebra 

  Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Video: P vs. NP and the Computational Complexity Zoo

We hear about these things every so often through the phase transitions (and the map makers who find them) that such and such algorithms display but I caught this introduction to complexity on my twitter feed this morning, and it's worth watching it. Here it is:

 P vs. NP and the Computational Complexity Zoo (The Complexity Zoo is here) 

h/t Hannah Fry

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Video: Sparse Identification of Nonlinear Dynamics (SINDy)

We mentioned the approach earlier in Discovering governing equations from data: Sparse identification of nonlinear dynamical systems - implementation - but Steve sent me the following as an add-on:

 Hi Igor,

I am attaching a link to a youtube video abstract of our recent paper on sparse identification of nonlinear dynamics (SINDy) in PNAS.  Hope you enjoy, and please feel free to share with anyone who may be interested.

Also, I saw that you mentioned our algorithm on your blog — thanks very much!!  It is awesome to hear the others like the work.

   Video abstract:  https://www.youtube.com/watch?v=gSCa78TIldg
   Paper [open access]:  http://www.pnas.org/content/113/15/3932.abstract

Best Regards,
Steve

Thanks  Steve ! Here is the video:

 

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Saturday Morning Videos: ICML 2015 in Lille

All the videos of all the talks at ICML were just released this week. Enjoy !

http://videolectures.net/icml2015_lille/

Here are a few I had not noticed before. On average they last about 15 to 20 minutes:

• Theory of Dual-sparse Regularized Randomized Reduction Tianbao Yang
• Guaranteed Tensor Decomposition: A Moment Approach Gongguo Tang  
• PU Learning for Matrix Completion Cho-Jui Hsieh  
• Low-Rank Matrix Recovery from Row-and-Column Affine Measurements Avishai Wagner  
• Intersecting Faces: Non-negative Matrix Factorization With New Guarantees James Y. Zou  
•  CUR Algorithm for Partially Observed Matrices Miao Xu  
• An Explicit Sampling Dependent Spectral Error Bound for Column Subset Selection Tianbao Yang 
• Swept Approximate Message Passing for Sparse Estimation Eric W. Tramel  
• Towards a Lower Sample Complexity for Robust One-bit Compressed Sensing Rongda Zhu  
• Sparse Subspace Clustering with Missing Entries René Vidal   
• Safe Subspace Screening for Nuclear Norm Regularized Least Squares Problems Qiang Zhou  
• Complete Dictionary Recovery Using Nonconvex Optimization John Wright  
• Low Rank Approximation using Error Correcting Coding Matrices Shashanka Ubaru  
• A Unified Framework for Outlier-Robust PCA-like Algorithms Wenzhuo Yang 
• Deep Unsupervised Learning using Nonequilibrium Thermodynamics Jascha Sohl-Dickstein
• Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions
  Alina Raluca Ene
• The Power of Randomization: Distributed Submodular Maximization on Massive Datasets Justin Ward
• Improving the Gaussian Process Sparse Spectrum Approximation by Representing Uncertainty in Frequency Inputs Yarin Gal
• Sparse Variational Inference for Generalized GP ModelsRishit Sheth
• A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-reduced Data Yining Wang  
• Stay on path: PCA along graph paths Megasthenis Asteris  
• Geometric Conditions for Subspace-Sparse Recovery René Vidal 
• A Convex Optimization Framework for Bi-Clustering Huan Xu  
• Multi-Task Learning for Subspace Segmentation Yu Wang  
• Multi-view Sparse Co-clustering via Proximal Alternating Linearized Minimization Jinbo Bi
• Log-Euclidean Metric Learning on Symmetric Positive Definite Manifold with Application to Image Set Classification Bo Xin

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Saturday Morning Videos: IPAM workshop on Computational Photography and Intelligent Cameras

 

 

Here are the videos of the IPAM workshop on Computational Photography and Intelligent Cameras (I haven't had much luck with firefox, but chrome seems to be ok with the low resolution videos):

• David Brady (Duke University) Gigapixel Videography 1080p | 480p | 240p |
• Mohit Gupta (Columbia University) Time-of-Flight Revolution 1080p | 480p | 240p |
• Kristin Dana (Rutgers University) Reflectance Gradients for Material Recognition 1080p | 480p | 240p |
• Patrick Llull (Duke University) Image-space coding of time and focus 1080p | 480p | 240p |
• Paul Debevec (USC Institute for Creative Technologies ) Computational Illumination for lighting real and virtual actors 1080p | 480p | 240p |
• Paolo Favaro (Universität Bern) Total Variation Blind Deconvolution: The Devil is in the Details 1080p | 480p | 240p |
• Richard Baraniuk (Rice University) Everybody Must Get STOne: Video Compressive Sensing
• Yohann Tendero (École Nationale Supérieure de Télécommunications) A mathematical model of a flutter shutter camera 1080p | 480p | 240p |
• Kevin Kelly (Rice University) Practicalities of Imaging by Compressive Sensing 1080p | 480p | 240p |
• William Freeman (Massachusetts Institute of Technology) The world of tiny motions 1080p | 480p | 240p |
• Carlos Fernandez-Granda (Stanford University) Optimization-based sparse recovery: Compressed sensing vs. super-resolution 1080p | 480p | 240p |
• Matthew Nokleby (Duke University) Information Theory and Compressive Sensing 1080p | 480p | 240p |
• Ayan Chakrabarti (Toyota Technological Institute at Chicago ) Low-level Vision by Consensus in a Spatial Hierarchy of Regions 1080p | 480p | 240p |
• Wolfgang Heidrich (King Abdullah Univ. of Science and Technology (KAUST)) Light Transport Analysis using Photonic Mixer Devices 1080p | 480p | 240p |
• Pauline Trouvé (Onera) Codesign of an 3D imaging system based on depth-from-defocus 1080p | 480p | 240p |
• Kari Pulli (Light) FlexISP: A Flexible Camera Image Processing Framework 1080p | 480p | 240p |
• Oliver Cossairt (Northwestern University) Motion Contrast 3D Scanning 1080p | 480p | 240p |
• Neus Sabater (Technicolor) Disparity guided demosaicking of plenoptic data
• Ashok Veeraraghavan (Rice University) Imaging for personalized health 1080p | 480p | 240p |
• Sabine Susstrunk (École Polytechnique Fédérale de Lausanne (EPFL)) Opponent Color Revisited1080p | 480p | 240p |
• Pascal Monasse (École Nationale des Ponts-et-Chaussées) Visualizing level lines and curvature in images 1080p | 480p | 240p |
• Jack Tumblin (Northwestern University) Aggregated Light Measurements by Paired Digital Cameras and Displays 1080p | 480p | 240p |

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.