## Friday, March 07, 2014

### Videos: NIPS 2013 Frank-Wolfe and Greedy Algorithms

Introduction to the Workshop

Ben Recht - The Algorithmic Frontiers of Atomic Norm Minimization - invited talk
Francis Bach - Conditional Gradients Everywhere - invited talk
Katya Scheinberg - Complexity of Inexact Proximal Newton Methods
Shai Shalev-Schwartz - Efficiently Training Sum-Product Neural Networks - invited talk
Paul Grigas - New Analysis and Results for the Conditional Gradient Method
Nikhil Rao - Conditional Gradient with Enhancement and Truncation for Atomic Norm Regularization
Jacob Steinhardt - A Greedy Framework for First-Order Optimization
Vamsi K. Potluru - Coordinate Descent for mixed-norm NMF

Simon Lacoste-Julien - An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms
David Belanger - Marginal Inference in MRFs using Frank-Wolfe
Ali Ghodsi - A Fast Greedy Algorithm for Generalized Column Subset Selection
Robert M. Freund - Remarks on Frank-Wolfe and Structural Friends - invited talk

Join the CompressiveSensing subreddit or the Google+ Community 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.

## Thursday, March 06, 2014

### CSjob: Post-Doc, Compressed Sensing Imaging through Multiply Scattering Materials, Paris, France

Laurent Daudet just sent me this postdoc announcement, I usually don't add up to it, but this one is special:

An 18-month post-doc position is available in Paris, France, on the subject of Compressed Sensing Imaging through multiply scattering materials.
The goal of this post-doc is to develop signal processing algorithms for compressed-sensing imaging through multiple scattering materials. This is a joint project between ESPCI ParisTech (Institut Langevin, Prof. Laurent Daudet) and Ecole Normale Supérieure (LKB, Prof. Sylvain Gigan ; and LPS, Prof. Florent Krzakala), funded by a grant from PSL Research University.
Our proof of concept (arXiv 1309.0425) has shown experimentally that compressed-sensing imaging through multiple scattering materials is indeed possible, despite strong experimental noise. This technique can be improved in many ways, for instance in its calibration procedure, by using intensity-only measurements, or by scaling up the resolution of the images - each of these challenges requiring speciﬁc model-based algorithmic developments. Primarily based at Institut Langevin (L. Daudet's team), the hired researcher will have frequent interaction with experimentalists at S. Gigan's optics team, and statistical physics / signal processing researchers of F. Krzakala's team at LPS, all within 10 minutes walk.
Candidates should hold a PhD in Signal processing, Applied mathematics, Computational optics or related domain, with some mandatory experience in sparse representations and/or compressed sensing. Good programming skills (Matlab), the ability to work independently, and good reporting skills are required. The ability to interact with physics experimentalists (acoustics / optics) and statistical physicists is essential.
Start date : no later than Sept. 1st, 2014. Salary according to experience.Informal enquiries should be made, by email only, to Prof. Laurent Daudet : laurent.daudet[at]espci.fr http://www.institut-langevin.espci.fr/Laurent-Daudet

Formal applications should include a detailed CV, a publications list, a short research statement, the name and email address of up to 3 references, and should be sent simultaneously to laurent.daudet[at]espci.fr, sylvan.gigan[at]espci.fr, ﬂorent.krzakala[at]ens.fr
The Langevin Institute ( http://www.institut-langevin.espci.fr/Langevin-Institute ) is a physics laboratory that investigates all aspects of waves (acoustics / optics), attached to the prestigious ESPCI ParisTech engineering school (7 Nobel prizes in physics and chemistry) and recently created PSL Research University. It is centrally located in the vibrant 5th "arrondissement" of Paris.

Join the CompressiveSensing subreddit or the Google+ Community 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: Marguerite Frank - Inventor of the Frank-Wolfe Algorithm -

Zaid Harchaoui and Martin Jaggi let me know of this particular video from the Frank-Wolfe and Greedy Algorithms  NIPS 2013 Workshop " which your readers might find interesting". Thanks Zaid and Martin

***
Honorary discussion panel with Marguerite Frank:

Nearly 60 years ago, Marguerite Frank and Philip Wolfe published a very interesting paper, while at Princeton university. The 1956 paper introduced the famous Frank-Wolfe algorithm (also known as conditional gradient), and was the very first method for general constrained convex optimization. The importance of the method can hardly be emphasized enough, as it marks a historical tipping point enabling the departure from linear programming, going to more general convex optimization.

The paper is still of great significance today, as it paved the way for various currently important and broadly used optimization algorithms, in particular sparse methods in signal processing and machine learning (including matching pursuit, Lasso and related techniques).

In the honorary discussion panel at the NIPS 2013 workshop, Marguerite Frank gives a personal account of the history of the paper, as well as her inspiring biography as the first woman in a newly emerging field,
today called mathematical optimization.

Frank–Wolfe algorithm on wikipedia

Yaroslav Bulatov just wrote a very nice summary of the presentations made at the Stochastic Gradient Methods 2014 IPAM meeting last week. You need to go read it, I'll wait.

Join the CompressiveSensing subreddit or the Google+ Community 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.

### Scalable methods for nonnegative matrix factorizations of near-separable tall-and-skinny matrices - implementation -

Numerous algorithms are used for nonnegative matrix factorization under the assumption that the matrix is nearly separable. In this paper, we show how to make these algorithms efficient for data matrices that have many more rows than columns, so-called "tall-and-skinny matrices". One key component to these improved methods is an orthogonal matrix transformation that preserves the separability of the NMF problem. Our final methods need a single pass over the data matrix and are suitable for streaming, multi-core, and MapReduce architectures. We demonstrate the efficacy of these algorithms on terabyte-sized synthetic matrices and real-world matrices from scientific computing and bioinformatics.
The attendant implementation is here.

Join the CompressiveSensing subreddit or the Google+ Community 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.

## Wednesday, March 05, 2014

### This is not something you see everyday!

From [smd] ROSES-14 Amendment 4: Eligible TRLs changed for C.12, PICASSO

ROSES-14 Amendment 4 narrows the range of entry technology readiness levels eligible for submission to C.12, Planetary Instrument Concepts for the Advancement of Solar System Observations (PICASSO). The PICASSO Program supports the development of spacecraft-based instrument systems that show promise for use in future planetary missions. The goal of the program is to conduct planetary and astrobiology science instrument feasibility studies, concept formation, proof of concept instruments, and advanced component technology development to the point where they may be proposed in response to the Maturation of Instruments for Solar System Exploration (MatISSE) Program, C.13 of ROSES. Therefore, the proposed instrument system or advanced components must address specific scientific objectives of likely future planetary science missions. The PICASSO Program is intended to enable timely and efficient technology infusion into the MatISSE Program and eventually into flight missions. As such, the entry technology readiness level (TRL) that PICASSO supports is 1-3. Proposals where the entry TRL is 4 or higher are not appropriate for the PICASSO, but should be submitted to C.13, the MatISSE program. The due dates remain unchanged. Step-1 proposals are due September 15, 2014, and Step-2 proposals are due November 14, 2014. On or about March 5, 2014, this Amendment to the NASA Research Announcement "Research Opportunities in Space and Earth Sciences (ROSES) 2014" (NNH14ZDA001N) will be posted on the NASA research opportunity homepage at http://nspires.nasaprs.com/ and will appear on the RSS feed at:http://nasascience.nasa.gov/researchers/sara/grant-solicitations/roses-2014
If you wonder what TRL 1 through 3 means check the wikipedia page.

Join the CompressiveSensing subreddit or the Google+ Community 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.

### CSjob: PhD Thesis, Signal processing and signal fusion methods for irregularly sampled signals obtained with crowd-sensing. Application to air quality monitoring.

Matthieu PUIGT just sent me the following:
Dear Igor,

Gilles Roussel (http://www-lisic.univ-littoral.fr/spip.php?article50&membre=41), Gilles Delmaire (http://www-lisic.univ-littoral.fr/spip.php?article50&membre=15) and I (http://www-lisic.univ-littoral.fr/~puigt/) are looking for a Ph.D. student. The successful candidate will work on semi-blind sensor calibration and data assimilation, applied to crowd-sensing. As the subject is related to some fields of interest of the Nuit blanche and the Wondering Star readers, I would really appreciate if you could forward the following advertisement on your blogs.

Best regards,
Matthieu

Here is the announcement:

------------------------------
-------------------------------------------
We have a new opening for a signal processing Ph.D. student position, at LISIC, ULCO, located in Calais, France. Some details for the position follow. This info is also available at the following link:

http://www-lisic.univ-littoral.fr/~puigt/jobs_opening.html
-------------------------------------------------------------------------

Signal processing and signal fusion methods for irregularly sampled signals obtained with crowd-sensing. Application to air quality monitoring.

Descrition:

This PhD thesis will focus on semi-blind sensor calibration and on data assimilation, from data irregularly sampled in time and space. The proposed approaches will be tested in the framework of air quality monitoring by citizen sensing (crowd-sensing).

Crowd-sensing refers to the use of an important and diffuse group of people, connected via their smartphones which are sensing information about their environment. The sensed data are transmitted to a server which merges them. Indeed, smartphones may be viewed as acquisition devices since they contain a GPS, a compass, accelerometers, camera(s), microphones, wireless connections (WIFI, Bluetooth, etc) and can be connected to external devices. By encouraging people to measure the levels of air pollutants through an ad-hoc acquisition device, and by using the GPS geolocation data, we will get a database to be processed, e.g., using advanced matrix factorization approaches and data assimilation methods.

In particular, the work performed during this Ph.D. thesis will consist of:
• proposing semi-blind calibration approaches for an heterogeneous sensor network, where the measure uncertainties due to the accuracy of the sensors will be considered,
• developing fusion methods for irregularly sampled data, using semi-physical assimilation or matrix factorization.
This Ph.D. thesis will be done in the LISIC lab (http://www-lisic.univ-littoral.fr/), in Calais, France, in collaboration with the Spirals project-team (Inria Lille - Nord Europe) which will provide its APISENSE crowd-sensing software platform (http://www.apisense.fr/).

From the application point of view, the proposed methods will be tested in the framework of a collaboration with the following French associations:
1. ATMO Nord-Pas de Calais (http://www.atmo-npdc.fr/home.htm), which is in charge to monitor the air quality in the Nord-Pas de Calais country (Northern French country),
2. Bâtisseurs d'Economie Solidaire (http://www.ecozone-littoral.fr/), which will deploy the air sensing devices.

Eligibility:

The successful candidate should have an M.Sc. in computer science, electrical engineering, applied mathematics, or a related field. She / he should get a significant programming experience in Matlab and/or C/C++. An experience in matrix factorization, sparse approximation, or compressed sensing would be a plus.

The potential candidate is invited to contact the supervisors before May 1st 2014. She or he should provide a CV, a cover letter, the marks and ranks obtained during the graduate studies (even partially if the M.Sc is not yet defended), and two recommendation letters (or at least the names of two referents).

Keywords:

semi-blind sensor calibration, data assimilation, matrix factorization, sparsity, non-negativity, crowd-sensing, air quality monitoring.

Related work which was previously investigated in the research group:

[1] G. Roussel, L. Bourgois, M. Benjelloun, G. Delmaire, "Estimation of a semi-physical GLBE model using dual EnKF learning algorithm coupled with a sensor network design strategy: application to air field monitoring," Elsevier, Information Fusion 14 (2013), pp. 335-348, http://dx.doi.org/10.1016/j.inffus.2013.03.001

[2] M. Plouvin, A. Limem, M. Puigt, G. Delmaire, G. Roussel, D. Courcot, "Enhanced NMF initialization using a physical model for pollution source apportionment," in Proceedings of the 22nd European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN 2014), Bruges, Belgium, April 23-25, 2014.

[2] A. Limem, G. Delmaire, M. Puigt, G. Roussel, D. Courcot, "Non-negative matrix factorization using weighted Beta divergence and equality constraints for industrial source apportionment," in Proceedings of the 23rd IEEE International Workshop on Machine Learning for Signal Processing (MLSP 2013), Southampton, UK, September 22-25, 2013.

[3] A. Limem, G. Delmaire, G. Roussel, D. Courcot, "Kullback-Leibler NMF Under Linear Equality Constraints. Application to Pollution Source Apportionment," in Proceedings of the International Conference on Information Science Signal Processing and their Applications (ISSPA 2012), Montreal, Canada, July 3-5, 2012.

Contact:

Gilles ROUSSEL (gilles.roussel@lisic.univ-littoral.fr)
Matthieu PUIGT (matthieu.puigt@lisic.univ-littoral.fr)
Gilles DELMAIRE (gilles.delmaire@lisic.univ-littoral.fr)

Join the CompressiveSensing subreddit or the Google+ Community 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.

### Phase Retrieval with Application to Optical Imaging

Afonso has a conversation with Hau-Tieng Wu: Alternating Projections in Phase Retrieval related to the following review that came up on arXiv:

This review article provides a contemporary overview of phase retrieval in optical imaging, linking the relevant optical physics to the information processing methods and algorithms. Its purpose is to describe the current state of the art in this area, identify challenges, and suggest vision and areas where signal processing methods can have a large impact on optical imaging and on the world of imaging at large, with applications in a variety of fields ranging from biology and chemistry to physics and engineering.

## Tuesday, March 04, 2014

### Slides: Greedy Algorithms, Frank-Wolfe and Friends - A modern perspective

Motivation: Greedy algorithms and related first-order optimization algorithms are at the core of many of the state of the art sparse methods in machine learning, signal processing, harmonic analysis, statistics and other seemingly unrelated areas, with very different goals at first sight. Examples include matching pursuit, boosting, greedy methods for sub-modular optimization, structured prediction, and many more. In the field of optimization, the recent renewed interest in Frank-Wolfe/conditional gradient algorithms opens up an interesting perspective towards a unified understanding of these methods, with a big potential to translate the rich existing knowledge about the respective greedy methods between the different fields.
The scope of this workshop is to gather renowned experts working on those algorithms in machine learning, optimization, signal processing, statistics and harmonic analysis, in order to engender a fruitful exchange of ideas and discussions and to push further the boundaries of scalable and efficient optimization for learning problems.

Goals: The goals of the workshop are threefold. First, to provide an accessible review and synthesis of not only recent results but also old-but-forgotten results describing the behavior and performance of the related greedy algorithms. Second, to cover recent advances on extensions of such algorithms relevant to machine learners, such as learning with atomic-norm regularization (Rao et al., 2012; Tewari et al., 2011, Harchaoui et al., 2012), submodular optimization (Bach, 2011), herding algorithms (Chen et al., 2010; Bach et al., 2012), or structured prediction (Lacoste-Julien et al., 2013). One important example of interest here is the study lower bounds as in (Lan, 2013, Jaggi 2013) to better understand the limitations of such greedy algorithms and of sparse methods. Third, the goal is to provide a forum for open problems, and to serve as stepping-stone for cutting-edge research on this family of scalable algorithms for big data problems.

Here are the presentations slides:

7:30 - 7:40amOrganizersIntroduction and Poster SetupSlides ]
7:40 - 8:20amRobert M. FreundRemarks on Frank-Wolfe and Structural FriendsSlides ]
8:20 - 9:00amBen RechtThe Algorithmic Frontiers of Atomic Norm Minimization: Relaxation, Discretization, and Greedy PursuitSlides ]
9:00 - 9:30pmCoffee Break
9:30 - 9:45amNikhil Rao, Parikshit Shah and Stephen WrightConditional Gradient with Enhancement and Truncation for Atomic Norm RegularizationSlides ]
9:45 - 9:55amHector Allende, Emanuele Frandi, Ricardo Nanculef, Claudio SartoriPairwise Away Steps for the Frank-Wolfe Algorithm
9:55 - 10:05amSimon Lacoste-Julien and Martin JaggiAn Affine Invariant Linear Convergence Analysis for Frank-Wolfe AlgorithmsSlides ]
10:05 - 10:15amVamsi Potluru, Jonathan Le Roux, Barak Pearlmutter, John Hershey and Matthew BrandCoordinate Descent for mixed-norm NMF
Slides ]
10:15 - 10:30amRobert M. Freund and Paul GrigasNew Analysis and Results for the Conditional Gradient MethodSlides ]
10:30 - 3:30pmLunch Break
3:30 - 3:45pmMarguerite FrankHonorary Guest
3:45 - 4:25pmShai Shalev-SchwartzEfficiently Training Sum-Product Neural Networks using Forward Greedy SelectionSlides ]
4:25 - 4:40pmXiaocheng Tang and Katya ScheinbergComplexity of Inexact Proximal Newton MethodsSlides ]

Vladimir TemlyakovFrom Greedy Approximation to Greedy OptimizationSlides ]
4:40 - 4:50pmJacob Steinhardt and Jonathan HugginsA Greedy Framework for First-Order OptimizationSlides ]
4:50 - 5:00pmAhmed Farahat, Ali Ghodsi and Mohamed KamelA Fast Greedy Algorithm for Generalized Column Subset SelectionSlides ]
Poster ]
5:00 - 5:30pmCoffee Break
5:30 - 6:10pmFrancis BachConditional Gradients EverywhereSlides ]
6:10 - 6:25pmDavid Belanger, Dan Sheldon and Andrew McCallumMarginal Inference in MRFs using Frank-WolfeSlides ]

Join the CompressiveSensing subreddit or the Google+ Community 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.

### Introduction into cross approximation / Fast multidimensional convolution in low-rank formats via cross approximation - implementation -

Ivan Oseledets just mentioned the release of a newer algorithm within the TT-toolbox that performs a new Matrix/Tensor Factorization and he calls it the cross approximation From the page:

## Cross approximation: intro

Posted on: 2014-02-26 00:00:00

### Skeleton decomposition

Cross approximation and skeleton decomposition are one of the basic concepts in our research. It is all about low-rank matrices which appear in many different applications: integral equations, tensor approximations and many others. Cross approximation is simple and elegant, but it is not widely known as it should be. Suppose that an n×m matrix A has rank r. Then it can be exactly recovered from r columns and r rows as
A=CAˆ1R,
where C are r columns of AR are r rows of A and Aˆ is a submatrix on their intersection. That means, that only (n+m)relements are required. What about the stability of this decomposition? Suppose A can be approximated with low rank only approximately:
A=Ar+E,
with ∥E∥=ε. How to select an good submatrix. A good guide is the maximum volume : among all r×r submatrices select the one that has largest volume, i.e. the maximum absolute value of the determinant. Then, the corresponding approximation
AAmaxvolC(r+1)σr+1,
where σr+1 is the (r+1)-th singular value of A and the error is measured in the Chebyshev norm (maximum absolute value).

### Cross approximation

A good question is how to compute (quasi)-optimal submatrices. One the possibility is the cross approximation algorithm, which is equivalent to the Gaussian elimination. The steps of the algorithm are simple:
1. Find some pivot (i′,j′)
2. Subtract a rank-1 cross from the matrix: Aij:=Aij−Aij′Ai′jAi′j′.
3. Cycle until the norm of A is small enough.
Different pivoting strategies are possible. The full pivoting assumes that (i′,j′) maximizes the absolute value of the residue. This involves O(nm) complexity and is unacceptable. Partial pivoting can be different: from the simplest row pivoting scheme to rook schemes and random sampling.

### Maximum-volume

Maximum-volume principle is the cornerstone of the low-rank approximation algorithms. Although it is often claimed that maximum-volume submatrix is hard to compute, there are very efficient algorithms for doing that. Maybe the most promiment one is the algorithm that computes a maximum-volume submatrix in a tall n×r matrix. It is an iterative algorithm: it starts from a non-singular r×r submatrix and then substitutes one row at a step (greedy approach). For this problem, the convergence is very fast. There are few tricks to make it really efficient. The efficient implementations of the maxvol algorithm are available both in the matlab and Python version of the tt-Toolbox.
From the code page:
Tensor trains
The basic operations with tensors in Tensor Train (tt) format have been implemented in
Block low-rank approximation techniques for large dense matrices
the latest arxiv shows one use of it:

Fast multidimensional convolution in low-rank formats via cross approximation by M. V. Rakhuba, I. V. Oseledets

We propose a new cross-conv algorithm for approximate computation of convolution in different low-rank tensor formats (tensor train, Tucker, Hierarchical Tucker). It has better complexity with respect to the tensor rank than previous approaches. The new algorithm has a high potential impact in different applications. The key idea is based on applying cross approximation in the "frequency domain", where convolution becomes a simple elementwise product. We illustrate efficiency of our algorithm by computing the three-dimensional Newton potential and by presenting preliminary results for solution of the Hartree-Fock equation on tensor-product grids.

Join the CompressiveSensing subreddit or the Google+ Community 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.