Randomized Online CP Decomposition

• URL: http://arxiv.org/abs/2007.10798v1
• Date: Tue, 21 Jul 2020 13:41:27 GMT
• Title: Randomized Online CP Decomposition
• Authors: Congbo Ma, Xiaowei Yang, Hu Wang
• Abstract summary: A novel CP decomposition algorithm called randomized online CP decomposition (ROCP) is proposed in this paper. ROCP avoids forming full Khatri-Rao product, which leads to boost the speed largely and reduce memory usage.
• Score: 13.425121208828044
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: CANDECOMP/PARAFAC (CP) decomposition has been widely used to deal with multi-way data. For real-time or large-scale tensors, based on the ideas of randomized-sampling CP decomposition algorithm and online CP decomposition algorithm, a novel CP decomposition algorithm called randomized online CP decomposition (ROCP) is proposed in this paper. The proposed algorithm can avoid forming full Khatri-Rao product, which leads to boost the speed largely and reduce memory usage. The experimental results on synthetic data and real-world data show the ROCP algorithm is able to cope with CP decomposition for large-scale tensors with arbitrary number of dimensions. In addition, ROCP can reduce the computing time and memory usage dramatically, especially for large-scale tensors.

Related papers

• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  We show how to analyze the behavior of distributed gradient descent algorithms in the presence of adversarial corruptions. We show how to use ideas from (lazy) mirror descent to design a corruption-tolerant distributed optimization algorithm. Experiments based on linear regression, support vector classification, and softmax classification on the MNIST dataset corroborate our theoretical findings.
  arXiv  Detail & Related papers  (2024-07-19T08:29:12Z)
• Oblivious subspace embeddings for compressed Tucker decompositions [8.349583867022204]
  This work establishes general Johnson-Lindenstrauss type guarantees for the estimation of Tucker decompositions. On moderately large face image and fMRI neuroimaging datasets, empirical results show that substantial dimension reduction is possible.
  arXiv  Detail & Related papers  (2024-06-13T17:58:32Z)
• Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
  We present a novel distributed computing framework that is robust to slow compute nodes, and is capable of both approximate and exact computation of linear operations. We propose a sequential decoding algorithm designed to handle real valued data while maintaining low computational complexity for recovery. We demonstrate the potential applications of this framework in various contexts, such as large-scale matrix multiplication and black-box optimization.
  arXiv  Detail & Related papers  (2023-09-01T18:02:04Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  We propose a novel algorithm that uses a random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel. Our algorithm provides at least a 100-fold speedup over KIP and can run on a single GPU. Our new method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms in accuracy over a range of large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-21T15:56:13Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  We propose a family of dynamic programming (RDP) randomized for scaling structured models to tens of thousands of latent states. Our method is widely applicable to classical DP-based inference. It is also compatible with automatic differentiation so can be integrated with neural networks seamlessly.
  arXiv  Detail & Related papers  (2021-12-07T11:26:41Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  Existing implementations of KRR require that all the data is stored in the main memory. We propose StreaMRAK - a streaming version of KRR. We present a showcase study on two synthetic problems and the prediction of the trajectory of a double pendulum.
  arXiv  Detail & Related papers  (2021-08-23T21:03:09Z)
• Tensor Principal Component Analysis in High Dimensional CP Models [3.553493344868413]
  We propose new algorithms for tensor CP decomposition with theoretical guarantees under mild incoherence conditions. The composite PCA applies the principal component or singular value decompositions twice, first to a matrix unfolding of the tensor data to obtain singular vectors and then to the matrix folding of the singular vectors obtained in the first step. We show that our implementations on synthetic data demonstrate significant practical superiority of our approach over existing methods.
  arXiv  Detail & Related papers  (2021-08-10T03:24:32Z)
• A Coupled Random Projection Approach to Large-Scale Canonical Polyadic Decomposition [11.325830583924803]
  We propose a novel algorithm for the computation of canonical polyadic decomposition (CPD) of large-scale tensors. The proposed algorithm generalizes the random projection (RAP) technique, which is often used to compute large-scale decompositions.
  arXiv  Detail & Related papers  (2021-05-10T03:00:50Z)
• Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions [1.8356693937139124]
  Low-rank Tucker and CP tensor decompositions are powerful tools in data analytics. We propose a fast and accurate sketched ALS algorithm for Tucker decomposition. It is further used to accelerate CP decomposition, by using randomized Tucker compression followed by CP decomposition of the Tucker core tensor.
  arXiv  Detail & Related papers  (2021-04-02T15:55:02Z)
• Kronecker CP Decomposition with Fast Multiplication for Compressing RNNs [11.01184134911405]
  Recurrent neural networks (RNNs) are powerful in the tasks oriented to sequential data, such as natural language processing and video recognition. In this paper, we consider compressing RNNs based on a novel Kronecker CANDECOMP/PARAFAC (KCP) decomposition.
  arXiv  Detail & Related papers  (2020-08-21T07:29:45Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.