Published on Wed Feb 25 2015

On Convolutional Approximations to Linear Dimensionality Reduction Operators for Large Scale Data Processing

Swayambhoo Jain, Jarvis Haupt

In this paper, we examine the problem of approximating a general linear dimensionality reduction (LDR) operator. We establish a fundamental result, that most large LDR matrices in fact cannot be well approximated by partial circulant matrices. We then propose a natural

0
0
0
Abstract

In this paper, we examine the problem of approximating a general linear dimensionality reduction (LDR) operator, represented as a matrix $A \in \mathbb{R}^{m \times n}$ with , by a partial circulant matrix with rows related by circular shifts. Partial circulant matrices admit fast implementations via Fourier transform methods and subsampling operations; our investigation here is motivated by a desire to leverage these potential computational improvements in large-scale data processing tasks. We establish a fundamental result, that most large LDR matrices (whose row spaces are uniformly distributed) in fact cannot be well approximated by partial circulant matrices. Then, we propose a natural generalization of the partial circulant approximation framework that entails approximating the range space of a given LDR operator over a restricted domain of inputs, using a matrix formed as a product of a partial circulant matrix having rows and a 'post processing' matrix. We introduce a novel algorithmic technique, based on sparse matrix factorization, for identifying the factors comprising such approximations, and provide preliminary evidence to demonstrate the potential of this approach.

Thu Jun 03 2021
Machine Learning
Nonlinear Matrix Approximation with Radial Basis Function Components
We introduce and investigate matrix approximation by decomposition into a sum of radial basis function (RBF) components. An RBF component is a generalization of the outer product between a pair of vectors. We provide extensive empirical evidence of the effectiveness of the RBF decomposition and that of the gradient-based fitting algorithm.
2
0
0
Tue Nov 02 2010
Machine Learning
A Very Fast Algorithm for Matrix Factorization
High-dimensional data are prevalent across many application areas. Such data generate an ever-increasing demand for methods of dimension reduction. Our algorithm uses a gradient-based approach which can be used with an arbitrary loss function provided the latter is differentiable.
0
0
0
Thu Oct 29 2015
Machine Learning
The Singular Value Decomposition, Applications and Beyond
singular value decomposition (SVD) is not only a classical theory inMatrix computation and analysis, but also is a powerful tool in machine learning and modern data analysis. In this tutorial we first study the basic notion of SVD and then show the central role of SVA in
0
0
0
Tue May 16 2017
Machine Learning
The Incremental Multiresolution Matrix Factorization Algorithm
Multiresolution analysis and matrix factorization are foundational tools in computer vision. New algorithm uncovers such structure one feature at a time, and hence scales well to large matrices.
0
0
0
Tue Apr 14 2015
Machine Learning
Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients
Nonlinear component analysis such as kernel PCA and KCCA can not scale up to big datasets. We propose a simple, computationally efficient, and memory friendly algorithm based on the "doubly stochastic gradients"
0
0
0
Wed Oct 01 2014
Machine Learning
Generalized Low Rank Models
Principal components analysis (PCA) is a well-known technique forroximating a tabular data set by a low rank matrix. Here, we extend the idea of PCA to handle arbitrary data sets consisting of numerical, Boolean, categorical, ordinal, and other data types.
0
0
0