Learning the nonlinear geometry of high-dimensional data: Models and algorithms - implementation -

I just realized this paper was on my pile when I saw that Waheed mentioned an implementation of it on his twitter feed.

Learning the nonlinear geometry of high-dimensional data: Models and algorithms by Tong Wu, Waheed U. Bajwa

Modern information processing relies on the axiom that high-dimensional data lie near low-dimensional geometric structures. This paper revisits the problem of data-driven learning of these geometric structures and puts forth two new nonlinear geometric models for data describing "related" objects/phenomena. The first one of these models-suited for mildly nonlinear data-is termed the metric-constrained union-of-subspaces (MC-UoS) model, which straddles the two extremes of the subspace model and the union-of-subspaces model. The second one of these models-suited for highly nonlinear data-is termed the metric-constrained kernel union-of-subspaces (MC-KUoS) model, which generalizes the kernel subspace model. The main contributions of this paper in this regard include the following. First, it motivates and formalizes the problems of MC-UoS and MC-KUoS learning. Second, it presents algorithms that efficiently learn an MC-UoS or an MC-KUoS underlying data of interest. Third, it extends these algorithms to the case when parts of the data are missing. Last, but not least, it reports the outcomes of a series of numerical experiments involving both synthetic and real data that demonstrate the superiority of the proposed geometric models and learning algorithms over existing approaches in the literature. These experiments also help clarify the connections between this work and the literature on (subspace and kernel k-means) clustering.  

An implementation is available here: https://bitbucket.org/SigProcessing/code_wb-tsp2015   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.

Manopt 3.0 released - implementation -

Nicolas just sent me the following:

Dear Igor,

Bamdev (cc) and I just released Manopt 3.0, our Matlab toolbox for optimization on manifolds:

http://www.manopt.org/downloads.html 

We would be delighted if you could announce this major release on your blog once again.

Manopt is a toolbox for optimization on manifolds, with major applications in machine learning and computer vision (low rank constraints, orthogonal matrices, ...). Of course, Manopt can also optimize over linear spaces (and it's quite good at it).

This is non-convex optimization. Yet, more and more papers show that certain classes of non-convex problems on manifolds can be solved to global optimality with local algorithms such as the ones implemented in Manopt. These tools are also routinely used to refine solutions obtained by convex or spectral relaxations, with excellent results.

The toolbox is user friendly, requiring little knowledge about manifolds to get started. See our tutorial and the many examples in the release:

http://www.manopt.org/tutorial.html 

Best,

Nicolas

 
 Sure Nicolas ! As a side note, Manopt even has a tag on Nuit Blanche and it is manopt.

 Here are the changes from Manopt 2.0

 

• Manopt 3.0, packaged November 12, 2016.
• Code moved to GitHub! Now accepting pull requests, and accelerating distribution of patches.
• Bugs caught
• Logic bug in linesearch: lsmem handling corrected thanks to Wen Huang. The default line-search algorithm for steepest descent should now be much faster.
• Logic bug in getGradient when using problem.grad with a different number of inputs compared to problem.cost.
• Corrected logic in plotting step of example low_rank_dist_completion
• obliquefactory, in transposed mode, had an incorrect M.log
• Modifications to core engine
• Added capability to obtain a partial gradient (Euclidean or Riemannian) of a cost function by specifying problem.partialgrad or problem.partialegrad coupled with problem.ncostterms. This is an important step to simplify the future addition of stochastic gradient methods. Use cases are: if problem.cost is expressed as a sum of problem.ncostterms terms, then problem.partialgrad accepts a point x and an index set I so that only the gradient with respect to terms indexed in I is computed and returned.
• Added possibility to define problem.approxgrad, to provide an approximation of the gradient. This can be populated with a generic gradient approximation based on finite differences via approxgradientFD. Solvers do this by default if they need a gradient and none is given. This feature is slow, but may be useful for prototyping. It is slow because Manopt generates an orthonormal basis of the tangent space, and compute a finite difference approximation of the directional derivative along each basis vector to get an approximate gradient (see also next item and new example thomson_problem.)
• getGradient now knows how to compute the gradient if the directional derivatives are accessible. This involves generating an orthonormal basis of the tangent space at the current point, then evaluating the directional derivative along each basis vector and taking the appropriate linear combination. This is very slow, especially for high dimensional manifolds.
• New tools
• lincomb for a generic way of computing a long linear combination of tangent vectors.
• grammatrix to compute the Gram matrix of a collection of tangent vectors.
• orthogonalize to orthogonalize a basis of tangent vectors.
• tangentorthobasis to obtain a random orthonormal basis of a tangent space, generically.
• smallestinconvexhull to compute the smallest tangent vector in the convex hull of a given collection of tangent vectors.
• hessianmatrix to get a matrix representing the Hessian at a point in an orthonormal tangent basis.
• checkretraction allows, for manifolds which have a correct exponential implemented, to verify the order of agreement between the retraction and the exponential, in order to determine numerically if the retraction is first- or second-order.
• New examples
• elliptope_SDP solves SDP's over positive semidefinite matrices with diagonal of 1's. This should run faster than the Max-Cut example for quite a few things.
• elliptope_SDP_complex, same as above for complex matrices. This solves the SDP which appears in PhaseCut and phase synchronization, for example.
• thomson_problem to illustrate the new features that allow to not specify the gradient of the cost (slow, but good for prototyping.)
• New geometries
• skewsymmetricfactory for skew-symmetric matrices (Euclidean geometry
• obliquecomplexfactory, to work with complex matrices whose columns (or rows) all have unit norm
• Modifications to previous behavior
• symfixedrankYYcomplexfactory now has a Riemannian metric matching that of euclideanfactory (it was scaled down by 2 as compared to previous Manopt versions.) This makes it easier to switch between those two geometries. Relevant changes propagated to radio_interferometric_calibration.
• hessianextreme now returns the info structure returned by the internal solver call. The helper tool tangentspherefactory now incorporates extra projections to ensure the vector returned by hessianextreme is indeed a tangent vector (former version could suffer from numerical drift.)
• At the end of generalized_eigenvalue_computation, added a rotation of Xsol to match the definition of generalized eigenvectors (the eigenvalues were fine.)
• Numerous minor improvements; highlights:
• rotationsfactory now has a function M.retr2 which is a second-order retraction.
• spherefactory and related sphere geometries now have a distance function M.dist which is orders of magnitude more accurate for close-by points.
• neldermead now respects options.verbosity less than 2.
• plotprofile / surfprofile have now mostly optional inputs, making them easier to call for a quick glimpse at the cost function.

 
 
 

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.

Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation

We have covered Manopt before several times ( tag Manopt). It now comes to Python. From the paper:

Further successful applications of optimization on manifolds include matrix completion tasks (Vandereycken, 2013; Boumal and Absil, 2015), robust PCA (Podosinnikova et al., 2014), dimension reduction for independent component analysis (ICA) (Theis et al., 2009), kernel ICA (Shen et al., 2007) and similarity learning (Shalit et al., 2012).
Many more applications to machine learning and other elds exist. While a full survey on the usefulness of these methods is well beyond the scope of this manuscript, we highlight that at the time of writing, a search for the term \manifold optimization" on the IEEE Xplore Digital Library lists 1065 results; the Manopt toolbox itself is referenced in 90 papers indexed by Google Scholar.

It looks like that at the time of this writing, it is more like 126 times that the Manopt toolbow has been referenced in Google Scholar.

Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation by  James Townsend, Niklas Koep, Sebastian Weichwald

Optimization on manifolds is a class of methods for optimization of an objective function, subject to constraints which are smooth, in the sense that the set of points which satisfy the constraints admits the structure of a differentiable manifold. While many optimization problems are of the described form, technicalities of differential geometry and the laborious calculation of derivatives pose a significant barrier for experimenting with these methods.
We introduce Pymanopt (available at this https URL), a toolbox for optimization on manifolds, implemented in Python, that---similarly to the Manopt Matlab toolbox---implements several manifold geometries and optimization algorithms. Moreover, we lower the barriers to users further by using automated differentiation for calculating derivative information, saving users time and saving them from potential calculation and implementation errors.

 
 The implementation is here: https://pymanopt.github.io/

 

h/t Nando. 
 
 

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.

Random projections of random manifolds

Looks like some bounds have been tightened. Funny enough, in a matter of a week, I am either talking to or featuring someone from SpaceX, which just happens to deliver today or tomorrow a nanopore sequencer to the international space station. 

Small worlds!

Anyway, getting back to the paper.

Random projections of random manifolds by Subhaneil Lahiri, Peiran Gao, Surya Ganguli

A ubiquitous phenomenon is that interesting signals or data concentrate on low dimensional smooth manifolds inside a high dimensional ambient Euclidean space. Random projections are a simple and powerful tool for dimensionality reduction of such signals and data. Previous, seminal works have studied bounds on how the number of projections needed to preserve the geometry of these manifolds, at a given accuracy, scales with the intrinsic dimensionality, volume and curvature of the manifold. However, such works employ definitions of volume and curvature that are inherently difficult to compute. Therefore such theory cannot be easily tested against numerical simulations to quantitatively understand the tightness of the proven bounds. We instead study the typical distortions arising in random projections of an ensemble of smooth Gaussian random manifolds. In doing so, we find explicitly computable, approximate theoretical bounds on the number of projections required to preserve the geometric structure of these manifolds to a prescribed level of accuracy. Our bounds, while approximate, can only be violated with a probability that is exponentially small in the ambient dimension, and therefore they hold with high probability in most cases of practical interest. Moreover, unlike previous work, we test our theoretical bounds against numerical experiments on the actual geometric distortions that typically occur for random projections of random smooth manifolds. Through this comparison, we find our bounds are tighter than previous results by several orders of magnitude.

  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.

Riemannian stochastic variance reduced gradient on Grassmann manifold - implementation -

 

 

 

Bamdev just sent me the following:

 

Dear Igor,

I wish to share our recent technical report on "Riemannian stochastic variance reduced gradient on Grassmann manifold", available at http://arxiv.org/abs/1605.07367. In this paper, we extend the Euclidean SVRG algorithm to compact Riemannian manifolds. The results are encouraging.

Additionally, the codes are available at https://bamdevmishra.com/codes/rsvrg/. We also provide a template file, Riemannian_svrg.m, that is compatible with the Manopt toolbox [1].


Regards,
Bamdev

[1] http://manopt.org. 

Thanks Bamdev ! Here is the paper: Riemannian stochastic variance reduced gradient on Grassmann manifold by Hiroyuki Kasai, Hiroyuki Sato, Bamdev Mishra

Stochastic variance reduction algorithms have recently become popular for minimizing the average of a large, but finite, number of loss functions. In this paper, we propose a novel Riemannian extension of the Euclidean stochastic variance reduced gradient algorithm (R-SVRG) to a compact manifold search space. To this end, we show the developments on the Grassmann manifold. The key challenges of averaging, addition, and subtraction of multiple gradients are addressed with notions like logarithm mapping and parallel translation of vectors on the Grassmann manifold. We present a global convergence analysis of the proposed algorithm with decay step-sizes and a local convergence rate analysis under fixed step-size with some natural assumptions. The proposed algorithm is applied on a number of problems on the Grassmann manifold like principal components analysis, low-rank matrix completion, and the Karcher mean computation. In all these cases, the proposed algorithm outperforms the standard Riemannian stochastic gradient descent algorithm.

 
 
 

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.

An information theoretic formulation of the Dictionary Learning and Sparse Coding Problems on Statistical Manifolds

  

An information theoretic formulation of the Dictionary Learning and Sparse Coding Problems on Statistical Manifolds by Rudrasis Chakraborty, Monami Banerjee, Victoria Crawford, Baba C. Vemuri

In this work, we propose a novel information theoretic framework for dictionary learning (DL) and sparse coding (SC) on a statistical manifold (the manifold of probability distributions). Unlike the traditional DL and SC framework, our new formulation {\it does not explicitly incorporate any sparsity inducing norm in the cost function but yet yields SCs}. Moreover, we extend this framework to the manifold of symmetric positive definite matrices, $\mathcal{P}_n$. Our algorithm approximates the data points, which are probability distributions, by the weighted Kullback-Leibeler center (KL-center) of the dictionary atoms. The KL-center is the minimizer of the maximum KL-divergence between the unknown center and members of the set whose center is being sought. Further, {\it we proved that this KL-center is a sparse combination of the dictionary atoms}. Since, the data reside on a statistical manifold, the data fidelity term can not be as simple as in the case of the vector-space data. We therefore employ the geodesic distance between the data and a sparse approximation of the data element. This cost function is minimized using an acceleterated gradient descent algorithm. An extensive set of experimental results show the effectiveness of our proposed framework. We present several experiments involving a variety of classification problems in Computer Vision applications. Further, we demonstrate the performance of our algorithm by comparing it to several state-of-the-art methods both in terms of classification accuracy and sparsity.

 
 
 
 

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.

Low-Rank Representation over the Manifold of Curves

Follow the curve:

Low-Rank Representation over the Manifold of Curves by Stephen Tierney, Junbin Gao, Yi Guo, Zhengwu Zhang

In machine learning it is common to interpret each data point as a vector in Euclidean space. However the data may actually be functional i.e.\ each data point is a function of some variable such as time and the function is discretely sampled. The naive treatment of functional data as traditional multivariate data can lead to poor performance since the algorithms are ignoring the correlation in the curvature of each function. In this paper we propose a method to analyse subspace structure of the functional data by using the state of the art Low-Rank Representation (LRR). Experimental evaluation on synthetic and real data reveals that this method massively outperforms conventional LRR in tasks concerning functional data.

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 a Natural Dynamics for Linear Programming

On the "Off the convex path" blog, the recent entry entitled "Nature, Dynamical Systems and Optimization" features Nisheeth Vishnoi's writing and his work on the connection between a dynamical system and a linear programing problem:

The main contribution of this paper is to provide answers to all of these questions: We show that Physarum dynamics can be seen as a steepest-descent type algorithm, however, not in Euclidean space, rather in a space endowed with a Riemannian metric obtained from an entropy-like function

I wonder how this way of looking at nonnegative linear programs can be used to speed up reconstruction solvers in compressive sensing....all this while using molds. This nature/physics based example is eerily similar to the example borrowed from spin glass physics used to design the magic matrices in Compressive Sensing.  Here is the attendant paper: On a Natural Dynamics for Linear Programming by Damian Straszak, Nisheeth K. Vishnoi

In this paper we study dynamics inspired by Physarum polycephalum (a slime mold) for solving linear programs [NTY00, IJNT11, JZ12]. These dynamics are arrived at by a local and mechanistic interpretation of the inner workings of the slime mold and a global optimization perspective has been lacking even in the simplest of instances. Our first result is an interpretation of the dynamics as an optimization process. We show that Physarum dynamics can be seen as a steepest-descent type algorithm on a certain Riemannian manifold. Moreover, we prove that the trajectories of Physarum are in fact paths of optimizers to a parametrized family of convex programs, in which the objective is a linear cost function regularized by an entropy barrier. Subsequently, we rigorously establish several important properties of solution curves of Physarum. We prove global existence of such solutions and show that they have limits, being optimal solutions of the underlying LP. Finally, we show that the discretization of the Physarum dynamics is efficient for a class of linear programs, which include unimodular constraint matrices. Thus, together, our results shed some light on how nature might be solving instances of perhaps the most complex problem in P: linear programming.

 
 

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.

What Happens to a Manifold Under a Bi-Lipschitz Map?

 

What Happens to a Manifold Under a Bi-Lipschitz Map by  Armin Eftekhari, Michael B. Wakin

We study geometric and topological properties of the image of a smooth submanifold of $\mathbb{R}^{n}$ under a bi-Lipschitz map to $\mathbb{R}^{m}$. In particular, we characterize how the dimension, diameter, volume, and reach of the embedded manifold relate to the original. Our main result establishes a lower bound on the reach of the embedded manifold in the case where $m \le n$ and the bi-Lipschitz map is linear. We discuss implications of this work in signal processing and machine learning, where bi-Lipschitz maps on low-dimensional manifolds have been constructed using randomized linear operators.

 
 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.

Guarantees of Riemannian Optimization for Low Rank Matrix Recovery

At last, the use of phase transitions to figure out if manifold based techniques can do well:

Guarantees of Riemannian Optimization for Low Rank Matrix Recovery by Ke Wei, Jian-Feng Cai, Tony F. Chan, Shingyu Leung

We establish theoretical recovery guarantees of a family of Riemannian optimization algorithms for low rank matrix recovery, which is about recovering an $m\times n$ rank $r$ matrix from $p < mn$ number of linear measurements. The algorithms are first interpreted as the iterative hard thresholding algorithms with subspace projections. Then based on this connection, we prove that if the restricted isometry constant $R_{3r}$ of the sensing operator is less than $C_\kappa /\sqrt{r}$ where $C_\kappa$ depends on the condition number of the matrix, the Riemannian gradient descent method and a restarted variant of the Riemannian conjugate gradient method are guaranteed to converge to the measured rank $r$ matrix provided they are initialized by one step hard thresholding. Empirical evaluation shows that the algorithms are able to recover a low rank matrix from nearly the minimum number of measurements necessary.

  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.

Efficient Clustering on Riemannian Manifolds: A Kernelised Random Projection Approach

  Interesting ! Large speedups for random projections on Riemannian manifolds.
 

 

 

Efficient Clustering on Riemannian Manifolds: A Kernelised Random Projection Approach by  Kun Zhao, Azadeh Alavi, Arnold Wiliem, Brian C. Lovell

Reformulating computer vision problems over Riemannian manifolds has demonstrated superior performance in various computer vision applications. This is because visual data often forms a special structure lying on a lower dimensional space embedded in a higher dimensional space. However, since these manifolds belong to non-Euclidean topological spaces, exploiting their structures is computationally expensive, especially when one considers the clustering analysis of massive amounts of data. To this end, we propose an efficient framework to address the clustering problem on Riemannian manifolds. This framework implements random projections for manifold points via kernel space, which can preserve the geometric structure of the original space, but is computationally efficient. Here, we introduce three methods that follow our framework. We then validate our framework on several computer vision applications by comparing against popular clustering methods on Riemannian manifolds. Experimental results demonstrate that our framework maintains the performance of the clustering whilst massively reducing computational complexity by over two orders of magnitude in some cases.

 
 

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.

Sequential Information Guided Sensing / Info-Greedy sequential adaptive compressed sensing

 

Finding changes in the compressed domain through adaptive sampling is what those two preprints are looking into:

Sequential Information Guided Sensing by Ruiyang Song, Yao Xie, Sebastian Pokutta

We study the value of information in sequential compressed sensing by characterizing the performance of sequential information guided sensing in practical scenarios when information is inaccurate. In particular, we assume the signal distribution is parameterized through Gaussian or Gaussian mixtures with estimated mean and covariance matrices, and we can measure compressively through a noisy linear projection or using one-sparse vectors, i.e., observing one entry of the signal each time. We establish a set of performance bounds for the bias and variance of the signal estimator via posterior mean, by capturing the conditional entropy (which is also related to the size of the uncertainty), and the additional power required due to inaccurate information to reach a desired precision. Based on this, we further study how to estimate covariance based on direct samples or covariance sketching. Numerical examples also demonstrate the superior performance of Info-Greedy Sensing algorithms compared with their random and non-adaptive counterparts.

 and earlier:

 

Info-Greedy sequential adaptive compressed sensing by Gabor Braun, Sebastian Pokutta, Yao Xie

We present an information-theoretic framework for sequential adaptive compressed sensing, Info-Greedy Sensing, where measurements are chosen to maximize the extracted information conditioned on the previous measurements. We lower bound the expected number of measurements for a given accuracy by drawing a connection between compressed sensing and complexity theory of sequential optimization, and derive various forms of Info-Greedy Sensing algorithms under different signal and noise models, as well as under the sparse measurement vector constraint. We also show the Info-Greedy optimality of the bisection algorithm for k-sparse signals, as well as that of the iterative algorithm which measures using the maximum eigenvector of the posterior Gaussian signals. For GMM signals, a greedy heuristic for the GMM signal is nearly Info-Greedy optimal compared to the gradient descent approach based on the minimum mean square error (MMSE) matrix. Numerical examples demonstrate the good performance of the proposed algorithms using simulated and real data.

 
 

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.

Anomaly Detection in Computer Systems using Compressed Measurements

Here is another area of application of compressive measurements and anomaly inference from said measurements in computer systems.

 

 

 

Anomaly Detection in Computer Systems using Compressed Measurements by  Tingshan Huang,  Naga Kandasamy and Harish Sethu.

Online performance monitoring of computer systems incurs a variety of costs: the very act of monitoring a system interferes with its performance and if the information is transmitted to a monitoring station for analysis and logging, this consumes network bandwidth and disk space. Compressive sampling-based schemes can help reduce these costs on the local machine by acquiring data directly from the system in a compressed form, and in a computationally efficient way. This paper focuses on reducing the computational cost associated with recovering the original signal from the transmitted sample set at the monitoring station for anomaly detection. Towards this end, we show that the compressed samples preserve, in an approximate form, properties such as mean, variance, as well as correlation between data points in the original full-length signal.
We then use this result to detect changes in the original signal that could be indicative of an underlying anomaly such as abrupt changes in magnitude and gradual trends without the need to recover the full-length data. We illustrate the usefulness of our approach via case studies involving IBM’s Trade Performance Benchmark using signals from the disk and memory subsystems. Experiments indicate that abrupt changes can be detected using a compressed sample size of 25% with a hit rate of 95% for a fixed false alarm rate of 5%; trends can be detected within aconfidence interval of 95% using a sample size of only 6%

  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.

Manopt 2.0: A Matlab tool­box for opti­mization on manifolds - implementation -

Nicolas Boumal just let me know of the following:

Dear Igor,

Bamdev (cc) and I develop Manopt, a Matlab toolbox for optimization on manifolds.

You featured a nice post about it on Nuit Blanche on May 28, 2013:

http://nuit-blanche.blogspot.fr/2013/05/manopt-matlab-toolbox-for-optimization.html

Over the last two years, the toolbox has improved vastly, in part thanks to our great contributors, and we just released Manopt 2.0 yesterday: 

http://www.manopt.org/downloads.html

http://www.manopt.org/about.html#contributors

We would be delighted if you could announce this major release on your blog once again.

Manopt is a toolbox for optimization on manifolds, that is, on smooth nonlinear spaces. This is ideal to handle rank constraints and orthogonality constraints, to name a few, with major applications in large-scale machine learning, computer vision, numerical linear algebra and scientific computing. Generically, it is an excellent paradigm to handle symmetry and invariance in optimization. Of course, Manopt can also optimize over linear spaces (and it's quite good at it). It is also a powerful way to refine ballpark estimates obtained from relaxations.

The toolbox is user friendly, requiring little knowledge about manifolds to get started. See our tutorial and the many examples in the release: 

http://www.manopt.org/tutorial.html

For a brief overview of what optimization on manifolds is about, this blog post may be a good start:

https://afonsobandeira.wordpress.com/2015/03/16/optimizing-in-smooth-waters-optimization-on-manifolds/

We hope you may find this to be of interest for Nuit Blanche's readership.

Thank you for your time,

Nicolas

Sure thing Nicolas and Bamdev !

From the About page:

Things users do with Manopt

We see a growing number of papers in various disciplines where researchers use Manopt. A list is available on Google Scholar. We single out a few projects we think illustrate some of the flexibility of the toolbox:

• Artiom Kovnatsky, Klaus Glashoff and Michael M. Bronstein proposed MADMM: a generic algorithm for non-smooth optimization on manifolds. This is essentially ADMM, where one of the steps is smooth optimization on a manifold ; that step is performed using Manopt.
• Reshad Hosseini and Suvrit Sra released a paper entitled Manifold Optimization for Gaussian Mixture Models. They address the important problem of estimating the distribution of data, when it is assumed to be sampled from a mixture (linear combination) of Gaussian distributions. See their MixEst project page for code and more. The same authors also developed the Geometric Optimization Toolbox (GOPT), aimed at optimization over the manifold of positive definite matrices. This includes a Riemannian BFGS algorithm.
• Vris Yuen-Lam Cheung, Dmitriy Drusvyatskiy, Nathan Krislock and Henry Wolkowicz consider a sensor network localization problem. They propose a smart way of obtaining a cheap initial guess, then refine this ballpark estimate to high accuracy with Manopt. They find that neither works very well without the other. The general idea of combining smart spectral or convex formulations to obtain rough (but controllable) estimates, then refining these using Manopt, is successful in many applications.

but also 

Related software

• GenRTR is the Generic Riemannian Trust-Region package for Matlab (it is included in a slightly modified form in Manopt) ;
• GROPT is a Riemannian optimization package written in C++ (with mex interface to Matlab), by Wen Huang and Kyle Gallivan ;
• GOPT is designed for optimization over positive definite matrices.
• SGMIN performs Stiefel-Grassmann optimization ;
• GrassmannOptim is an R-package for optimization on the Grassmann manifold ;
• Optman hosts a collection of algorithms from Rice University for optimization with orthogonality constraints ;
• Traian Abrudan has code for optimization under unitary matrix constraints ;
• LORM is a C++ toolbox for global optimization of polynomials on the sphere and the special orthogonal group.
• Your code? Let us know!

 

  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.

Riemannian preconditioning for tensor and matrix completion - implementation(s) -

 

Bamdev just sent me the following: 

 

 Dear Igor,

I wish to share our recent technical report on "Riemannian preconditioning for tensor completion", available at http://arxiv.org/abs/1506.02159. The results are promising.


It works with the fixed-rank Tucker manifold by endowing it with a "preconditioned" Riemannian geometry. The preconditioned geometry results from exploiting the two fundamental structures of the completion problem, i.e.,
1) the quadratic structure of the cost function and
2) the non-uniqueness of Tucker decomposition.


The code is available at http://bamdevmishra.com/codes/tensorcompletion/. It is built on the Manopt toolbox for optimization on manifolds.

The work actually builds upon the earlier work on matrix completion "R3MC: A Riemannian three-factor algorithm for low-rank matrix completion", available at http://arxiv.org/abs/1306.2672. The code is at http://bamdevmishra.com/codes/r3mc/.


The general preconditioning idea is motivated in "Riemannian preconditioning", available at http://arxiv.org/abs/1405.6055. 

Regards,
Bamdev

Thanks Bamdev ! Here are the attendant papers:

 

Riemannian preconditioning for tensor completion by Hiroyuki Kasai, Bamdev Mishra

We propose a novel Riemannian preconditioning approach for the tensor completion problem with rank constraint. A Riemannian metric or inner product is proposed that exploits the least-squares structure of the cost function and takes into account the structured symmetry in Tucker decomposition. The specific metric allows to use the versatile framework of Riemannian optimization on quotient manifolds to develop a preconditioned nonlinear conjugate gradient algorithm for the problem. To this end, concrete matrix representations of various optimization-related ingredients are listed. Numerical comparisons suggest that our proposed algorithm robustly outperforms state-of-the-art algorithms across different problem instances encompassing various synthetic and real-world datasets.

R3MC: A Riemannian three-factor algorithm for low-rank matrix completion by B. Mishra, R. Sepulchre

We exploit the versatile framework of Riemannian optimization on quotient manifolds to develop R3MC, a nonlinear conjugate-gradient method for low-rank matrix completion. The underlying search space of fixed-rank matrices is endowed with a novel Riemannian metric that is tailored to the least-squares cost. Numerical comparisons suggest that R3MC robustly outperforms state-of-the-art algorithms across different problem instances, especially those that combine scarcely sampled and ill-conditioned data.

 

Riemannian preconditioning by Bamdev Mishra, Rodolphe Sepulchre

The paper exploits a basic connection between sequential quadratic programming and Riemannian gradient optimization to address the general question of selecting a metric in Riemannian optimization, in particular when the Riemannian structure is sought on a quotient manifold. The proposed method is shown to be particularly insightful and efficient in quadratic optimization with orthogonality and/or rank constraints, which covers most current applications of Riemannian optimization in matrix manifolds.

 

    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.

Compressed Manifold Modes for Mesh Processing - implementation -

Kiran Varanasi mentioned it on the Google+ Community. He also said:

Compressed manifold modes are compressed eigenfunctions of the Laplace-Beltrami operator on 3D manifold surfaces. They constitute a novel functional basis, called the compressed manifold basis, where each function has local support. We derive a method, based on ADMM, for computing compressed manifold modes (CMMs) for discrete polyhedral 3D meshes. We show that CMMs identify key shape features, yielding an intuitive understanding of the basis for a human observer, where a shape can be processed as a collection of parts. We demonstrate various applications in 3D geometry processing. Our paper is published at the Symposium of Geometry Processing (SGP) 2014. We release the source-code for the method.

Please also refer to "Compressed modes for variational problems in mathematics and physics" - Ozolins, Lai, Caflisch & Osher, PNAS 2013.

Prof. Stan Osher's talk on their PNAS paper (and more) can be found here:

http://nuit-blanche.blogspot.fr/2013/08/videos-and-slides-sahd-2013-duke.html

Thanks Kiran ! Here is the paper and attendant implementation:
 

Compressed Manifold Modes for Mesh Processing by Thomas Neumann, Kiran Varanasi, Christian Theobalt, Marcus Magnor, and Markus Wacker

This paper introduces compressed eigenfunctions of the Laplace-Beltrami operator on 3D manifold surfaces. They constitute a novel functional basis, called the compressed manifold basis, where each function has local support. We derive an algorithm, based on the alternating direction method of multipliers (ADMM), to compute this basis on a given triangulated mesh. We show that compressed manifold modes identify key shape features, yielding an intuitive understanding of the basis for a human observer, where a shape can be processed as a collection of parts. We evaluate compressed manifold modes for potential applications in in shape matching and mesh abstraction. Our results show that this basis has distinct advantages over existing alternatives, indicating high potential for a wide range of use-cases in mesh processing.

The project page with implementation 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.

MOUSSE: Multiscale Online Union of SubSpaces Estimation - implementation -

Manifold signal processing here we are. From the paper: 

From this video, it is clear that we are effectively tracking the dynamics of the submanifold, and keeping the representation parsimonious so the number of subsets used by our model is proportional to the curvature of the submanifold.

wow!

That attendant paper is: Multiscale Online Tracking of Manifolds by Yao Xie, Jiaji Huang, Rebecca Willett

This paper describes a Multiscale Online Union of SubSpaces Estimation (MOUSSE) algorithm for online tracking ofa time-varying manifold. MOUSSE uses linear subsets of lowdimensional hyperplanes to approximate a manifold embedded ina high-dimensional space. Each subset corresponds to the leafnode in a binary tree which encapsulates the multiresolution analysis underlying the proposed algorithm. The tree structure andparameters of the subsets are estimated and sequentially updatedusing a stream of noisy samples. For each update, MOUSSE requires only simple linear computations. The update of each hyperplane in the estimate is computed via gradient descent on theGrassmannian manifold. Numerical simulations demonstrate thestrong performance of MOUSSE in tracking a time-varying manifold.

and a related one: Changepoint detection for high-dimensional time series with missing data by Yao Xie, Jiaji Huang, Rebecca Willett

This paper describes a novel approach to change-point detection when the observed high-dimensional data may have missing elements. The performance of classical methods for change-point detection typically scales poorly with the dimensionality of the data, so that a large number of observations are collected after the true change-point before it can be reliably detected. Furthermore, missing components in the observed data handicap conventional approaches. The proposed method addresses these challenges by modeling the dynamic distribution underlying the data as lying close to a time-varying low-dimensional submanifold embedded within the ambient observation space. Specifically, streaming data is used to track a submanifold approximation, measure deviations from this approximation, and calculate a series of statistics of the deviations for detecting when the underlying manifold has changed in a sharp or unexpected manner. The approach described in this paper leverages several recent results in the field of high-dimensional data analysis, including subspace tracking with missing data, multiscale analysis techniques for point clouds, online optimization, and change-point detection performance analysis. Simulations and experiments highlight the robustness and efficacy of the proposed approach in detecting an abrupt change in an otherwise slowly varying low-dimensional manifold.

The project page for MOUSSE and attendant implementation can be found here.

Yao Xie made a presentation of it for ITA, here it is:

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.