FRAPPE: $\underline{\text{F}}$ast $\underline{\text{Ra}}$nk $\underline{\text{App}}$roximation with $\underline{\text{E}}$xplainable Features for Tensors

• URL: http://arxiv.org/abs/2206.09316v2
• Date: Sat, 25 May 2024 07:05:54 GMT
• Title: FRAPPE: $\underline{\text{F}}$ast $\underline{\text{Ra}}$nk $\underline{\text{App}}$roximation with $\underline{\text{E}}$xplainable Features for Tensors
• Authors: William Shiao, Evangelos E. Papalexakis,
• Abstract summary: FRAPPE is the first method to estimate the canonical rank of a tensor without having to compute the CPD. It is over 24 times faster than the best-performing baseline and exhibits a 10% improvement in MAPE on a synthetic dataset.
• Score: 5.39764619690516
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Tensor decompositions have proven to be effective in analyzing the structure of multidimensional data. However, most of these methods require a key parameter: the number of desired components. In the case of the CANDECOMP/PARAFAC decomposition (CPD), the ideal value for the number of components is known as the canonical rank and greatly affects the quality of the decomposition results. Existing methods use heuristics or Bayesian methods to estimate this value by repeatedly calculating the CPD, making them extremely computationally expensive. In this work, we propose FRAPPE, the first method to estimate the canonical rank of a tensor without having to compute the CPD. This method is the result of two key ideas. First, it is much cheaper to generate synthetic data with known rank compared to computing the CPD. Second, we can greatly improve the generalization ability and speed of our model by generating synthetic data that matches a given input tensor in terms of size and sparsity. We can then train a specialized single-use regression model on a synthetic set of tensors engineered to match a given input tensor and use that to estimate the canonical rank of the tensor - all without computing the expensive CPD. FRAPPE is over 24 times faster than the best-performing baseline and exhibits a 10% improvement in MAPE on a synthetic dataset. It also performs as well as or better than the baselines on real-world datasets.

Related papers

• Multi-Dictionary Tensor Decomposition [5.733331864416094]
  We propose a framework for Multi-Dictionary Decomposition (MDTD) We derive a general optimization algorithm for MDTD that handles both complete input and input with missing values. It can impute missing values in billion-entry tensors more accurately and scalably than state-of-the-art competitors.
  arXiv  Detail & Related papers  (2023-09-18T12:31:56Z)
• From Fake to Real: Pretraining on Balanced Synthetic Images to Prevent Spurious Correlations in Image Recognition [64.59093444558549]
  We propose a simple, easy-to-implement, two-step training pipeline that we call From Fake to Real. By training on real and synthetic data separately, FFR does not expose the model to the statistical differences between real and synthetic data. Our experiments show that FFR improves worst group accuracy over the state-of-the-art by up to 20% over three datasets.
  arXiv  Detail & Related papers  (2023-08-08T19:52:28Z)
• A Novel Tensor Factorization-Based Method with Robustness to Inaccurate Rank Estimation [9.058215418134209]
  We propose a new tensor norm with a dual low-rank constraint, which utilizes the low-rank prior and rank information at the same time. It is proven theoretically that the resulting tensor completion model can effectively avoid performance degradation caused by inaccurate rank estimation. Based on this, the total cost at each iteration of the optimization algorithm is reduced to $mathcalO(n3log n +kn3)$ from $mathcalO(n4)$ achieved with standard methods.
  arXiv  Detail & Related papers  (2023-05-19T06:26:18Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Modeling Label Correlations for Second-Order Semantic Dependency Parsing with Mean-Field Inference [34.75002236767817]
  Second-order semantic parsing with end-to-end mean-field inference has been shown good performance. In this work we aim to improve this method by modeling label correlations between adjacent arcs. To tackle this computational challenge, we leverage tensor decomposition techniques.
  arXiv  Detail & Related papers  (2022-04-07T17:40:08Z)
• Computationally Efficient Approximations for Matrix-based Renyi's Entropy [33.72108955447222]
  Recently developed matrix based Renyi's entropy enables measurement of information in data. computation of such quantity involves the trace operator on a PSD matrix $G$ to power $alpha$(i.e., $tr(Galpha)$. We present computationally efficient approximations to this new entropy functional that can reduce its complexity to even significantly less than $O(n2)$.
  arXiv  Detail & Related papers  (2021-12-27T14:59:52Z)
• Augmented Tensor Decomposition with Stochastic Optimization [46.16865811396394]
  Real-world tensor data are usually high-ordered and have large dimensions with millions or billions of entries. It is expensive to decompose the whole tensor with traditional algorithms. This paper proposes augmented tensor decomposition, which effectively incorporates data augmentations to boost downstream classification.
  arXiv  Detail & Related papers  (2021-06-15T06:29:05Z)
• Beyond Lazy Training for Over-parameterized Tensor Decomposition [69.4699995828506]
  We show that gradient descent on over-parametrized objective could go beyond the lazy training regime and utilize certain low-rank structure in the data. Our results show that gradient descent on over-parametrized objective could go beyond the lazy training regime and utilize certain low-rank structure in the data.
  arXiv  Detail & Related papers  (2020-10-22T00:32:12Z)
• Spectral Learning on Matrices and Tensors [74.88243719463053]
  We show that tensor decomposition can pick up latent effects that are missed by matrix methods. We also outline computational techniques to design efficient tensor decomposition methods.
  arXiv  Detail & Related papers  (2020-04-16T22:53:00Z)

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.