Finding the smallest or largest element of a tensor from its low-rank factors

Nicholas D. Sidiropoulos, Paris A. Karakasis, Aritra KonararXiv 2022 · DOI · OpenReview

TL;DR

This paper tackles the fundamental problem of finding the minimum or maximum element within a low-rank tensor, proving it's NP-hard for ranks greater than one. They introduce a novel continuous relaxation that's mathematically tight, enabling efficient gradient-based optimization for practical applications like decoding error-correcting codes and signal processing.

What Problem Does This Paper Address?

Imagine you have a massive dataset represented as a high-order tensor (think of it as a multi-dimensional array). This tensor is "low-rank," meaning it can be efficiently described by a few underlying factors. The problem is to find the absolute smallest or largest value within this tensor, or more precisely, to find the specific combination of elements from its factors that yields this extreme value. This is crucial in fields like recommender systems (finding the best user-item match), knowledge discovery (identifying optimal relationships between entities), and modeling complex probability distributions. While the matrix case (2D tensor) has been studied, the high-order tensor version, especially for practical low-rank representations, remained computationally challenging and less understood.

Methods

The core of the paper lies in two main contributions:

  1. NP-Hardness Proof: The authors rigorously prove that finding the minimum or maximum element of a low-rank tensor (specifically, a Canonical Polyadic Decomposition or CPD) is NP-hard for any rank greater than one. This is a significant theoretical result, establishing the inherent difficulty of the problem. They achieve this by cleverly transforming the well-known partition problem into their tensor problem.
  2. Continuous Relaxation and Optimization: To overcome the NP-hardness, they propose a novel continuous relaxation of the discrete problem. This means they transform the problem into one involving continuous variables (probabilities) instead of discrete choices. Crucially, they prove this relaxation is "tight," meaning the optimal solution to the relaxed problem directly corresponds to the optimal solution of the original discrete problem. This continuous formulation then allows them to employ efficient gradient-based optimization techniques, such as projected gradient descent and Frank-Wolfe. They also explore various parametrizations to handle the simplex constraints inherent in probability distributions.

The paper also emphasizes that these results hold for various popular tensor decomposition models, including Tucker, HOSVD/MLSVD, tensor train (TT), and tensor ring (TR), not just CPD.

Datasets

The paper does not introduce new datasets. Instead, it uses established problem formulations and benchmarks for evaluation:

  • Partition Problem: Used for theoretical hardness proofs.
  • Sign Retrieval: Evaluated using randomly generated problem instances with varying parameters (N, M, and noise standard deviation σ).
  • Parity Check Codes: Evaluated on five different scenarios of parity check codes with varying densities and lengths (N=32 and N=96), using both custom LDPC codes and randomly generated matrices.

Key Insights and Ideas

  • Fundamental Hardness: The NP-hardness result for ranks > 1 is surprising, as it implies that even simple low-rank tensor structures can encode computationally intractable problems.
  • The Power of Continuous Relaxation: The tight continuous relaxation is a game-changer. It bridges the gap between intractable discrete problems and efficient continuous optimization, opening up practical solutions.
  • Universality of the Approach: The fact that the core results and optimization framework apply to multiple tensor decomposition models (CPD, Tucker, TT, TR) makes the work broadly applicable.
  • Broad Applicability: The paper demonstrates that a wide array of important NP-hard problems (integer programming, least squares, sign retrieval, error-correcting code decoding) can be elegantly framed as instances of this tensor minimization problem.
  • "Blind" Optimization Potential: The work hints at the possibility of solving problems where the cost function is not fully known, but only samples are available, by leveraging tensor completion principles.

Key Results

  • NP-Hardness: The problem of finding the smallest/largest element of a tensor is proven NP-hard for ranks R > 1. For R=1, it's polynomial-time solvable.
  • Optimization Performance: The proposed gradient-based optimization algorithms (especially Frank-Wolfe) demonstrate state-of-the-art performance in several applications:
  • Partition Problem: Outperforms greedy algorithms, often achieving optimal or near-optimal solutions.
  • Sign Retrieval: Achieves performance comparable to enumeration-based methods, with competitive squared error.
  • Parity Check Codes: Achieves better or comparable Bit Error Rate (BER) performance than Belief Propagation (BP) for various code types and channel conditions, notably without needing channel-specific parameters.

Limitations and Future Work

  • Initialization Dependence: While the algorithms are generally effective, performance can be sensitive to initialization, especially for problems without natural starting points (like sign retrieval). The authors suggest using DP-based algorithms or random initializations.
  • Convergence Guarantees: For some algorithms and parametrizations, convergence to the global optimum is not guaranteed due to the non-convex nature of the cost function. The authors mention setting iteration limits.
  • Scalability for Very High Ranks: While the algorithms are efficient for low ranks, the complexity can still grow with R. For problems where R is large (e.g., exponential in N), low-rank approximation techniques would be necessary.
  • Future Work: The authors plan to improve scalability and speed, establish stronger convergence guarantees, and explore applications in more diverse settings, including top-k/bottom-k recommendation and other machine learning tasks. They are also interested in further exploring the "blind" optimization aspects.

Summary updated

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. We show that this fundamental tensor problem is NP-hard for any tensor rank higher than one, and polynomial-time solvable in the rank-one case. We also propose a continuous relaxation and prove that it is tight for any rank. For low-enough ranks, the proposed continuous reformulation is amenable to low-complexity gradient-based optimization, and we propose a suite of gradient-based optimization algorithms drawing from projected gradient descent, Frank-Wolfe, or explicit parametrization of the relaxed constraints. We also show that our core results remain valid no matter what kind of polyadic tensor model is used to represent the tensor of interest, including Tucker, HOSVD/MLSVD, tensor train, or tensor ring. Next, we consider the class of problems that can be posed as special instances of the problem of interest. We show that this class includes the partition problem (and thus all NP-complete problems via polynomial-time transformation), integer least squares, integer linear programming, integer quadratic programming, sign retrieval (a special kind of mixed integer programming / restricted version of phase retrieval), and maximum likelihood decoding of parity check codes. We demonstrate promising experimental results on a number of hard problems, including state-of-art performance in decoding low density parity check codes and general parity check codes.
BibTeX
@misc{sidiropoulos2022finding,
  author = {Nicholas D. Sidiropoulos and Paris A. Karakasis and Aritra Konar},
  title = {{Finding the smallest or largest element of a tensor from its low-rank factors}},
  year = {2022},
  eprint = {2210.11413},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.11413},
}
Figure