Memory and Computation Efficient PCA via Very Sparse Random Projections

Memory and Computation Efficient PCA via Very Sparse Random Projections by Farhad Pourkamali Anaraki, Shannon Hughes

Algorithms that can efficiently recover principal components in very high-dimensional, streaming, and/or distributed data settings have become an important topic in the literature. In this paper, we propose an approach to principal component estimation that utilizes projections onto very sparse random vectors with Bernoulli-generated nonzero entries. Indeed, our approach is simultaneously efficient in memory/storage space, efficient in computation, and produces accurate PC estimates, while also allowing for rigorous theoretical performance analysis. Moreover, one can tune the sparsity of the random vectors deliberately to achieve a desired point on the tradeoffs between memory, computation, and accuracy. We rigorously characterize these tradeoffs and provide statistical performance guarantees. In addition to these very sparse random vectors, our analysis also applies to more general random projections. We present experimental results demonstrating that this approach allows for simultaneously achieving a substantial reduction of the computational complexity and memory/storage space, with little loss in accuracy, particularly for very high-dimensional data. 

 supplementary material     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.

Compressive Imaging in Scanning Transmission Electron Microscopy and Microwave Ghost Imaging

Here are two new hardware randomized acquisition of signals:

Development of a fast electromagnetic shutter for compressive sensing imaging in scanning transmission electron microscopy
Armand Béché, Bart Goris, Bert Freitag, Jo Verbeeck

The concept of compressive sensing was recently proposed to significantly reduce the electron dose in scanning transmission electron microscopy (STEM) while still maintaining the main features in the image. Here, an experimental setup based on an electromagnetic shutter placed in the condenser plane of a STEM is proposed. The shutter blanks the beam following a random pattern while the scanning coils are moving the beam in the usual scan pattern. Experimental images at both medium scale and high resolution are acquired and then reconstructed based on a discrete cosine algorithm. The obtained results confirm the predicted usefulness of compressive sensing in experimental STEM even though some remaining artifacts need to be resolved.

Microwave Surveillance based on Ghost Imaging and Distributed Antennas
Xiaopeng Wang, Zihuai Lin

In this letter, we proposed a ghost imaging (GI) and distributed antennas based microwave surveillance scheme. By analyzing its imaging resolution and sampling requirement, the potential of employing microwave GI to achieve high-quality surveillance performance with low system complexity has been demonstrated. The theoretical analysis and effectiveness of the proposed microwave surveillance method are also validated via simulations.

    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.

On the Complexity of Robust PCA and $\ell_1$-norm Low-Rank Matrix Approximation - implementation -

On the Complexity of Robust PCA and $\ell_1$-norm Low-Rank Matrix Approximation
Nicolas Gillis, Stephen A. Vavasis

The low-rank matrix approximation problem with respect to the component-wise $\ell_1$-norm ($\ell_1$-LRA), which is closely related to robust principal component analysis (PCA), has become a very popular tool in data mining and machine learning. Robust PCA aims at recovering a low-rank matrix that was perturbed with sparse noise, with applications for example in foreground-background video separation. Although $\ell_1$-LRA is strongly believed to be NP-hard, there is, to the best of our knowledge, no formal proof of this fact. In this paper, we prove that $\ell_1$-LRA is NP-hard, already in the rank-one case, using a reduction from MAX CUT. Our derivations draw interesting connections between $\ell_1$-LRA and several other well-known problems, namely, robust PCA, $\ell_0$-LRA, binary matrix factorization, a particular densest bipartite subgraph problem, the computation of the cut norm of $\{-1,+1\}$ matrices, and the discrete basis problem, which we all prove to be NP-hard.

An implementation is available here: https://sites.google.com/site/nicolasgillis/code. From the page:

This Matlab code implements an exact cyclic coordinate descent method for the component-wise ℓ1-norm matrix approximation problem: Given an m-by-n matrix M and a factorization rank r, find an m-by-r matrix U and an r-by-n matrix V such that ||M-UV||1 = sumi,j |M-UV|ij is minimized. By default, it initializes the algorithm with the optimal solution of the ℓ2-norm problem using the truncated singular value decomposition provided by Matlab.

 
 
 

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.

Sunday Morning Insight: The Second Inflection Point in Genome Sequencing

This week, I was making a presentation for Company X and needed to keep abreast of the recent cost per genome figure computed at genome.gov. Well, thanks to a retweet by Michael, it looks like October 1 saw the Second Inflection point we've been waiting for. Time to change the slides and time to think about The Important Things after Commodity Sequencing.

Let us note that this cost figure still doesn't seem to include neither Pacific BioSciences RSII nor Oxford Nanopore technology cost.

Related:

• A Second Inflection Point in Genome Sequencing ? and then ...  
• Hamming's time: The Important Things after Commodity Sequencing 

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.

Ceci n'est toujours pas le site de la Nuit Blanche

Les attractions des Nuits Blanches de Paris se trouvent ici, celles de Bruxelles se trouvent ici et celles de Toronto ici.

Si par contre vous etes interessés par le déluge de données qui dépassent le nombre d'étoiles dans l'univers et comment les utiliser pour mieux comprendre le monde, bienvenue, vous êtes arrivés a bon port. Pour information, il y a depuis plus de deux ans, des meetups sur le Machine Learning a Paris.  

L'un des membre de la communauté de Machine Learning, Samim Winiger devrait faire partie du programme d'une future Nuit Blanche, voici ces derniers billets qui parlent de ces activités ou il utilise des modèles sophisitiqués de machine learning pour produire des images de rêves et de comédie: 

•  Generating ComicsA Creative Human Machine Collaboration 
• A.I Astrology Predicting Social Characteristics of Famous People using Natural Language Processing 
• Deepdream Music Video 
• Sensual Machines, Adult Computer Vision Experiment 
• ZEN-RRNN - On Meditation & Machines, What our minds teach us about machines  
• TED-RNN — Machine generated TED-TalksIdeas worth generating 

Voici certaines des vidéo générées par certain des modêles utilisés par Samim 

      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: Gaussian Processes with Neil Lawrence

Here is a video on Gaussian Processes by Neil Lawrence from the excellent CVTalks site.

    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.

FastEmbed: Compressive spectral embedding: sidestepping the SVD - implementation -

From the paper:

"...In this paper, we tackle these scalability bottlenecks by focusing on what embeddings are actually used for: computing ℓ2-based pairwise similarity metrics typically used for supervised or unsupervised learning. For example, K-means clustering uses pairwise Euclidean distances, and SVM-based classification uses pairwise inner products. We therefore ask the following question: “Is it possible to compute an embedding which captures the pairwise euclidean distances between the rows of the spectral embedding E= [f(σ1)u1···f(σk)uk], while sidestepping the computationally expensive partial SVD?” We answer this question in the affirmative by presenting a compressive algorithm which directly computes a low-dimensional embedding..."

Compressive spectral embedding: sidestepping the SVD by Dinesh Ramasamy, Upamanyu Madhow

Spectral embedding based on the Singular Value Decomposition (SVD) is a widely used "preprocessing" step in many learning tasks, typically leading to dimensionality reduction by projecting onto a number of dominant singular vectors and rescaling the coordinate axes (by a predefined function of the singular value). However, the number of such vectors required to capture problem structure grows with problem size, and even partial SVD computation becomes a bottleneck. In this paper, we propose a low-complexity it compressive spectral embedding algorithm, which employs random projections and finite order polynomial expansions to compute approximations to SVD-based embedding. For an m times n matrix with T non-zeros, its time complexity is O((T+m+n)log(m+n)), and the embedding dimension is O(log(m+n)), both of which are independent of the number of singular vectors whose effect we wish to capture. To the best of our knowledge, this is the first work to circumvent this dependence on the number of singular vectors for general SVD-based embeddings. The key to sidestepping the SVD is the observation that, for downstream inference tasks such as clustering and classification, we are only interested in using the resulting embedding to evaluate pairwise similarity metrics derived from the euclidean norm, rather than capturing the effect of the underlying matrix on arbitrary vectors as a partial SVD tries to do. Our numerical results on network datasets demonstrate the efficacy of the proposed method, and motivate further exploration of its application to large-scale inference tasks.

A Python implementation of FastEmbed is available at: https://bitbucket.org/dineshkr/fastembed/src/NIPS2015

  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.

True BLAS-3 Performance QRCP using Random Sampling

Using directly randomized sampling in BLAS3 operations, wow !

 

True BLAS-3 Performance QRCP using Random Sampling by Jed A. Duersch, Ming Gu

The dominant contribution to communication complexity in factorizing a matrix using QR with column pivoting is due to column-norm updates that are required to process pivot decisions. We use randomized sampling to approximate this process which dramatically reduces communication in column selection. We also introduce a sample update formula to reduce the cost of sampling trailing matrices. Using our column selection mechanism we observe results that are comparable to those obtained from the QRCP algorithm, but with performance near unpivoted QR. We also demonstrate strong parallel scalability on shared memory multiple core systems using an implementation in Fortran with OpenMP.
This work immediately extends to produce low-rank truncated approximations of large matrices. We propose a truncated QR factorization with column pivoting that avoids trailing matrix updates which are used in current implementations of BLAS-3 QR and QRCP. Provided the truncation rank is small, avoiding trailing matrix updates reduces approximation time by nearly half. By using these techniques and employing a variation on Stewart's QLP algorithm, we develop an approximate truncated SVD that runs nearly as fast as truncated QR.

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.

Nuit Blanche in Review ( September 2015 )

 

What happened since the last Nuit Blanche in Review ( August 2015 ) ?: Well besides knowing that liquid water has been found on Mars. We had a few implementations made available by their authors (and we are getting close to 400 such implementation since we started mentioning them here). We had three theses (congratulations to the new Ph.Ds), a few in-depth posts. We also started the Anomaly Detection tag,  have seen some discussions on Group Testing, found a new highly technical reference page, a new book, an interesting dataset, some jobs, a few videos and the presentations of the Season 3's first Paris Machine Learning Meetup. Enjoy !

Implementations

• Parametric Bilinear Generalized Approximate Message Passing
• Entropy-Scaling Search of Massive Biological Data
• Tensorizing Neural Networks
• Thesis: Fusion of Sparse Reconstruction Algorithms in Compressed Sensing
• Discovering governing equations from data: Sparse identification of nonlinear dynamical systems
• CSPDEs: Compressed-sensing based approximation of solutions to high-dimensional operator equations
• ASimCo: Analysis SimCO Algorithms for Sparse Analysis Model Based Dictionary Learning
• LSS: Learning the Structure for Structured Sparsity

Theses

• Thesis: Unsupervised Feature Learning in Computer Vision by Rostislav Goroshin
• Thesis: Hashing for Large-Scale Structured Data Classification, Lianhua Chi 
• Thesis: Fusion of Sparse Reconstruction Algorithms in Compressed Sensing, Sooraj K. Ambat- implementation -

CS/MF/RandNLA

• Sparsity-based Ankylography for Recovering 3D molecular structures from single-shot 2D scattered light intensity
• CORSING : A theoretical study of COmpRessed SolvING for advection-diffusion-reaction problems
• Dictionary Learning for Blind One Bit Compressed Sensing
• A Theory of Super-Resolution from Short-Time Fourier Transform Measurements 
• Fast Randomized Singular Value Thresholding for Nuclear Norm Minimization

 

Hardware

• FlatCam: Thin, Bare-Sensor Cameras using Coded Aperture and Computation

 

ML

• Training Deep Networks with Structured Layers by Matrix Backpropagation
• Metric Learning: Random Projections and Deep Learning Style 
• Train faster, generalize better: Stability of stochastic gradient descent
• Learning Deep $\ell_0$ Encoders
• NIPS 2015 Accepted Papers: Some Preprints 
• Steps Toward Deep Kernel Methods from Infinite Neural Networks

 

Anomaly Detection

• Anomaly Detection in High Dimensional Data: Hyperspectral data, movies and more...
• Anomaly Detection in Computer Systems using Compressed Measurements

Group Testing

• Group Testing and SAFFRON
• Phase Transitions in Group Testing
• A comment on "Phase Transitions in Group Testing "

LSH

• Locality-sensitive Hashing without False Negatives
• Practical and Optimal LSH for Angular Distance

Highly Technical Site

• A new Highly Technical Reference Page: Probabilistic-Programming.org

Book

• Book: Information Entropy and their Geometric Structures

Dataset

• Data: MindBigData, the "MNIST" of Brain Digits 

 

 

Jobs:

• Jobs: Center for Advanced Mathematics for Energy Research Applications (CAMERA)
• CSjob: PostDoc, Novel Algorithms and Signal Processing, ASTRON & IBM, The Netherlands
• CSJob: PostDoc, Adaptive antenna processing correcting the decoherence effects induced by the fluctuations of the propagating media, Brest, Brittany, France

Videos:

• Saturday Morning Video: Deep Learning and Convolutional Neural Networks, Yann LeCun, Hot Chips 27
• Saturday Morning Videos: Visualizing and Understanding Recurrent Networks, Andrej Karpathy/ Developing better drugs with Deep Learning, Jeffrey Ng/ GPU Software Platform for Deep Learning, Jeremy Appleyard
• Saturday Morning Videos: IPAM workshop on Computational Photography and Intelligent Cameras
• Saturday Morning Videos: Videos and Slides, Deep Learning Summer School, Montreal 2015

Other

• "...Under Certain Circumstances, Liquid Water Has Been Found on Mars..."
•  Talking Machine Season 2 on Kickstarter: Human Conversation about Machine Learning

Paris Machine Learning Meetup

• Tonight: Paris Machine Learning #1 Season 3: "September, When Did That Happen ?"

 

Image credit: NASA/JPL-Caltech/UCLA/MPS/DLR/IDA
This image, taken by NASA's Dawn spacecraft, shows the surface of dwarf planet Ceres from an altitude of 915 miles (1,470 kilometers). The image was taken on August 24, 2015, and has a resolution of 450 feet (140 meters) per pixel.

 

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.

Thesis: Unsupervised Feature Learning in Computer Vision by Rostislav Goroshin

Just fresh out of NYU, here is: Unsupervised Feature Learning in Computer Vision by Rostislav Goroshin

Much of computer vision has been devoted to the question of representation through feature extraction. Ideal features transform raw pixel intensity values to a representation in which common problems such as object identification, tracking, and segmentation are easier to solve. Recently, deep feature hierarchies have proven to be immensely successful at solving many problems in computer vision. In the supervised setting, these hierarchies are trained to solve specific problems by minimizing an objective function of the data and problem specific label information. Recent findings suggest that despite being trained on a specific task, the learned features can be transferred across multiple visual tasks. These findings suggests that there exists a generically useful feature representation for natural visual data. his work aims to uncover the principles that lead to these generic feature representations in the unsupervised setting, which does not require problem specific label information. We begin by reviewing relevant prior work, particularly the literature on auto-encoder networks and energy based learning. We introduce a new regularizer for auto-encoders that plays an analogous role to the partition function in probabilistic graphical models. Next we explore the role of specialized encoder architectures for sparse inference. The remainder of the thesis explores visual feature learning from video. We establish a connection between slow-feature learning and metric learning, and exper- imentally demonstrate that semantically coherent metrics can be learned from natural videos. Finally, we posit that useful features linearize natural image transformations in video. To this end, we introduce a new architecture and loss for training deep feature hierarchies that linearize the transformations observed in unlabeled natural video sequences by learning to predict future frames in the presence of uncertainty.

From Ross'recent work

[1]*New* Learning to Linearize Under Uncertainty
Ross Goroshin, Michael Mathieu, Yann LeCun
[2] Unsupervised Learning of Spatiotemporally Coherent Metrics
Ross Goroshin, Joan Bruna, Jonathan Tompson, David Eigen, Yann LeCun
[3] Unsupervised Feature Learning from Temporal Data
Ross Goroshin, Joan Bruna, Arthur Szlam, Jonathan Tompson, David Eigen, Yann LeCun, NIPS 2014 Deep Learning Workshop, Montreal, QC and ICLR 2015 Workshop, San Diego, CA
[4] Efficient Object Localization Using Convolutional Networks
Jonathan Tompson, Ross Goroshin, Arjun Jain, Yann LeCun, Chris Bregler
[5] Saturating Auto-Encoders
Rostislav Goroshin and Yann LeCun, International Conference on Learning Representations (ICLR 2013), Scottsdale, AZ

 

  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.