Finding the smallest or largest element of a tensor from its low-rank factors
Preprint
Abstract
We consider the problem of finding the smallest or largest entry of a tensor of order $N$ that is specified via its rank decomposition. Stated in a different way, we are given $N$ sets of $R$-dimensional vectors and we wish to select one vector from each set such that the sum of the Hadamard product of the selected vectors is minimized or maximized. This is a fundamental tensor problem with numerous applications in embedding similarity search, recommender systems, graph mining, multivariate probability, and statistics. We show that this discrete optimization problem is NP-hard for any tensor rank higher than one, but also provide an equivalent continuous problem reformulation which is amenable to disciplined non-convex optimization. We propose a suite of gradient-based approximation algorithms whose performance in preliminary experiments appears to be promising.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- From the simplex to the sphere: faster constrained optimization using the Hadamard parametrizationInformation and Inference: A Journal of the IMA, 2023
- Tensors, Learning, and “Kolmogorov Extension” for Finite-Alphabet Random VectorsIEEE Transactions on Signal Processing, 2018
- Optimal Multi-Way Number PartitioningJournal of the ACM, 2018
- Tensor Decomposition for Signal Processing and Machine LearningIEEE Transactions on Signal Processing, 2017
- Estimating the Largest Elements of a MatrixSIAM Journal on Scientific Computing, 2016
- Diamond Sampling for Approximate Maximum All-Pairs Dot-Product (MAD) Search2015
- Most Tensor Problems Are NP-HardJournal of the ACM, 2013
- Tensor-Train DecompositionSIAM Journal on Scientific Computing, 2011
- A Multilinear Singular Value DecompositionSIAM Journal on Matrix Analysis and Applications, 2000
- Some Mathematical Notes on Three-Mode Factor AnalysisPsychometrika, 1966