The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements

The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements by Chrtistos Thrampoulidis, Ehsan Abbasi, Babak Hassibi

Consider estimating an unknown, but structured, signal x0∈Rn from m measurement yi=gi(aTix0), where the ai's are the rows of a known measurement matrix A, and, g is a (potentially unknown) nonlinear and random link-function. Such measurement functions could arise in applications where the measurement device has nonlinearities and uncertainties. It could also arise by design, e.g., gi(x)=sign(x+zi), corresponds to noisy 1-bit quantized measurements. Motivated by the classical work of Brillinger, and more recent work of Plan and Vershynin, we estimate x0 via solving the Generalized-LASSO for some regularization parameter λ>0 and some (typically non-smooth) convex structure-inducing regularizer function. While this approach seems to naively ignore the nonlinear function g, both Brillinger (in the non-constrained case) and Plan and Vershynin have shown that, when the entries of A are iid standard normal, this is a good estimator of x0 up to a constant of proportionality μ, which only depends on g. In this work, we considerably strengthen these results by obtaining explicit expressions for the squared error, for the \emph{regularized} LASSO, that are asymptotically \emph{precise} when m and n grow large. A main result is that the estimation performance of the Generalized LASSO with non-linear measurements is \emph{asymptotically the same} as one whose measurements are linear yi=μaTix0+σzi, with μ=Eγg(γ) and σ2=E(g(γ)−μγ)2, and, γ standard normal. To the best of our knowledge, the derived expressions on the estimation performance are the first-known precise results in this context. One interesting consequence of our result is that the optimal quantizer of the measurements that minimizes the estimation error of the LASSO is the celebrated Lloyd-Max quantizer.

      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.

A Randomized Rounding Algorithm for Sparse PCA

A Randomized Rounding Algorithm for Sparse PCA by Petros Drineas, Kimon Fountoulakis, Abhisek Kundu

We present and analyze a simple, two-step algorithm to approximate the optimal solution of the sparse PCA problem. Our approach first solves a convex l1 relaxation of the NP-hard sparse PCA optimization problem and then uses a randomized rounding strategy to sparsify the resulting dense solution. Our main theoretical result guarantees an additive error approximation and provides a tradeoff between sparsity and accuracy. Our experimental evaluation indicates that our approach is competitive in practice, even compared to state-of-the-art toolboxes such as Spasm.

 
 

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.

A Deep Learning Approach to Structured Signal Recovery

Ali just sent me the following:

Dear Igor,

Recently, we have published a paper in which we have introduced a new approach for signal recovery from compressive measurements based on a deep learning approach.

I was thinking that it might be interesting for you and Nuit Blanche readers. The main point and innovation in our paper is that we can do the signal recovery with a great quality (outperforming almost all of the previous approaches) at least 1000 times faster. More specifically, we can recover an image from its compressive measurements in 0.002 seconds with a great quality.

You can find the paper in here:
http://arxiv.org/abs/1508.04065

Regards,
Ali

 Thanks Ali ! Table 1 and 2 are very telling but I chose to feature figure 8 of the paper as a reminder that the Great convergence will allow results in compressive sensing to yield interesting insights in Deep Learning. In particular, phase transitions are likely to provide good ways to evaluate the capabilities of this or that neural network architectures that ought to go faster than current reconstruction algorithms in compressive sensing (as shown in the following paper). Without further ado: A Deep Learning Approach to Structured Signal Recovery by Ali Mousavi, Ankit B. Patel, Richard G. Baraniuk

In this paper, we develop a new framework for sensing and recovering structured signals. In contrast to compressive sensing (CS) systems that employ linear measurements, sparse representations, and computationally complex convex/greedy algorithms, we introduce a deep learning framework that supports both linear and mildly nonlinear measurements, that learns a structured representation from training data, and that efficiently computes a signal estimate. In particular, we apply a stacked denoising autoencoder (SDA), as an unsupervised feature learner. SDA enables us to capture statistical dependencies between the different elements of certain signals and improve signal recovery performance as compared to the CS approach.

Related:

• Sunday Morning Insight: The Great Convergence ?
• Sunday Morning Insight: Randomization is not a dirty word
• Sunday Morning Insight: Sharp Phase Transitions in Machine Learning ?
• Sunday Morning Insight: Exploring Further the Limits of Admissibility
• Sunday Morning Insight: The Map Makers 
• Sunday Morning Insight: A Quick Panorama of Sensing from Direct Imaging to Machine Learning

    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.

Manitest: Are classifiers really invariant? - implementation -

 As I was reading about IGO and Emmy Noether's theorem, Hussein just sent me the following:

We recently published with Pascal Frossard a paper that introduces a method to quantify the invariance of arbitrary classifiers to geometric transformations. Our method is based on viewing the set of transformed images as a smooth manifold and define our invariance measure as a well-chosen geodesic distance on that manifold. The paper is on the arXiv http://arxiv.org/abs/1507.06535 and the code is available on the project website https://sites.google.com/site/invmanitest/

If you have comments or questions, please let us know! Thanks,

Hussein.

Thanks Hussein! 

 

Manitest: Are classifiers really invariant?  by Alhussein Fawzi, Pascal Frossard

Invariance to geometric transformations is a highly desirable property of automatic classifiers in many image recognition tasks. Nevertheless, it is unclear to which extent state-of-the-art classifiers are invariant to basic transformations such as rotations and translations. This is mainly due to the lack of general methods that properly measure such an invariance. In this paper, we propose a rigorous and systematic approach for quantifying the invariance to geometric transformations of any classifier. Our key idea is to cast the problem of assessing a classifier's invariance as the computation of geodesics along the manifold of transformed images. We propose the Manitest method, built on the efficient Fast Marching algorithm to compute the invariance of classifiers. Our new method quantifies in particular the importance of data augmentation for learning invariance from data, and the increased invariance of convolutional neural networks with depth. We foresee that the proposed generic tool for measuring invariance to a large class of geometric transformations and arbitrary classifiers will have many applications for evaluating and comparing classifiers based on their invariance, and help improving the invariance of existing classifiers.

 

Low-Rank Spectral Optimization - implementation -

Michael just let me know of his recent work and attendant implementation. Thanks Michael !.

Low-Rank Spectral Optimization by Michael Friedlander, Ives Macedo

Various applications in signal processing and machine learning give rise to highly structured spectral optimization problems characterized by low-rank solutions. Two important examples that motivate this work are optimization problems from phase retrieval and from blind deconvolution, which are designed to yield rank-1 solutions. An algorithm is described based on solving a certain constrained eigenvalue optimization problem that corresponds to the gauge dual. Numerical examples on a range of problems illustrate the e ffectiveness of the approach.

The implementation is here: https://www.math.ucdavis.edu/~mpf/2015-spectral-low-rank.html

  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.

Single-sensor multispeaker listening with acoustic metamaterials / Spectral-temporal compressive imaging

The idea of compressive sensing is to project a signal onto a specific basis such that any sparse signal can be recovered with few measurements. From the very beginning, the field has been focused on finding ways of changing the first layer of data acquisition devices. Here are two examples today from the DISP group of David Brady at Duke. One uses a single sensor and 3D printing to enhance  acoustic recording while the other continues earlier work on getting a multispectral video camera on a single camera. wow!

      Single-sensor multispeaker listening with acoustic metamaterials by Yangbo Xie, Tsung-Han Tsai, Adam Konneker, Bogdan-Ioan Popa, David J. Brady, and Steven A. Cummer

Designing a “cocktail party listener” that functionally mimics the selective perception of a human auditory system has been pursued over the past decades. By exploiting acoustic metamaterials and compressive sensing, we present here a single-sensor listening device that separates simultaneous overlapping sounds from different sources. The device with a compact array of resonant metamaterials is demonstrated to distinguish three overlapping and independent sources with 96.67% correct audio recognition. Segregation of the audio signals is achieved using physical layer encoding without relying on source characteristics. This hardware approach to multichannel source separation can be applied to robust speech recognition and hearing aids and may be extended to other acoustic imaging and sensing applications.

I note from the methods,

The design process was aided with a commercial full-wave simulation package COMSOL Multiphysics. Three-dimensional simulations with Pressure Acoustics Module were conducted to extract the frequency responses of all of the waveguides.

Spectral-temporal compressive imaging by Tsung-Han Tsai, Patrick Llull, Xin Yuan, Lawrence Carin, and David Brady

We present a compressive camera that combines mechanical translation and spectral dispersion to compress a multi-spectral, high-speed scene onto a monochrome, video-rate detector. Single-frame reconstructions of 15 spectral channels and 10 temporal frames are reported.

previously we had:

Coded aperture compressive temporal imaging by Patrick Llull, Xuejun Liao, Xin Yuan, Jianbo Yang, David Kittle,Lawrence Carin, Guillermo Sapiro, and David J. Brady

We use mechanical translation of a coded aperture for code division multiple access compression of video. We present experimental results for reconstruction at 148 frames per coded snapshot.

  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.

The inverse fast multipole method: using a fast approximate direct solver as a preconditioner for dense linear systems

If you know the influence the Fast Multipole Method has had on Engineering and Science in the past two decades, you know that any improvement is a big deal. It is nice to see it coming from a decomposition that is not unknown to us. From the paper:

The first step in obtaining such a solver is to exploit the matrix’H2-structure in order to convert the original dense system into an extended sparse system, as solving the latter is more efficient from a computational point of view. The sparsification procedure is based on recursively decomposing a dense matrix into a sparse matrix (representing the “near field” interactions) and a low-rank approximation (representing the “far field” interactions), combined with the introduction of auxiliary variables. This is done in a multilevel fashion. Similar ideas have been considered for HSS matrices in [13,31].

The recursion on that decomposition is not something we have not seen either. It parallels several works featured in Sunday Morning Insight: Matrix Factorizations and the Grammar of Life (of related interest Sunday Morning Insight: Of Fluid Autoencoders and Data Tsunamis). Without further ado, here is: The inverse fast multipole method: using a fast approximate direct solver as a preconditioner for dense linear systems by Pieter Coulier, Hadi Pouransari, Eric Darve

Although some preconditioners are available for solving dense linear systems, there are still many matrices for which preconditioners are lacking, in particular in cases where the size of the matrix N becomes very large. There remains hence a great need to develop general purpose preconditioners whose cost scales well with the matrix size N. In this paper, we propose a preconditioner with broad applicability and with cost O(N) for dense matrices, when the matrix is given by a smooth kernel. Extending the method using the same framework to general H2-matrices is relatively straightforward. These preconditioners have a controlled accuracy (machine accuracy can be achieved if needed) and scale linearly with N. They are based on an approximate direct solve of the system. The linear scaling of the algorithm is achieved by means of two key ideas. First, the H2-structure of the dense matrix is exploited to obtain an extended sparse system of equations. Second, fill-ins arising when performing the elimination are compressed as low-rank matrices if they correspond to well-separated interactions. This ensures that the sparsity pattern of the extended sparse matrix is preserved throughout the elimination, hence resulting in a very efficient algorithm with O(Nlog(1/ε)2) computational cost and O(Nlog1/ε) memory requirement, for an error tolerance 0<ε<1. The solver is inexact, although the error can be controlled and made as small as needed. These solvers are related to ILU in the sense that the fill-in is controlled. However, in ILU, most of the fill-in is simply discarded whereas here it is approximated using low-rank blocks, with a prescribed tolerance. Numerical examples are discussed to demonstrate the linear scaling of the method and to illustrate its effectiveness as a preconditioner.

    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: Summer School on Hashing: Theory and Applications, 2014

Last year, I mentioned the slides of the 2014 Summer School on Hashing: Theory and Applications but Idid not realize they also had videos for the talks. Here they are from this channel. A wonderful summary of these talks was given on the neustar resarch blog (Hitting the Books: EADS Summer School on Hashing ) 

Basics of hashing: k-independence and the impact on applications (by Rasmus Pagh)
by Aikimaify



1:02:16


Bloom filters and their diverse applications (Michael Mitzenmacher)
by Aikimaify



1:27:23


High speed hashing for integers and strings (by Mikkel Thorup)
by Aikimaify



58:18


Dictionaries with implicit keys (by Rasmus Pagh)
by Aikimaify



34:42


Cuckoo hashing and balanced allocations (by Michael Mitzenmacher)
by Aikimaify



1:32:50


Reliable hashing for complex applications (by Mikkel Thorup)
by Aikimaify



1:01:40


WATCHED
Streams, sketching, and databases I (by Graham Cormode)
by Aikimaify



1:21:58


Dimensionality reductions (by Alexander Andoni)
by Aikimaify



1:24:55


Coordinated sampling (Haim Kaplan)
by Aikimaify



1:23:36


Streams, sketching, and databases II (by Graham Cormode)
by Aikimaify



1:27:03


Locality senitive hashing (Alexander Andoni)
by Aikimaify



1:34:18


Hashing in machine learning (by John Langford)
by Aikimaify



1:12:28


Hashing Algorithms for Efficient Search, Learning, and Compressed Sensing (Workshop by Ping Li)
by Aikimaify



1:35:09


Cell probe lower bounds for approximate near neighbor search with Bregman divergences
by Aikimaify

  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: Machine Learning with Scikit Learn, Andreas Mueller & Kyle Kastner, SciPy 2015 Tutorial

Beware, the two parts of this tutorial by Andreas Mueller and Kyle Kastner lasts 6 hours in all:

 

All material is here: https://github.com/amueller/scipy_2015_sklearn_tutorial

Outline

Morning Session

• What is machine learning? (Sample applications)
• Kinds of machine learning: unsupervised vs supervised.
• Data formats and preparation.
• Supervised learning
  • Interface
  • Training and test data
  • Classification
  • Regression
• Unsupervised Learning
  • Unsupervised transformers
  • Preprocessing and scaling
  • Dimensionality reduction
  • Clustering
• Summary : Estimator interface
• Application : Classification of digits
• Application : Eigenfaces
• Methods: Text feature abstraction, bag of words
• Application : SMS spam detection
• Summary : Model building and generalization

Afternoon Session

• Cross-Validation
• Model Complexity: Overfitting and underfitting
• Complexity of various model types
• Grid search for adjusting hyperparameters
• Basic regression with cross-validation
• Application : Titanic survival with Random Forest
• Building Pipelines
  • Motivation and Basics
  • Preprocessing and Classification
  • Grid-searching Parameters of the feature extraction
• Application : Image classification
• Model complexity, learning curves and validation curves
• In-Depth supervised models
  • Linear Models
  • Kernel SVMs
  • trees and Forests
• Learning with Big Data
  • Out-Of-Core learning
  • The hashing trick for large text corpuses

    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.

Slides; Deep Learning Summer School 2015

 

 

Figure from Adam Coates's Systems issues and distributed training presentation

 

Here are some of the slides presented at the Deep Learning Summer School 2015. Enjoy !

Day 1, Mon, Aug 3

Pascal Vincent: Intro to ML (9:00-10:30) 

Yoshua Bengio: Theoretical motivations for Representation Learning & Deep Learning (11:00-12:30) 

Leon Bottou: Intro to multi-layer nets (2:00-3:30) 

Day 2, Tue, Aug 4

Hugo Larochelle: Neural nets and backprop (9:00-10:30) 

Leon Bottou: Numerical optimization and SGD, Structured problems & reasoning (11:00-12:30) 

Hugo Larochelle: Directed Graphical Models and NADE (2:00-3:30) 

Intro to Theano (4:00-5:30)

Day 3, Wed, Aug 5

Aaron Courville: Intro to undirected graphical models (9:00-10:30) 

Honglak Lee: Stacks of RBMs (11:00-12:30) 

Pascal Vincent: Denoising and contractive auto-encoders, manifold view (2:00-3:30) 

GPU Programming (4:00-5:30)

Day 4, Th, Aug 6

Roland Memisevic: Visual features (9:00-10:30) 

Honglak Lee: Convolutional networks (11:00-12:30) 

Graham Taylor: Learning similarity  (2:00-3:30) 

Day 5, Fri, Aug 7

Chris Manning: NLP 101 (9:00-10:30) 

Graham Taylor: Modeling human motion, pose estimation and tracking  (11:00-12:30) 

Chris Manning: NLP / Deep Learning (2:00-3:30) 

Theano programming, datasets with Fuel (4:00-5:30)

Day 6, Sat, Aug 8

Ruslan Salakhutdinov: Deep Boltzmann Machines (9:00-10:30) 

Adam Coates: Speech recognition with deep learning (11:00-12:30) 

Ruslan Salakhutdinov: Multi-modal models (2:00-3:30) 

Day 7, Sun, Aug 9

Ian Goodfellow: Structure of optimization problems (9:00-10:30) 

Adam Coates: Systems issues and distributed training (11:00-12:30) 

Ian Goodfellow: Adversarial examples (2:00-3:30) 

Day 8, Mon, Aug 10

Phil Blunsom: From language modeling to machine translation (9:00-10:30) 

Richard Socher: Recurrent neural networks  (11:00-12:30) 

Phil Blunsom: Memory, Reading, and Comprehension (2:00-3:30) 

Theano debugging tools, conv. nets (4:00-5:30)

Day 9, Tue, Aug 11

Richard Socher: DMN for NLP (9:00-10:30) 

Mark Schmidt: Smooth, Finite, and Convex Optimization (11:00-12:30) 

Roland Memisevic: Visual Features II (2:00-3:30)

Theano implementation of iterations (scan), RNNs (4:00-5:30)

Day 10, Wed, Aug 12

Mark Schmidt: Non-Smooth, Non-Finite, and Non-Convex Optimization (9:00-10:30) 

Aaron Courville: VAEs and deep generative models for vision (11:00-12:30) 

Yoshua Bengio: Generative models from auto-encoders (2:00-3:30) 

Theano programming: overflow session (4:00-5:00)

 

  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.