Page Views on Nuit Blanche since July 2010







Please join/comment on the Google+ Community (1561), the CompressiveSensing subreddit (920), the Facebook page (70 likes), the LinkedIn Compressive Sensing group (3353) or the Advanced Matrix Factorization Group (1066)

Wednesday, September 02, 2015

Sparsity-based Ankylography for Recovering 3D molecular structures from single-shot 2D scattered light intensity

If the following paper is telling you anything, it is to never listen to anyone who thinks something is impossible because they cannot discuss rationally their model priors. For context here are two blog entries of a few years back on the subject of Ankylography reconstruction.
 And now, let us read the fantastic job of Maor Mutzafi, Yoav Shechtman, Yonina Eldar, Oren Cohen & Mordechai Segev !
 


Sparsity-based Ankylography for Recovering 3D molecular structures from single-shot 2D scattered light intensity by Maor Mutzafi, Yoav Shechtman, Yonina C. Eldar, Oren Cohen & Mordechai Segev

  Deciphering the three-dimensional (3D) structure of complex molecules is of major importance, typically accomplished with X-ray crystallography. Unfortunately, many important molecules cannot be crystallized, hence their 3D structure is unknown. Ankylography presents an alternative, relying on scattering an ultrashort X-ray pulse off a single molecule before it disintegrates, measuring the far-field intensity on a two-dimensional surface, followed by computation. However, significant information is absent due to lower dimensionality of the measurements and the inability to measure the phase. Recent Ankylography experiments attracted much interest, but it was counter-argued that Ankylography is valid only for objects containing a small number of volume pixels. Here, we propose a sparsity-based approach to reconstruct the 3D structure of molecules. Sparsity is natural for Ankylography, because molecules can be represented compactly in stoichiometric basis. Utilizing sparsity, we surpass current limits on recoverable information by orders of magnitude, paving the way for deciphering the 3D structure of macromolecules.
 
 
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.

Tuesday, September 01, 2015

Parametric Bilinear Generalized Approximate Message Passing - implementation -

Today, we have an extension of BiG-AMP, woohoo !

 


Parametric Bilinear Generalized Approximate Message Passing by Jason T. Parker, Yan Shou, Philip Schniter
We propose a scheme to estimate the parameters bi and cj of the bilinear form zm=i,jbiz(i,j)mcj from noisy measurements {ym}Mm=1, where ym and zm are related through an arbitrary likelihood function and z(i,j)m are known. Our scheme is based on generalized approximate message passing (G-AMP): it treats bi and cj as random variables and z(i,j)m as an i.i.d.\ Gaussian tensor in order to derive a tractable simplification of the sum-product algorithm in the large-system limit. It generalizes previous instances of bilinear G-AMP, such as those that estimate matrices B and C from a noisy measurement of Z=BC, allowing the application of AMP methods to problems such as self-calibration, blind deconvolution, and matrix compressive sensing. Numerical experiments confirm the accuracy and computational efficiency of the proposed approach.


The implementation can be found here: http://gampmatlab.wikia.com/wiki/Generalized_Approximate_Message_Passing 


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.

Dictionary Learning for Blind One Bit Compressed Sensing

So this is how the Great Convergence occur: step-by-step, this article could have been called Sparse Coding for one bit signals if it were to be written for a matrix factorization crowd or supervised learning of a shallow network for sparse binary signals if it were to be sold to the Machine Learning community. In the end, it doesn't matter:   


This letter proposes a dictionary learning algorithm for blind one bit compressed sensing. In the blind one bit compressed sensing framework, the original signal to be reconstructed from one bit linear random measurements is sparse in an unknown domain. In this context, the multiplication of measurement matrix $\Ab$ and sparse domain matrix Φ, \ie $\Db=\Ab\Phi$, should be learned. Hence, we use dictionary learning to train this matrix. Towards that end, an appropriate continuous convex cost function is suggested for one bit compressed sensing and a simple steepest-descent method is exploited to learn the rows of the matrix $\Db$. Experimental results show the effectiveness of the proposed algorithm against the case of no dictionary learning, specially with increasing the number of training signals and the number of sign measurements.
 
 
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.

Monday, August 31, 2015

Nuit Blanche in Review ( August 2015 )

Since the last Nuit Blanche in Review ( July 2015 ) we saw the birth of GitXiv and a few implementations.

 We also had some in-depth studies, with in particular some on-going clues of The Great Convergence in action as well as some compressive sensing hardware:

Jobs:
Theses:
Videos/Slides/proceedings

Credit: NASA/Johns Hopkins University Applied Physics Laboratory/Southwest Research Institute

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.

Unsupervised Feature Selection on Data Streams / Streaming Anomaly Detection Using Randomized Matrix Sketching

Today, we see the use of streaming algorithms to figure out anomaly detection or unsupervised feature selection.


Streaming Anomaly Detection Using Randomized Matrix Sketching by Hao Huang, Shiva Kasiviswanathan.
Data is continuously being generated from sources such as machines, network traffic, application logs, etc. Timely and accurate detection of anomalies in massive data streams have important applications such as in preventing machine failures, intrusion detection, and dynamic load balancing. In this paper, we introduce a novel anomaly detection algorithm, which can detect anomalies in a streaming fashion by making only one pass over the data while utilizing limited storage. The algorithm uses ideas from matrix sketching and randomized low-rank matrix approximations to maintain, in a streaming model, a set of few orthogonal vectors that form a good approximate basis for the data. Using this constructed orthogonal basis, anomalies in new incoming data are detected based on a simple reconstruction error test. We theoretically prove that our algorithm compares favorably with an offline approach based on global singular value decomposition updates. The experimental results show the effectiveness and efficiency of our approach over other popular fast anomaly detection methods.

Massive data streams are continuously being generated from sources such as social media, broadcast news, etc., and typically these datapoints lie in high-dimensional spaces (such as the vocabulary space of a language). Timely and accurate feature subset selection in these massive data streams has important applications in model interpretation, computational/storage cost reduction, and generalization enhancement. In this paper, we introduce a novel unsupervised feature selection approach on data streams that selects important features by making only one pass over the data while utilizing limited storage. The proposed algorithm uses ideas from matrix sketching to e ciently maintain a low-rank approximation of the observed data and applies regularized regression on this approximation to identify the important features. We theoretically prove that our algorithm is close to an expensive offline approach based on global singular value decompositions. The experimental results on a variety of text and image datasets demonstrate the excellent ability of our approach to identify important features even in presence of concept drifts and also its efficiency over other popular scalable feature selection algorithms.

Previously:


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.

Friday, August 28, 2015

Machine Learning and Homomorphic Encryption - implementation -

We have mentioned homomorphic encryption here on Nuit Blanche mostly because of Andrew McGregor et al's work on the subject (see references below). Today, we have a Machine Learning approach using this encoding strategy, which in effect is not really that far from the idea of homomorphic sketches  or random projections for low dimensional manifolds. Without further ado:


A review of homomorphic encryption and software tools for encrypted statistical machine learning by  Louis J. M. Aslett, Pedro M. Esperança, Chris C. Holmes

Recent advances in cryptography promise to enable secure statistical computation on encrypted data, whereby a limited set of operations can be carried out without the need to first decrypt. We review these homomorphic encryption schemes in a manner accessible to statisticians and machine learners, focusing on pertinent limitations inherent in the current state of the art. These limitations restrict the kind of statistics and machine learning algorithms which can be implemented and we review those which have been successfully applied in the literature. Finally, we document a high performance R package implementing a recent homomorphic scheme in a general framework.


Encrypted statistical machine learning: new privacy preserving methods  by Louis J. M. Aslett, Pedro M. Esperança, Chris C. Holmes

We present two new statistical machine learning methods designed to learn on fully homomorphic encrypted (FHE) data. The introduction of FHE schemes following Gentry (2009) opens up the prospect of privacy preserving statistical machine learning analysis and modelling of encrypted data without compromising security constraints. We propose tailored algorithms for applying extremely random forests, involving a new cryptographic stochastic fraction estimator, and na\"{i}ve Bayes, involving a semi-parametric model for the class decision boundary, and show how they can be used to learn and predict from encrypted data. We demonstrate that these techniques perform competitively on a variety of classification data sets and provide detailed information about the computational practicalities of these and other FHE methods.
 An implementation in R is available here:
 References:
  h/t Albert Swart
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.

Mash: Fast genome distance estimation using the MinHash algorithm - implementation -




In this Sunday Morning Insight: What Happens When You Cross into P Territory ?, I mentioned this article on using LSH for genome alignment from long read technology (PacBio RS II or Oxford Nanopore MiNion).

Assembling Large Genomes with Single-Molecule Sequencing and Locality Sensitive Hashing by Konstantin Berlin, Sergey Koren, Chen-Shan Chin, James Drake, Jane M Landolin, Adam M Phillippy

while assembling the genome is important, with cheap and fast long reads, the goalpost is now slowly moving to the unsupervised learning of groups of genomes. That type of unsupervised learning can only be enabled with the right dimensionality reduction technique, today it is MinHash

Here is Mash: Fast genome distance estimation using the MinHash algorithm from Adam Phillippy's group.



Wonder how MinHash works, check this write-up by Matthew Casperson on MinHash for dummies.

Related:

      
    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.

    Thursday, August 27, 2015

    Toward a unified theory of sparse dimensionality reduction in Euclidean space

     So we are now converging toward a theory for using sparse random projections for a variety of problems.
     
    Toward a unified theory of sparse dimensionality reduction in Euclidean space  by Jean Bourgain, Sjoerd Dirksen, Jelani Nelson

    Let ΦRm×n be a sparse Johnson-Lindenstrauss transform [KN14] with s non-zeroes per column. For a subset T of the unit sphere, ε(0,1/2) given, we study settings for m,s required to ensure
    EΦsupxTΦx221<ε,
    i.e. so that Φ preserves the norm of every xT simultaneously and multiplicatively up to 1+ε. We introduce a new complexity parameter, which depends on the geometry of T, and show that it suffices to choose s and m such that this parameter is small. Our result is a sparse analog of Gordon's theorem, which was concerned with a dense Φ having i.i.d. Gaussian entries. We qualitatively unify several results related to the Johnson-Lindenstrauss lemma, subspace embeddings, and Fourier-based restricted isometries. Our work also implies new results in using the sparse Johnson-Lindenstrauss transform in numerical linear algebra, classical and model-based compressed sensing, manifold learning, and constrained least squares problems such as the Lasso.
     
    h/t Laurent Jacques
     
    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.

    Comparative Analysis of Scattering and Random Features in Hyperspectral Image Classification

    The great convergence is happenng right under our eyes. Here is a comparison between Random Features and Scattering Transform features for classification of hyperspectral datasets:

    Hyperspectral images (HSI) contains extremely rich spectral and spatial information that offers great potential to discriminate between various land cover classes. The inherent high dimensionality and insufficient training samples in such images introduces Hughes phenomenon. In order to deal with this issue, several preprocessing techniques have been integrated in processing chain of HSI prior to classification. Supervised feature extraction is one such method which mitigates the curse of dimensionality induced by Hughes effect. In recent years, new strategies for feature extraction based on scattering transform and Random Kitchen Sink have been introduced, which can be used in context of hyperspectral image classification. This paper presents a comparative analysis of scattering and random features in hyperspectral image classification. The classification is performed using simple linear classifier such as Regularized Least Square (RLS) accessed through Grand Unified Regularized Least Squares (GURLS) library. The proposed approach is tested on two standard hyperspectral datasets namely, Salinas-A and Indian Pines subset scene captured by NASAs AVIRIS sensor (Airborne Visible Infrared Imaging Spectrometer). In order to show the effectiveness of proposed method, a comparative analysis is performed based on feature dimension, classification accuracy measures and computational time. From the comparative assessment, it is evident that classification using random features achieve excellent classification results with less computation time when compared with raw pixels(without feature extraction) and scattering features for both the datasets.
     
     
    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.

    Printfriendly