Tensor Random Projection for Low Memory Dimension Reduction

• URL: http://arxiv.org/abs/2105.00105v1
• Date: Fri, 30 Apr 2021 22:08:04 GMT
• Title: Tensor Random Projection for Low Memory Dimension Reduction
• Authors: Yiming Sun and Yang Guo and Joel A. Tropp and Madeleine Udell
• Abstract summary: Random projections reduce the dimension of a set of vectors while preserving structural information. This paper proposes a novel use of row-product random matrices in random projection. It requires substantially less memory than existing dimension reduction maps.
• Score: 22.715952036307648
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random projections reduce the dimension of a set of vectors while preserving structural information, such as distances between vectors in the set. This paper proposes a novel use of row-product random matrices in random projection, where we call it Tensor Random Projection (TRP). It requires substantially less memory than existing dimension reduction maps. The TRP map is formed as the Khatri-Rao product of several smaller random projections, and is compatible with any base random projection including sparse maps, which enable dimension reduction with very low query cost and no floating point operations. We also develop a reduced variance extension. We provide a theoretical analysis of the bias and variance of the TRP, and a non-asymptotic error analysis for a TRP composed of two smaller maps. Experiments on both synthetic and MNIST data show that our method performs as well as conventional methods with substantially less storage.

Related papers

• Distributed Least Squares in Small Space via Sketching and Bias Reduction [0.0]
  Matrix sketching is a powerful tool for reducing the size of large data matrices. We show that these limitations can be circumvented in the distributed setting by designing sketching methods that minimize the bias of the estimator, rather than its error. In particular, we give a sparse sketching method running in optimal space and current matrix multiplication time, which recovers a nearly-unbiased least squares estimator using two passes over the data.
  arXiv  Detail & Related papers  (2024-05-08T18:16:37Z)
• Optimal Projections for Discriminative Dictionary Learning using the JL-lemma [0.5461938536945723]
  Dimensionality reduction-based dictionary learning methods have often used iterative random projections. This paper proposes a constructive approach to derandomize the projection matrix using the Johnson-Lindenstrauss lemma.
  arXiv  Detail & Related papers  (2023-08-27T02:59:59Z)
• Optimal Discriminant Analysis in High-Dimensional Latent Factor Models [1.4213973379473654]
  In high-dimensional classification problems, a commonly used approach is to first project the high-dimensional features into a lower dimensional space. We formulate a latent-variable model with a hidden low-dimensional structure to justify this two-step procedure. We propose a computationally efficient classifier that takes certain principal components (PCs) of the observed features as projections.
  arXiv  Detail & Related papers  (2022-10-23T21:45:53Z)
• Orthogonal Matrix Retrieval with Spatial Consensus for 3D Unknown-View Tomography [58.60249163402822]
  Unknown-view tomography (UVT) reconstructs a 3D density map from its 2D projections at unknown, random orientations. The proposed OMR is more robust and performs significantly better than the previous state-of-the-art OMR approach.
  arXiv  Detail & Related papers  (2022-07-06T21:40:59Z)
• Memory-Efficient Backpropagation through Large Linear Layers [107.20037639738433]
  In modern neural networks like Transformers, linear layers require significant memory to store activations during backward pass. This study proposes a memory reduction approach to perform backpropagation through linear layers.
  arXiv  Detail & Related papers  (2022-01-31T13:02:41Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• 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)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• Tensorized Random Projections [8.279639493543401]
  We propose two tensorized random projection maps relying on the tensor train(TT) and CP decomposition format, respectively. The two maps offer very low memory requirements and can be applied efficiently when the inputs are low rank tensors given in the CP or TT format. Our results reveal that the TT format is substantially superior to CP in terms of the size of the random projection needed to achieve the same distortion ratio.
  arXiv  Detail & Related papers  (2020-03-11T03:56:44Z)
• Stable Sparse Subspace Embedding for Dimensionality Reduction [9.033485533901658]
  This paper builds a stable sparse subspace embedded matrix based on random sampling without replacement in statistics. It is proved that the S-SSE is stabler than the existing matrix, and it can maintain Euclidean distance between points well after dimension reduction.
  arXiv  Detail & Related papers  (2020-02-07T15:30:22Z)

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.