Democratic Representations

You probably recall an implementation of an l_infinity solver back in 2011, there are now two new algorithms to perform those reconstructions. No word yet on where they are located. Let us note the effective appearance of a new kind of sharp phase transition with a democratic proxy on the y-axis and the fact that it opens the door to other empirical approaches investigating other norms and attendant of signals/phase transitions. Without further due, here is the paper:

 

Democratic Representations by Christoph Studer, Tom Goldstein, Wotao Yin, Richard G. Baraniuk

Minimization of the $\ell_\infty$ (or maximum) norm subject to a constraint that imposes consistency to an underdetermined system of linear equations finds use in a large number of practical applications, including vector quantization, peak-to-average power ratio (PAPR) (or "crest factor") reduction in communication systems, approximate nearest neighbor search, and peak force minimization in robotics and control. This paper analyzes the fundamental properties of signal representations obtained by solving such a convex optimization problem. We develop bounds on the maximum magnitude of such representations using the uncertainty principle (UP) introduced by Lyubarskii and Vershynin, IEEE Trans. IT, 2010, and study the efficacy of $\ell_\infty$-norm-based PAPR reduction. Our analysis shows that matrices satisfying the UP, such as randomly subsampled Fourier or i.i.d. Gaussian matrices, enable the computation of what we call democratic representations, whose entries all have small and similar magnitude, as well as low PAPR. To compute democratic representations at low computational complexity, we present two new, efficient convex optimization algorithms. We finally demonstrate the efficacy of democratic representations for PAPR reduction in a DVB-T2-based broadcast system.

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.

Paris Machine Learning Meetup #7: Video of the meetup

 

Last night we had the 7th Paris Machine Learning Meetup at DojoEvents. We first had two Skype presentations of crowdfunded projects that are connected to Machine Vision. The Q&As are in English and before watching the video above you want to watch the VMX video introduction which is what the attendees saw before the Hangout started. It is here.

The program:

• Tomasz Malisiewicz, VMX Project: Computer Vision for Everyone (English)
• Allen Yang, Atheer One, what it feels like to have superpowers (English)
• Patrick Perez From image to descriptors and back again (French)
• Kenji Lefèvre-Hasegawa , 'Dataiku Science Studio', What does it take to win the Kaggle/Yandex competition ?  (French)

Links to presentations will come later with a summary of the meetup.

Abstracts:

From image to descriptors and back again , Patrick Perez

The context of this presentation is visual search, with a specific focus on retrieving images similar to a query image. I will first discuss one corner stone of such large-scale systems: aggregation of local descriptors (typically SIFTs) into a fixed-sized image signature. I shall present "Vector of Locally Aggregated Descriptors" (VLAD) which offers a powerful alternative to popular "Bag-of-Word" (BoF) approach. Combined with an efficient indexing system, VLAD can lead to a memory footprint as compact as 16 bytes per image with good approximate search performance. I will then touch upon risks of visual information leakage in such image search systems, showing that human-understandable reconstruction of an image can be obtained from the sparse set of its local descriptors, and no other side information.

What does it take to win the Kaggle/Yandex competition,  Kenji Lefèvre-Hasegawa

I'll give a feedback on the "personnalized web search" Kaggle challenge for which our team won First prize. I will focus the talk on both the experience itself (team work and tools) and the models we've used.

  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.

How Close is Compressive Sensing to Random Features with Random Kitchen Sinks?

I don't know but here is how the authors of [1] describe the Random KitcHen Sinks (RKS) for FastFood which are the non adaptive version of approaches like XNV. RKS seems to be a play on words for Reproducing Kernel Hilbert Spaces that one can use to approximate the identity (i.e. the reproducing property). From [1]

Random Kitchen Sinks (Rahimi & Recht, 2007;2008)1, the algorithm that our algorithm is based on, approximates the function f by means of multiplying the input with a Gaussian random matrix, followed by the application of a nonlinearity. If the expansion dimension is n and the input dimension is d (i.e., the Gaussian matrix is n x d), it requires O(nd) time and memory to evaluate the decision function f. For large problems with sample size mxn, this is typically much faster than the aforementioned \kernel trick" because the computation is independent of the size of the training set. Experiments also show that this approximation method achieves accuracy comparable to RBF kernels while offering significant speedup.

Potentially Interesting Reading

[1] Fastfood | Approximating Kernel Expansions in Loglinear Time, Quoc Le, Tam, Alex Smola

[2] Fast Functions via Randomized Algorithms: Linear Regression with Random Projections

Video: Fast Food: Approximating Kernel Expansion in Loglinear Time

[3] Video: Random Kitchen Sinks, Fast Food and other randomized kernel evaluations

[4] Fast Functions via Randomized Algorithms: Fastfood versus Random Kitchen Sinks,

[5] Compressed Sensing: Random Features for Large-Scale Kernel Machines

[6] Uniform Approximation of Functions with Random Bases, Ali Rahimi and Benjamin Recht
[7]The Summer of the Deeper Kernels

[8] Nystrom Method vs Random Fourier Features:: A Theoretical and Empirical Comparison Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, Zhi-Hua Zhou

[9 Pruning random features with correlated kitchen sinks -poster- Brian McWilliams and David Balduzzi
[11] XNV: Correlated random features for fast semi-supervised learning - implementation -[10] Learning Fastfood Feature Transforms for Scalable Neural Networks, Micol Marchetti-Bowick, Willie Neiswanger

Deep neural networks are flexible models that are able to learn complex nonlinear functions of data. The goal of this project is to build a shallow neural network that has the same representational power as a deep network by learning an extra nonlinear feature transformation at each node. To apply these transformations, we borrow techniques from the area of scalable, approximate kernel methods. In particular, we use the Fastfood method introduced by Le at al. in [1], which allows an approximate feature map for a transition-invariate kernel to be computed in log-linear time. Our method learns an optimal Fastfood feature expansion at each node while simultaneously optimizing the weight parameters of the neural network. We demonstrate our method on multiple datasets and show that it has better classification performance than neural networks with similar architectures.

Image Credit: NASA/JPL/Space Science Institute

Full-Res: W00086165.jpg

W00086165.jpg was taken on January 12, 2014 and received on Earth January 12, 2014. The camera was pointing toward SATURN at approximately 1,457,373 miles (2,345,415 kilometers) away, and the image was taken using the MT3 and CL2 filters.

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.

First French-German Mathematical Image Analysis Conference starting today

I'll be attending a few talks at the First French-German Mathematical Image Analysis Conference before eventually co-hosting the 7th Paris Machine Learning Meetup on Wednesday night. See you there.

FGMIA 2014

- Program -

Monday 13 January
08:45am-09:00am	-	Welcome Message
09:00am-09:45am	-	Yi Ma (Microsoft Research Asia, China) (abstract) (slides)
09:45am-10:30am	-	Anders Hansen (Cambridge University, UK) (abstract) (slides)
	-	Coffee break
11:00am-11:45am	-	Richard Baraniuk (Rice, USA) (abstract) (slides)
11:45am-12:30pm	-	Deanna Needell (Claremont McKenna College, USA) (abstract) (slides)
	-	Lunch break
02:00pm-02:45pm	-	Mario Figueiredo (Instituto Superior Técnico, Portugal) (abstract) (slides)
02:45pm-03:30pm	-	Kristian Bredies (University of Graz, Austria) (abstract) (slides)
	-	Coffee break
04:00pm-04:45pm	-	Xiaoqun Zhang (Shanghai Jiao Tong University, China) (abstract) (slides)
04:45pm-05:30pm	-	Raymond Chan (The Chinese University of Hong Kong, Hong Kong) (abstract) (slides)

Tuesday 14 January
09:00am-09:45am	-	Otmar Scherzer (University of Vienna, Austria) (abstract) (slides)
09:45am-10:30am	-	Birsen Yazici (Rensselaer Polytechnic Institute, USA) (abstract) (slides)
	-	Coffee break
11:00am-11:45am	-	Adel Faridani (Oregon State University, USA) (abstract) (slides)
11:45am-12:30pm	-	Christoph Schnörr (University of Heidelberg, Germany) (abstract) (slides)
	-	Lunch break
02:00pm-02:45pm	-	Daniel Cremers (Technical University of Munich, Germany) (abstract) (slides)
02:45pm-03:30pm	-	Patrick Perez (Technicolor, France) (abstract) (slides)
	-	Coffee break
04:00pm-04:45pm	-	Olga Sorkine-Hornung (ETH, Switzerland) (abstract) (slides)
04:45pm-05:30pm	-	Cordelia Schmid (INRIA, France) (abstract) (slides)

Wednesday 15 January
09:00am-09:45am	-	René Vidal (Johns Hopkins, USA) (abstract) (slides)
09:45am-10:30am	-	Amit Singer (Princeton, USA) (abstract) (slides)
	-	Coffee break
11:00am-11:45am	-	Eero Simoncelli (New York University, USA) (abstract) (slides)
11:45am-12:30pm	-	Yohann Tendero (UCLA, USA (Andrea Bertozzi)) (abstract) (slides)
	-	Lunch break
02:00pm-02:45pm	-	Yuri Boykov (University of Western Ontario, Canada) (abstract) (slides)
02:45pm-03:30pm	-	Russell Luke (University of Göttingen, Germany) (abstract) (slides)
	-	Coffee break
04:00pm-04:45pm	-	Luca Zanni (University of Modena and Reggio Emilia, Italy) (abstract) (slides)
04:45pm-05:30pm	-	François-Xavier Vialard (University Paris-Dauphine, France) (abstract) (slides)

- Abstracts -

Richard Baraniuk - Learning Near-Isometric Linear Embeddings

In many machine learning and signal processing applications, we seek a low-dimensional representation (or embedding) of data that live in a high-dimensional ambient space. The classical principal components analysis (PCA) approach linearly maps the data into the lower-dimensional subspace spanned by the dominant eigenvectors of the data covariance matrix. While simple and computationally efficient, PCA suffers from an important drawback: the resulting embedding can arbitrarily distort pairwise distances between sample data points. The neoclassical random projections approach maps the data into a random lower-dimensional subspace. While also simple, random projections offer only probabilistic and asymptotic performance guarantees and, moreover, cannot leverage any special geometric structure of the data that might be present. In this talk, we introduce a new framework for the deterministic construction of linear, near-isometric embeddings of a finite set of data points. Our formulation is based on an affine rank minimization problem that we relax into a tractable semidefinite program (SDP). The resulting Nuclear norm minimization with Max-norm constraints (NuMax) framework has a number of applications in machine learning and signal processing, which we demonstrate via a range of experiments on large-scale synthetic and real datasets.

Yi Ma - The Pursuit of Low-dimensional Structures in High-dimensional Data

In this talk, we will discuss a new class of models and techniques that can effectively model and extract rich low-dimensional structures in high-dimensional data such as images and videos, despite nonlinear transformation, gross corruption, or severely compressed measurements. This work leverages recent advancements in convex optimization for recovering low-rank or sparse signals that provide both strong theoretical guarantees and efficient and scalable algorithms for solving such high-dimensional combinatorial problems. These results and tools actually generalize to a large family of low-complexity structures whose associated regularizers are decomposable. We illustrate how these new mathematical models and tools could bring disruptive changes to solutions to many challenging tasks in computer vision, image processing, and pattern recognition. We will also illustrate some emerging applications of these tools to other data types such as web documents, image tags, microarray data, audio/music analysis, and graphical models.
This is joint work with John Wright of Columbia, Emmanuel Candes of Stanford, Zhouchen Lin of Peking University, and my students Zhengdong Zhang, Xiao Liang of Tsinghua University, Arvind Ganesh, Zihan Zhou, Kerui Min and Hossein Mobahi of UIUC.

Anders Hansen - Compressed sensing in the real world - The need for a new theory

Compressed sensing is based on the three pillars: sparsity, incoherence and uniform random subsampling. In addition, the concepts of uniform recovery and the Restricted Isometry Property (RIP) have had a great impact. Intriguingly, in an overwhelming number of inverse problems where compressed sensing is used or can be used (such as MRI, X-ray tomography, Electron microscopy, Reflection seismology etc.) these pillars are absent. Moreover, easy numerical tests reveal that with the successful sampling strategies used in practice one does not observe uniform recovery nor the RIP. In particular, none of the existing theory can explain the success of compressed sensing in a vast area where it is used. In this talk we will demonstrate how real world problems are not sparse, yet asymptotically sparse, coherent, yet asymptotically incoherent, and moreover, that uniform random subsampling yields highly suboptimal results. In addition, we will present easy arguments explaining why uniform recovery and the RIP is not observed in practice. Finally, we will introduce a new theory that aligns with the actual implementation of compressed sensing that is used in applications. This theory is based on asymptotic sparsity, asymptotic incoherence and random sampling with different densities. This theory supports two intriguing phenomena observed in reality: 1. the success of compressed sensing is resolution dependent, 2. the optimal sampling strategy is signal structure dependent. The last point opens up for a whole new area of research, namely the quest for the optimal sampling strategies.

Deanna Needell - What we know and what we do not know about practical compressive sampling

Compressive sampling (CS) is a new and exciting technology which demonstrates that to recover compressible signals, far fewer samples are needed than traditional sampling theory suggests. Although the theory of CS is quite extensive for the now standard setting of incoherence and approximate sparsity, the practical abilities of CS are not always well understood. In this talk we will discuss several particular aspects of CS necessary for applications including dictionary or sampling correlations, quantization, and constrained measurements. New results showing whether CS is feasible in these settings are discussed, as well as some important directions that are not yet understood. We ask when and under what conditions can the power of CS actually be utilized, as well as with what methods accurate recovery can be achieved.

Mario Figueiredo - Some Recent Advances on the Use of ADMM in Imaging: Non-Periodic and Blind Deconvolution

The alternating direction method of multipliers (ADMM) has shown to be a flexible and efficient convex optimization tool for a variety of imaging inverse problems, under non-smooth convex regularization. ADMM exhibits state-of-the-art speed if the subproblems that constitute each iteration are efficiently solvable (e.g., using fast transforms or simple proximity operators). In deconvolution, one of these subproblems involves a matrix inversion, which can be done efficiently (by FFT) under periodic boundary conditions. We show how to extend ADMM-based image deconvolution to the realistic scenario of unknown boundaries. The proposed approach also handles, at no extra cost, problems that combine inpainting with deconvolution. In a another direction, we show how ADMM can be used to address blind deconvolution, achieving highly competitive results, with very few assumptions about the unknown convolution kernel.

Kristian Bredies - Total generalized variation: From regularization theory to applications in imaging 

Total generalized variation (TGV) functionals have shown to be effective penalties for variational imaging problems which allow to selectively regularize on different levels of smoothness. In particular, they are edge-aware similar to the total variation (TV) but also incorporate higher-order information leading to the absense of typical TV-induced artifacts like staircasing. Their convexity is moreover a convenient feature for algorithm design and numerical computations. In this talk, we start with discussing fundamental regularization properties of TGV for symmetric tensors in a functional-analytic framework. It turns out that TGV constitutes a regularizer for inverse problems in essentially the cases where it is possible to regularize with TV. We then discuss a general algorithmic framework which is suitable for the solution of TGV-regularized problems. The applicability to standard imaging problems like denoising, deblurring and compressed sensing is shown. Furthermore, we present various applications, in particular in magentic resonance imaging and image decompression, where with the help of TGV, one is able to obtain state-of-the-art high-quality reconstructions.

Xiaoqun Zhang - Primal-dual fixed point algorithms for separable minimization problems and their applications in imaging

In recent years, the minimization of a sum of two convex functions has received considerable interests in variational image restoration models. In this talk, I will present a general algorithmic framework for solving separable convex minimization problems with/without constraints from the point of view of fixed point algorithms and proximity operators. Convergence and rate analysis will be discussed under some assumptions. The efficiency and the advantages of the proposed algorithmic framework will be illustrated through applications to image restoration, parallel magnetic resonance imaging and computerized tomography. Finally, I will also discuss the perspective of application to nonconvex minimization problems such as regularized nonlinear inverse problems.

Raymond Chan - A Two-stage Image Segmentation Method using a Convex Variant of the Mumford-Shah Model and Thresholding

The Mumford-Shah model is one of the most important image segmentation models, and has been studied extensively in the last twenty years. In this talk, we propose a two-stage segmentation method based on the Mumford-Shah model. The first stage of our method is to find a smooth solution g to a convex variant of the Mumford-Shah model. Once g is obtained, then in the second stage, the segmentation is done by thresholding g into different phases. The thresholds can be given by the users or can be obtained automatically using any clustering methods. Because of the convexity of the model, g can be solved efficiently by techniques like the split-Bregman algorithm or the Chambolle-Pock method. We prove that our method is convergent and the solution g is always unique. In our method, there is no need to specify the number of segments K (K >= 2) before finding g. We can obtain any K-phase segmentations by choosing (K-1) thresholds after g is found in the first stage; and in the second stage there is no need to recompute g if the thresholds are changed to reveal different segmentation features in the image. Experimental results show that our two-stage method performs better than many standard two-phase or multi-phase segmentation methods for very general images, including anti-mass, tubular, MRI, noisy, and blurry images; and for very general noise models such as Gaussian, Poisson and multiplicative Gamma noise.

Otmar Scherzer - Mathematical Methods for Photoacoustical Imaging

In this talk we give an overview on (quantitative) photoacoustical imaging. In particular we emphasize on some recent trends in photoacoustical imaging, such as sectional imaging, where opposed to standard Photoacoustics, only certain regions of an object are illuminated. We present backprojection formulas in this case. This focusing method also allows for the recovery of scattering and absorption parameters, i.e., quantitative imaging. A new measurement setup for this purpose is studied. Another advantage of sectional imaging is that it can be used as an approach for simultaneous identification of the absorption density (imaging parameter of Photoacoustics) and the speed of sound via photoacoustic measurements. The mathematical model for such an experiment is developed and exact reconstruction formulas for both parameters are presented. This is joint work with P.Elbau (University of Vienna), A. Kirsch (University Karlsruhe), R. Schulze (University Innsbruck).

Birsen Yazici - Microlocal Analysis in Synthetic Aperture Imaging

Microlocal analysis is the abstract theory of Fourier Integral Operators (FIO) and singularities. An FIO can be viewed as a generalized Radon transform. Microlocal analysis is important to imaging since generalized Radon transforms arise in a wide range of tomographic imaging problems. This talk will introduce basics of microlocal analysis and describe a novel synthetic aperture imaging modality inspired by this theory.

Adel Faridani - On $\pi$-line reconstruction formulas in tomography

$\pi$-line formulas are a family of exact inversion formulas for recovering a function from its line integrals in two or three dimensions. We investigate characteristic features, typical artifacts, sampling conditions and some specific applications for these formulas.

Christoph Schnörr - Variational Image Analysis Using Wasserstein-Distance Based Priors

Locally computed empirical measures of features are widely used for various tasks of image analysis and computer vision. This talk focuses on more involved variational approaches that include global priors based on the Wasserstein distance between empirical measures that depend on the variable to be optimized. Convex relaxations and problem decompositions are discussed for the design of numerical algorithms. Applications include variational image restoration, variational segmentation and cosegmentation. This is a joint work with Paul Swoboda.

Daniel Cremers - Convex Relaxation Methods for Computer Vision

Numerous problems in computer vision and image analysis can be solved by variational methods and partial differential equations. Yet, many traditional approaches correspond to non-convex energies giving rise to suboptimal solutions and often strong dependency on appropriate initialization. In my presentation, I will show how problems like image segmentation, multiple view reconstruction, optical flow estimation and 3D shape matching can be tackled by means of convex relaxation methods. Subsequently, I will introduce methods of convexification which allow to efficiently compute globally optimal or near-optimal solutions. The arising convex problems can be solved by means of provably convergent primal-dual algorithms. They are easily parallelized on GPUs providing high-quality solutions in acceptable runtimes.

Patrick Perez - From image to descriptors and back again

The context of this presentation is visual search, with a specific focus on retrieving images similar to a query image. I will discuss three problems: - Aggregation of local descriptors (typically SIFTs) into a fixed-sized image signature. I shall present "Vector of Locally Aggregated Descriptors" (VLAD), an aggregation technique derived from Fisher kernel, which offers a powerful alternative to popular "Bag-of-Word" (BoF) approach. Combined with an efficient indexing system, VLAD can lead to a memory footprint as compact as 16 bytes per image with good approximate search performance. - Efficient search with complex similarity measures. When kernels not based on the Euclidean distance are more suited to compare image signatures (e.g., chi-square kernel), corresponding exact or approximate nearest neighbor search can become expensive. I shall present ways to expedite it, including one based on so-called explicit embedding. - Visual information leakage in image indexing systems. I shall show in particular that human-understandable reconstruction of an image can be obtained from the sparse local descriptors of this image and no other side information.

Olga Sorkine-Hornung - Variational warping for multi-image editing

We present a method for consistent automatic transfer of edits applied to one image to many other images of the same object or scene. By introducing novel, content-adaptive weight functions we enhance the non-rigid alignment framework of Lucas-Kanade to robustly handle changes of view point, illumination and non-rigid deformations of the subjects. Our weight functions are content-aware and possess high-order smoothness, enabling to define high-quality image warping with a low number of parameters using spatially-varying weighted combinations of affine deformations. Optimizing the warp parameters leads to subpixel-accurate alignment while maintaining computation efficiency. Our method allows users to perform precise, localized edits such as simultaneous painting on multiple images in real-time, relieving them from tedious and repetitive manual reapplication to each individual image.

Cordelia Schmid - DeepFlow: Large displacement optical flow with deep matching

Optical flow computation is a key component in many computer vision systems designed for tasks such as action detection or activity recognition. However, despite several major advances over the last decade, handling large displacement in optical flow remains an open problem. Inspired by the large displacement optical flow of Brox and Malik, our approach, termed DeepFlow, blends a matching algorithm with a variational approach for optical flow. We propose a descriptor matching algorithm, tailored to the optical flow problem, that allows to boost performance on fast motions. The matching algorithm builds upon a multi-stage architecture with 6 layers, interleaving convolutions and max-pooling, a construction akin to deep convolutional nets. Using dense sampling, it allows to efficiently retrieve quasi-dense correspondences, and enjoys a built-in smoothing effect on descriptors matches, a valuable asset for integration into an energy minimization framework for optical flow estimation. DeepFlow efficiently handles large displacements occurring in realistic videos, and shows competitive performance on optical flow benchmarks. Furthermore, it sets a new state-of-the-art on the MPI-Sintel dataset.

René Vidal - Algebraic, Sparse and Low-Rank Subspace Clustering

In the era of data deluge, the development of methods for discovering structure in high-dimensional data is becoming increasingly important. Traditional approaches often assume that the data is sampled from a single low-dimensional manifold. However, in many applications in signal/image processing, machine learning and computer vision, data in multiple classes lie in multiple low-dimensional subspaces of a high-dimensional ambient space. In this talk, I will present methods from algebraic geometry, sparse representation theory and rank minimization for clustering and classification of data in multiple low-dimensional subspaces. I will show how these methods can be extended to handle noise, outliers as well as missing data. I will also present applications of these methods to video segmentation and face clustering.

Amit Singer - Covariance Matrix Estimation for the Cryo-EM Heterogeneity Problem

In cryo-electron microscopy (cryo-EM), a microscope generates a top view of a sample of randomly-oriented copies of a molecule. The cryo-EM problem is to use the resulting set of noisy 2D projection images taken at unknown directions to reconstruct the 3D structure of the molecule. In some situations, the molecule under examination exhibits structural variability, which poses a fundamental challenge in cryo-EM. The heterogeneity problem is the task of mapping the space of conformational states of a molecule. It has been previously shown that the leading eigenvectors of the covariance matrix of the 3D molecules can be used to solve the heterogeneity problem. Estimating the covariance matrix is however challenging, since only projections of the molecules are observed, but not the molecules themselves. In this talk we derive an estimator for the covariance matrix as a solution to a certain linear system. While we prove that the resulting estimator for the covariance matrix is consistent in the classical limit as the number of projection images grow indefinitely, an interesting open question regarding the sample complexity of the problem remains. Namely, how many images are required in order to resolve heterogeneous structures as a function of the volume size and the signal to noise ratio? We will see that solving this question requires us to extend the analysis of principal component analysis (PCA) in high dimensions, as we encounter limiting distributions that differ from the classical Marcenko-Pastur distribution. Joint work with G. Katsevich and A. Katsevich

Eero Simoncelli - Recovery of sparse translation-invariant signals with continuous basis pursuit

We consider the problem of decomposing a signal into a linear combination of features, each a continuously translated version of one of a small set of elementary features. Although these constituents are drawn from a continuous family, most current signal decomposition methods rely on a finite dictionary of discrete examples selected from this family (e.g., a set of shifted copies of a set of basic waveforms), and apply sparse optimization methods to select and solve for the relevant coefficients. Here, we generate a dictionary that includes auxilliary interpolation functions that approximate translates of features via adjustment of their coefficients. We formulate a constrained convex optimization problem, in which the full set of dictionary coefficients represent a linear approximation of the signal, the auxiliary coefficients are constrained so as to only represent translated features, and sparsity is imposed on the non-auxiliary coefficients using an L1 penalty. The well-known basis pursuit denoising (BP) method may be seen as a special case, in which the auxiliary interpolation functions are omitted, and we thus refer to our methodology as continuous basis pursuit (CBP). We develop two implementations of CBP for a one-dimensional translationinvariant source, one using a first-order Taylor approximation, and another using a form of trigonometric spline. We examine the tradeoff between sparsity and signal reconstruction accuracy in these methods, demonstrating empirically that trigonometric CBP substantially outperforms Taylor CBP, which in turn offers substantial gains over ordinary BP. In addition, the CBP bases can generally achieve equally good or better approximations with much coarser sampling than BP, leading to a reduction in dictionary dimensionality. I will show a new set of state-of-the-art results on the problem of estimating spike arrival times from multi-electrode measurements in the brain.

Yohan Tendero - On the Foundations of Computational Photography: Theory and Practice

This work is about a revolutionary camera concept called "flutter shutter". Flutter shutter cameras promised to increase the image quality when photographing moving objects. The talk gives a mathematical theory and formulas that answer the questions on these recent camera designs. (The theory is also proved to be valid for the "motion invariant photography": the only other competitor of the flutter shutter".)

Russell Luke - Nonconvex notions of regularity and sparse affine feasibility: local and global linear convergence to a global solution of a nonconvex optimization problem.

We hope to convince our audience that convexity is not a categorical imperative for provablly convergent numerical algorithms. Firm nonexpansiveness of self-mappings is a global property that yields global convergence of fixed point algorithms. This property is intimately connected to convexity and has a long history in the literature of convex optimization. Unfortunately many applications one encounters are nonconvex. To accommodate nonconvexity, we formulate a generalization of firm nonexpansiveness that, together with a coercivity condition with respect to the set of fixed points, yields local linear convergence of generic nonmonotone fixed point algorithms. These tools enable us to prove local linear convergence of fundamental algorithms applied to the problem of finding a sparse vector subject to underdetermined affine constraints. Together with additional assumptions that are usually used to guarantee the correspondence of convex relaxations to the sparsity optimization problem, these local results are extended to show global linear convergence of a standard relaxation of the fundamental method of alternating projections applied to a nonconvex feasibility formulation of the problem.

Luca Zanni - Parameter estimation in regularization models for Poisson data

In many imaging applications the image intensity is measured by counting incident particles and, consequently, the fluctuations in the counting process can be taken into account by modeling the data as realizations of Poisson random variables. In such case, the maximum likelihood approach for image restoration leads to minimization problems in which the data-fidelity function is the generalized Kullback-Leibler (KL) divergence. Since, in general, these optimization problems are ill-conditioned, regularization approaches are necessary and the design of strategies for selecting a proper value of the regularization parameter is a crucial issue. This is still an open problem for Poisson data and, in special cases, interesting contributions have been recently provided. In this work we consider some regularization models and the theoretical and numerical issues concerning with their parameter estimations. Following the idea of the discrepancy principle, we discuss strategies that provide a parameter estimation as solution of a discrepancy equation and also regularization models in which a suited estimation is obtained by solving constrained optimization problems which force an upper bound on the discrepancy function. Furthermore, reconstruction strategies that require only an overestimation of the regularization parameter will be also presented.

Yuri Boykov - Combinatorial optimization for higher-order segmentation functionals: Entropy, Color Consistency, Curvature, etc.

This talk discusses recent advances in image segmentation in the context of higher-order appearance and smoothness functionals. The most basic segmentation energies combine unary terms enforcing certain color appearance models and pair-wise terms enforcing boundary smoothness. If color models are known, the corresponding binary optimization problem can be globally minimized. Estimation of color models leads to NP-hard mixed optimization problems that are typically solved with iterative block-coordinate descent (Zhu-Yuille, Chan-Vese, GrabCut, etc.) sensitive to initialization. This talk motivates higher-order appearance functionals (e.g. entropy and color-consistency) that do not require explicit estimation of segment appearance models. We show that in many cases such energies can be minimized globally. For example, our approach allows replacing iterative “grabcut” technique with a one cut method finding a global minimum. We also discuss a general Trust Region approach for approximate minimization of other high-order appearance terms. Time permitting, we will also motivate higher-order boundary smoothness terms (e.g. curvature) and describe the corresponding state-of-the-art combinatorial optimization techniques.

François-Xavier Vialard - New mathematical models in Computational Anatomy

One goal of computational anatomy is to develop statistical models on biomedical shapes. In this talk, we will briefly present the so-called LDDMM model and we will propose new geometrical models to overcome some of its shortcomings. In particular, we will present the use of left-invariant metrics on group of diffeomorphisms and the use of De-Rham theorem to define Riemannian metrics on space of shapes that satisfy constraints of interest.

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.

Another Paris ML Meetup#7 talk: What does it take to win the Kaggle/Yandex competition

I mentioned on Friday the three talks we will be having on Wednesday for the Paris Machine Learning Meetup #7: Machine Vision: VMX, Atheer One and VLAD

We will also feature Kenji Lefèvre-Hasegawa from the 'Dataiku Science Studio' team  (that includes Paul Masurel, Matt Scordia, Kenji Lefèvre and Christophe Bourguignat ) which just won First Prize of the Kaggle/Yandex competition out of 194 contenders ( the team listed as number one is OOC, i.e. Out Of Competition as it is a Yandex team). At the previous meetup, a member of that team, Matthieu Scordia, presented us what the team's strategy was at the time. I am told that the strategy changed in the last month of the challenge so we will get more insight directly from the horse's mouth.

Title: What does it take to win the Kaggle/Yandex competition

Abstract: I'll give a feedback on the "personnalized web search" Kaggle challenge for which our team won First prize. I will focus the talk on both the experience itself (team work and tools) and the models we've used. 

The Meetup group has now more than 460 members probably one of the largest Machine Learning Meetup group outside the US.

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.

Saturday Morning Videos: Analyzing Animal Vocal Sequences Investigative Workshop

With the advent very high quality microphones in the home (think Kinect), the large amount of data that can be gathered without undue hardship related to privacy issues, the rapid development of large machine learning algorithms, isn't time to be more seriously considering talking to animals i.e. the first item in this list of Just on the right Side of Impossible projects.

Related: 

The Analyzing Animal Vocal Sequences Investigative Workshop took place 21-23 October 2013, at NIMBioS. The aim of this workshop was to bridge the gap between mathematical and biological researchers with an interest in the quantitative analysis of animal vocal sequences

Machine learning for the classification of animal vocalizations, Michael Johnson

Information theoretic principles of human language and animal behavior, Ramon Ferrer-i-Cancho,

Laurance R. Doyle, SETI Institute, "Animal communication sequence analysis using information theory"

Kirsten Bohn,  "Singing isn't just for the birds"

Brenda McCowan,  "Unraveling dolphin communication complexity: Past approaches and next steps"

Edgar Vallejo,Automated identification of bird individuals using machine learning: A hierarchical approach

Other interesting references

• Classification of dog barks: a machine learning approach, Molnar, Csaba; Kaplan, Frederic; Roy, Pierre; Pachet, Francois; Pongracz, Peter;Doka, Antal; Miklosi, Adam
• Darwin, C. R. 1872. The expression of the emotions in man and animals.
• Human_Animal Communication on Wikipedia Dolphin Communication Project
• Dr. Doolittle Project

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.

Paris Machine Learning Meetup #7: Machine Vision: VMX, Atheer One and VLAD

From [1]

The Paris Machine Learning Meetup #7 will take place this coming wednesday Januray 15th. It will feature at least three presentations. Two of them will be made by people offsite and will focus on two crowdfunding campaigns that have a Machine Learning component. If everything goes well, we'll continue on experimenting with these off-site presentations. We've asked the meetupers to watch the videos first so they have questions ready for our speakers. Here is a draft program:

• Tomasz Malisiewicz: VMX Project: Teach your computer how to see 
• Allen Yang:  Atheer One: What it feels like to have superpowers! 
• Patrick Perez , From image to descriptors and back again

Abstract: The context of this presentation is visual search, with a specific focus on retrieving images similar to a query image. I will first discuss one corner stone of such large-scale systems: aggregation of local descriptors (typically SIFTs) into a fixed-sized image signature. I shall present "Vector of Locally Aggregated Descriptors" (VLAD) which offers a powerful alternative to popular "Bag-of-Word" (BoF) approach. Combined with an efficient indexing system, VLAD can lead to a memory footprint as compact as 16 bytes per image with good approximate search performance. I will then touch upon risks of visual information leakage in such image search systems, showing that human-understandable reconstruction of an image can be obtained from the sparse set of its local descriptors, and no other side information.

The Paris Machine Learning on LinkedIn: http://www.linkedin.com/groups?gid=6400776

To take part in the meetup, please register on Meetup.com, join the Paris ML group and go to this page.

The archives for the previous meetings can be found here.

[1] Reconstructing an image from its local descriptors by Philippe Weinzaepfel, Herve Jegou, Patrick Perez as featured here on Nuit Blanche


Organizers: Franck Bardol, Frederic Dembak, Igor Carron

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.

GrAMPA: Generalized Approximate Message Passing for Analysis Compressive Sensing - implementation -

Here is a potentially interesting AMP solver for analysis compressive sensing:

Generalized Approximate Message Passing for the Cosparse Analysis Model by Mark Borgerding, Philip Schniter

In "synthesis'' compressive sensing (CS), one seeks a sparse coefficient vector that approximately matches a set of linear measurements, whereas in "analysis'' CS, one instead seeks a (nonsparse) signal vector matches a set of linear measurements while being sparse in a given linear transformation (e.g., the finite difference operator in the case of total variation regularization). The Approximate Message Passing (AMP) algorithm, first proposed by Donoho, Maleki, and Montanari, has established itself as an effective means of solving the synthesis CS problem but not the analysis CS problem. In this paper, we propose a novel interpretation of the generalized AMP algorithm, first proposed by Rangan, that provides a direct vehicle for solving the analysis CS problem. In addition, we propose a novel form of soft thresholding, based on the limit of the MMSE denoiser for a Bernoulli-Uniform prior with increasing support, that successfully mimics ℓ0regularization. Extensive empirical experiments demonstrate the advantages of our proposed "Generalized AMP for Analysis'' (GrAMPA) algorithm, in both accuracy and runtime, over several existing approaches based on greedy analysis pursuit, Douglas-Rachford splitting, and iteratively-reweighted-ℓ1.

The GrAMPA page 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.

Binary Linear Classification and Feature Selection via Generalized Approximate Message Passing

If you have read:

• Sunday Morning Insight: Randomization is not a dirty word
• Sunday Morning Insight: Sharp Phase Transitions in Machine Learning ?

you won't be surprised by the finding that phase transitions are indeed coming to Machine Learning. If you are, here is another stone to that story:

Binary Linear Classification and Feature Selection via Generalized Approximate Message Passing by Justin Ziniel, Philip Schniter

For the problem of binary linear classification and feature selection, we propose algorithmic approaches to classifier design based on the generalized approximate message passing (GAMP) algorithm, recently proposed in the context of compressive sensing. Our work focuses on the regime where the number of features greatly exceeds the number of training examples, but where only a few features suffice for accurate classification. We show that sum-product GAMP can be used to (approximately) minimize the classification error rate and max-sum GAMP can be used to minimize a wide variety of regularized loss functions. Moreover, we show how a "turbo" extension to GAMP allows us to learn weight vectors that exhibit structured sparsity. Furthermore, we describe an expectation-maximization (EM)-based scheme to learn the associated model parameters online, as an alternative to cross-validation, and we show that GAMP's state evolution framework can be used to accurately predict the misclassification rate. Finally, we present a detailed numerical study to confirm the accuracy, speed, and flexibility afforded by our GAMP-based approaches to binary linear classification.

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.

Around the blogs in 78 hours

It's been a while since we haven't this around the blogs, here some noteworthy blog entries.Enjoy!

Masaaki

• Sparsity-related researches in IEEE CDC 2013
• Sparse Packetized Predictive Control

Dustin

• Deterministic RIP matrices: Breaking the square-root bottleneck, II
• Deterministic RIP matrices: Breaking the square-root bottleneck
• Matheon Workshop 2013: Compressed Sensing and its Applications

Afonso

• Guest post by Andy Zhu: Alignment and Unique Games
• A different angle to the 4M-4 conjecture
• Deterministic RIP matrices: a new cooperative online project
• The little Grothendieck problem over O(d)

Sergey

• December finds in #arxiv

David

• ANALCO, day 1 ANALCO, day 2 ANALCO, day 3

John

• A year of consulting

Vladimir

• FLIR Announces First Consumer Thermal Camera
• Toshiba Announces 240fps Video Sensor Technology
• Softkinetic News
• Blue Filters in Short Supply
• Experiment: Pinned PD Paper Peer Review
• Vision Research Announces 1MP 22,000fps Camera

Thomasz

• Tracking points in a live camera feed: A behind-the-scenes look at the VMX Project webapp
• You asked, we listened. VMX will be available to run locally.

Danny

• Registration for the 3rd GraphLab Conference is open!
• GraphLab Tutorial @ Strata
• Plotly - a nice visualization package in Python
• Reverse engineering Netflix customized categories
• Amazon EC2 Education Grants - ML Focus - January 10 Deadline Approaching

Andrew

• 2013
• NYT version of birthday graph
• Happy birthday

Bob

• DFF FTP Independent Postdoc Project Results 2012-2013
• Paper of the Day (Po'D): Music descriminations by carp (Cyprinus carpio) edition

Andrej

• Released new pet project ConvNetJS: Deep Learning in your browser.
• Quantifying Hacker News with 50 days of data

while on Nuit Blanche, we had since the last Nuit Blanche In Review (December 2013):

• Nonlinear Basis Pursuit - implementation -
• Blind Identification via Lifting - implementation -
• Frugal Streaming and Sparse Recovery with Very Sparse Compressed Counting
• CfP: Advances in sparse modeling and low-rank modeling for speech processing
• Indiegogo: Atheer One: What it feels like to have superpowers!
• Highly Technical Aggregators - request -
• Nonlinear Compressive Sensing - request -
• Novel meetings: Image processing for materials characterization (ICIP 2014, special session), Spin Glass and Beyond: An old tool for new problems, ITWIST'14 deadline extended
• Popular Posts of 2013
• Two PhD positions on compressive imaging for astronomical and biomedical applications, Edinburgh
• Dynamics and termination cost of spatially coupled mean-field models

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.