Matrix Factorization with Binary Components

So the Arora et al paper has really provoked a tsunami in the NMF world probably because like Suresh says, "One can think of the NMF as an l_1 variant of the SVD”. Another attractiveness of NMF was its easy, albeit very slow implementation. Let us say that currently we don't much implementation made available for the new crop of solvers. It's just a question of time I am sure ....

Matrix factorization with Binary Components by Martin Slawski, Matthias Hein, Pavlo Lutsik

Motivated by an application in computational biology, we consider low-rank matrix factorization with {0,1}-constraints on one of the factors and optionally convex constraints on the second one. In addition to the non-convexity shared with other matrix factorization schemes, our problem is further complicated by a combinatorial constraint set of size 2m⋅r, where mis the dimension of the data points and r the rank of the factorization. Despite apparent intractability, we provide - in the line of recent work on non-negative matrix factorization by Arora et al. (2012) - an algorithm that provably recovers the underlying factorization in the exact case with O(mr2r+mnr+r2n) operations for n datapoints. To obtain this result, we use theory around the Littlewood-Offord lemma from combinatorics.

Related:

New developments in nonnegative matrix factorization by Suresh Venkatasubramanian

Computing a Nonnegative Matrix Factorization -- Provably by Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra

In the Nonnegative Matrix Factorization (NMF) problem we are given an n×m nonnegative matrix M and an integer r superior to 0. Our goal is to expressM as AW where A and W are nonnegative matrices of size n×r and r×m respectively. In some applications, it makes sense to ask instead for the product AW to approximate M -- i.e. (approximately) minimize$\norm{M - AW}_F$ where $\norm{}_F$ denotes the Frobenius norm; we refer to this as Approximate NMF. This problem has a rich history spanning quantum mechanics, probability theory, data analysis, polyhedral combinatorics, communication complexity, demography, chemometrics, etc. In the past decade NMF has become enormously popular in machine learning, where A and W are computed using a variety of local search heuristics. Vavasis proved that this problem is NP-complete. We initiate a study of when this problem is solvable in polynomial time:

1. We give a polynomial-time algorithm for exact and approximate NMF for every constant r. Indeed NMF is most interesting in applications precisely when r is small.

2. We complement this with a hardness result, that if exact NMF can be solved in time (nm)o(r), 3-SAT has a sub-exponential time algorithm. This rules out substantial improvements to the above algorithm.

3. We give an algorithm that runs in time polynomial in n, m and r under the separablity condition identified by Donoho and Stodden in 2003. The algorithm may be practical since it is simple and noise tolerant (under benign assumptions). Separability is believed to hold in many practical settings.

To the best of our knowledge, this last result is the first example of a polynomial-time algorithm that provably works under a non-trivial condition on the input and we believe that this will be an interesting and important direction for future work.

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.

Sparse Packetized Predictive Control for Networked Control over Erasure Channels

Masaaki who writes a blog on sparsity in control systems summarized his recent paper on his blog.

Sparse Packetized Predictive Control for Networked Control over Erasure Channels by Masaaki Nagahara, Daniel E. Quevedo, Jan Ostergaard

We study feedback control over erasure channels with packet-dropouts. To achieve robustness with respect to packet-dropouts, the controller transmits data packets containing plant input predictions, which minimize a finite horizon cost function. To reduce the data size of packets, we propose to adopt sparsity-promoting optimizations, namely, ell-1-ell-2 and ell-2-constrained ell-0 optimizations, for which efficient algorithms exist. We derive sufficient conditions on design parameters, which guarantee (practical) stability of the resulting feedback control systems when the number of consecutive packet-dropouts is bounded.

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 Video: CMOS Image Sensors: Tech Transfer from Saturn to your Cell Phone

If you are a reader of this blog, you are accustomed to seeing images from the Cassini probe around Saturn every so often. 

In this video, Eric Fossum recounts the story behind CMOS Image Sensors and the technology transfer that took place from imagers used to view Saturn on Cassini all the way to your cell Phone. Think about it, no imaging CMOS in 1995, billions of chips 19 years later. The attendant presentation 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.

Saturday Morning Video: Unraveling dolphin communication complexity: Past approaches and next steps

For some odd reason, this video from last saturday on the Analyzing Animal Vocal Sequences Investigative Workshop could not play correctly. Well here it is:

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

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.

Sharp Phase Transition for Joint Sparse Recovery (MMV)

Jeff Blanchard just sent me the following

Dear Igor, 

I saw in your January 22 post that you posed the question, "Isn't it time, we devise a universal phase transition diagram for MMV computations?" If you haven't seen it, I think you might be interested in a paper I wrote with three of my students,

Jeffrey D. Blanchard, Michael Cermak, David Hanle, Yirong Jing. "Greedy algorithms for Joint Sparse Recovery", IEEE Trans. Sig. Proc., in press, 2014.

While it does not resolve your question, we present weak, empirical recovery phase transitions for the MMV setting for simultaneous recovery variants of NIHT, HTP, and CoSaMP in addition to RIP-based, uniform recovery guarantees.

It should be online at TSP in the next week or so as the preprint version. In the meantime, you can get the preprint from my webpage.

www.math.grinnell.edu/~blanchaj/Research/Research.html

All the best,

Jeff

Thanks Jeff ! Here is the paper: Greedy Algorithms for Joint Sparse Recovery by Jeff Blanchard, Michael Cermak, David Hanle, and , Yirong Jing

Abstract—Five known greedy algorithms designed for the single measurement vector setting in compressed sensing and sparse approximation are extended to the multiple measurement vector scenario: Iterative Hard Thresholding (IHT), Normalized IHT (NIHT), Hard Thresholding Pursuit (HTP), Normalized HTP (NHTP), and Compressive Sampling Matching Pursuit (CoSaMP). Using the asymmetric restricted isometry property (ARIP), sufficient conditions for all five algorithms establish bounds on the discrepancy between the algorithms’ output and the optimal row-sparse representation. When the initial multiple measurement vectors are jointly sparse, ARIP-based guarantees for exact recovery are also established. The algorithms are then compared via the recovery phase transition framework. The strong phase transitions describing the family of Gaussian matrices which satisfy the sufficient conditions are obtained via known bounds on the ARIP constants. The algorithms’ empirical weak phase transitions are compared for various numbers of multiple measurement vectors. Finally, the performance of the algorithms is compared against a known rank aware greedy algorithm, Rank Aware Simultaneous Orthogonal Matching Pursuit + MUSIC. Simultaneous recovery variants of NIHT, NHTP, and CoSaMP all outperform the rank-aware algorithm.

One figure, in particular, triggered my interest: figure 3c

Figure 3c of Greedy Algorithms for Joint Sparse Recovery

because it has the same shape as the one we found experimentally in the lab with a random medium used as measurement matrix.

Figure 4 from this preprint

Those are not exact match because Jeff  et al's paper: 

• produces phase transition for l=2, 5 and 10 while ours is for l = 3 (it is between their l=2 and l=5)
• focuses on noiseless phase transitions (lab experiments are not noiseless).

it is noteworthy that if the phase transition showed l*m/n on the x-axis , it would show exact recovery for x (l*m/n)  less than 1 and this for l =2 or 3. We noted before that there is something interesting at l = 2 and 3 in a computational-only study featuring Imaging strong localized scatterers with sparsity promoting optimization.

As an aside, maybe the Advanced Matrix Factorization Jungle page ought to have a place for each of the factorization and papers covering their phase transitions. In fact, I just added these templates for each factorization:

Phase Transitions:

• None so far.

Implementations:

Please kindly let me know by which paper I should remove the current "None so far" item.

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.

Sparse Matrix Factorization: Simple rules for growing neural nets and Provable Bounds for Learning Some Deep Representations

I cannot tell you how much I **love** the following two papers. Why ? because using Advanced Matrix Factorization one can foresee a much more direct understanding of the whole Panorama of Sensing while allowing these models to provide information Faster Than a Blink of an Eye. Furthermore, it paves the way to naturally see how phase transitions put a limit on these contructions in a rational way (Sunday Morning Insight: The Map Makers). Think of these papers as gateway papers. Wow.

Sparse Matrix Factorization by Behnam Neyshabur, Rina Panigrahy

We investigate the problem of factorizing a matrix into several sparse matrices and propose an algorithm for this under randomness and sparsity assumptions. This problem can be viewed as a simplification of the deep learning problem where finding a factorization corresponds to finding edges in different layers and values of hidden units. We prove that under certain assumptions for a sparse linear deep network with n nodes in each layer, our algorithm is able to recover the structure of the network and values of top layer hidden units for depths up to O~(n1/6). We further discuss the relation among sparse matrix factorization, deep learning, sparse recovery and dictionary learning.

The attendant slides are here. Of interest is the following slide for the hardware pêople


Highly relevant:
Provable Bounds for Learning Some Deep Representations by Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma

We give algorithms with provable guarantees that learn a class of deep nets in the generative model view popularized by Hinton and others. Our generative model is an n node multilayer neural net that has degree at most n for some \gamma less than 1 and each edge has a random edge weight in [-1; 1]. Our algorithm learns almost all networks in this class with polynomial running time. The sample complexity is quadratic or cubic depending upon the details of the model. The algorithm uses layerwise learning. It is based upon a novel idea of observing correlations among features and using these to infer the underlying edge structure via a global graph recovery procedure. The analysis of the algorithm reveals interesting structure of neural networks with random edge weights.

see also Rong Ge's PhD thesis: Provable Algorithms for Machine Learning Problems and

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

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.

The Why and How of Nonnegative Matrix Factorization

Nicolas Gillis has been one of the people who has tried to make mathematical sense as to why an empirical matrix factorization has been so successful for the past 14 years. His latest arxiv preprint (see below) provides some perspectives on where we are in that respect. It is no secret that every paper using nonnegative matrix factorization has produced its own version of the NMF decomposition in some way or another. To call the ensemble a zoo would be, at the very least, charitable. I personally decided to call it a jungle. This sentiment of being lost in the jungle has had a curious side effect: the cannibalization of the semantics used for matrix factorization. Indeed, in many people's mind, Matrix Factorization and NMF hae become one and the same. This is a situation not unlike the one we faced in compressive sensing with the myriad of sparsity seeking solvers. In turn, this issue of being easily lost led me to write this blog entry pointing to a solution: If there is revolution in rank minimization and nobody hears about it, is this a revolution ? or this one. The remedy to this state of affairs in compressive sensing has been to use the "acid test" of the universal phase transitions. One can expect that at some point in time we'll surely get there with NMF as well. Without further due, here is the paper: The Why and How of Nonnegative Matrix Factorization by Nicolas Gillis (Update: version 2 is here , also Matlab code , attendant slides)

Nonnegative matrix factorization (NMF) has become a widely used tool for the analysis of high-dimensional data as it automatically extracts sparse and meaningful features from a set of nonnegative data vectors. We first illustrate this property of NMF on three applications, in image processing, text mining and hyperspectral imaging --this is the why. Then we address the problem of solving NMF, which is NP-hard in general. We review some standard NMF algorithms, and also present a recent subclass of NMF problems, referred to as near-separable NMF, that can be solved efficiently (that is, in polynomial time), even in the presence of noise --this is the how. Finally, we briefly describe some problems in mathematics and computer science closely related to NMF via the nonnegative rank.

also relevant: Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework by Jingu Kim, Yunlong He, Haesun Park

Abstract We review algorithms developed for nonnegative matrix factorization (NMF) and nonnegative tensor factorization (NTF) from a unified view based on the block coordinate descent (BCD) framework. NMF and NTF are low-rank approximation methods for matrices and tensors in which the low-rank factors are constrained to have only nonnegative elements. The nonnegativity constraints have been shown to enable natural interpretations and allow better solutions in numerous applications including text analysis, computer vision, and bioinformatics. However, the computation of NMF and NTF remains challenging and expensive due the constraints. Numerous algorithmic approaches have been proposed to efficiently compute NMF and NTF. The BCD framework in constrained non-linear optimization readily explains the theoretical convergence properties of several efficient NMF and NTF algorithms, which are consistent with experimental observations reported in literature. In addition, we discuss algorithms that do not fit in the BCD framework contrasting them from those based on the BCD framework. With insights acquired from the unified perspective, we also propose efficient algorithms for updating NMF when there is a small change in the

reduced dimension or in the data. The effectiveness of the proposed updating algorithms are validated experimentally with synthetic and real-world data sets. 

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.

Sparse Randomized Kaczmarz for Multiple Measurement Vectors - implementation -

Extension of Sparse Randomized Kaczmarz Algorithm for Multiple Measurement Vectors by Hemant Kumar Aggarwal, Angshul Majumdar

The Kaczmarz algorithm is popular for iteratively solving an overdetermined system of linear equations. However the traditional Kaczmarz algorithm has a linear convergence rate,a randomized version of the Kaczmarz algorithm was shown to converge exponentially. Recently an algorithm for finding sparse solution to a linear system of equations has been proposed based on weighted randomized Kaczmarz algorithm. These algorithms solves single measurement vector problem; however there are applications were multiple-measurements are available. In this work, the objective is to solve a multiple measurement vector problem with common sparse support by modifying the randomized Kaczmarz algorithm. We have also modeled the problem of face recognition from video as the multiple measurement vector problem and solved using our proposed technique. We have compared the proposed algorithm with state-of-art spectral projected gradient algorithm for multiple measurement vectors on both real and synthetic datasets. The Monte Carlo simulations confirms that our proposed algorithm have better recovery and convergence rate than the MMV version of spectral projected gradient algorithm under fairness constraints.

I note from the paper:

The algorithm works for both over-determined and under-determined system of equations.

Isn't it time, we devise a universal phase transition diagram for MMV computations ? At least some people on the experimental side could see if it fits the best that can be achieved numerically.

The implementation is on Matlab Central

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.

Far-field subwavelength imaging from a single broadband antenna in combined with strongly disordered medium

So using one antenna and a random medium to locate "things" we've heard that one before :-) Lianlin and colleagues explore this new capability and even provide us a phase transition map, what else can you ask ?

Far-field subwavelength imaging from a single broadband antenna in combined with strongly disordered medium by Lianlin Li, Fang Li, Tie Jun Cui

The far-field subwavelength imaging is a challenging issue. In this letter we demonstrate numerically that the far-field subwavelength imaging of weakly scattering objects can be obtained by processing the data acquired by a single antenna, which benefits from the use of the strongly disordered medium. A mathematical model has been proposed for solving such problem based on the idea of sparse reconstruction. Moreover, this study leads to an important conclusion that the strongly disordered medium can serves as an efficient apparatus for the single-antenna compressive measurement, which shifts the complexity of devising compressive sensing (CS) hardware from the design, fabrication and electronic control. The proposed method and associated results can find applications in several imaging disciplines, such as optics, THz, RF or ultrasound imaging.

Subwavelength imaging of sparse broadband sources surrounded by an open disordered medium from a single antenna by Lianlin Li, Fang Li, Tie Jun Cui

In this letter we study the subwavelength imaging of sparse broadband sources inside a disordered medium by processing the data acquired by a single antenna. A mathematical model has been developed for solving such problem based on the idea of sparse reconstruction. We show that the strongly disordered medium can serves as an efficient apparatus for compressive measurement, which shifts the complexity of devising compressive sensing (CS) hardware from the design, fabrication and electronic control. The proposed method and associated results can find applications in several imaging disciplines, such as optics, THz, RF or ultrasound imaging.

Highly relevant:

Subwavelength focusing inside an open disordered medium by time reversal at a single point antenna by Romain Pierrat, Cédric Vandenbem, Mathias Fink, Rémi Carminati

We study theoretically light focusing at subwavelength scale inside a disordered strongly scattering open medium. We show that broadband time reversal at a single point antenna, in conjunction with near-field interactions and multiple scattering, produces spatial focusing with a quality comparable to that obtained in an ideal closed cavity. This gives new perspectives for super-resolved optical imaging and coherent control of single nanosources or absorbers in complex media.

h/t Sylvain Gigan.

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.

"We already have cats under control": A summary of Paris Machine Learning Meetup #7

"We already have cats under control"

Following up on our first Q&A, Tom from VMX (a Machine Learning #Kickstarter campaign)  implemented a cat face detector using VMX. He also checked it against the PASCAL VOC 2007 dataset to find images with cats. From the blog entry:

...Pre-trained VMX Object Detectors

VMX will come with a set of pre-trained models.  While the fun part of using VMX is training your own specialized detectors, we understand that that are scenarios where you want access to a library of pre-existing object detectors.  You'll be able to modify those detectors and customize them for your own use (such as taking a generic face detector and making it better by giving it examples of your own face).  If there is an object you utterly love and really want a pre-trained version in VMX, just send us a message.  We already have cats under control.

Just imagine cat lovers using VMX to detect their cats intention during the day or ... the possibilities look endless.

The 7th Parisian Machine Learning Meetup was initally held with a Machine Vision theme with: VMX , Atheer One,VLAD and What does it take to win the Kaggle/Yandex competition? even though the latter presentation was an impromptu one. It took place on Wednesday January 15th, 2014 at DojoEvents. Here is the video of the Meetup. The program and attendant presentations:

• Tomasz Malisiewicz, VMX Project: Computer Vision for Everyone
• Allen Yang, Atheer One, what it feels like to have superpowers
• Patrick Perez From image to descriptors and back again
• Kenji Lefèvre-Hasegawa , 'Dataiku Science Studio', What does it take to win the Kaggle/Yandex competition ?
• Presentation/Context of the meetup, Franck Bardol, Igor Carron.

I noted that the VMX project could handle local computation with about 20 objects requiring a good computer. For Atheer, I think the issue of battery is set aside as the glass seem to be aiming for a crowd next to a power plug. Kenji told us that the winning entry was based on LambdaMART beating out another of their Random Forest implementation. Patrick also mentioned a series of photos reconstructed from descriptors. That series is on Herve Jegou's page. While  Patrick pointed out it was information leakage, most folks in the crowd were simply wowed.

Many more examples on this page.

Needless to say, there is an uncanny visual parallel beween these reconstruction and the ones from MRI readings featured at the third meetup where we learned about mindreading with MRI thanks to Alexandre Gramfort. ( see also Dreaming reconstructions)

During the off moment of the meetup, we had a discussion on counting things and how it should be part of the general ML generic knowledge. Sam Bessalah mentioned the large repository of information on counting things done by Debasish Gosh and I mentioned the recent entry on the same subject here on Nuit Blanche: Frugal Streaming and Sparse Recovery with Very Sparse Compressed Counting. I think we'll have a meetup on the subject in March. Stay tuned.

Frank and I were so very impressed by how smooth the Skype Q&As went, we decided to expand the reach of these ML Meetups. Again stay tuned.

Related Blog entries: 

• Dataiku has a related blog entry by Paul Masurel: Winning Kaggle, An introduction to Re-Ranking
• Tom from VMX Machine Learning #Kickstarter campaign implemented a cat face detector using VMX

The meetup was slated to have 142 people but I counted about 110 people in all. Not bad. Next meetup event is February 12th. Don't forget about also the Paris Machine Learning LinkedIn group (225 members) where one can post jobs or find job postings. The archive of the previous meetings can be found 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.