Tight Lower Bound on the Tensor Rank based on the Maximally Square Unfolding

2019/09/12 by Calvi, Giuseppe G., Dees, Bruno Scalzo, Mandic, Danilo P.
#FOS: Electrical engineering #Signal Processing (eess.SP) #electronic engineering #information engineering

paper · doi:10.48550/arxiv.1909.05831

Abstract

Tensors decompositions are a class of tools for analysing datasets of high dimensionality and variety in a natural manner, with the Canonical Polyadic Decomposition (CPD) being a main pillar. While the notion of CPD is closely intertwined with that of the tensor rank, R, unlike the matrix rank, the computation of the tensor rank is an NP-hard problem, owing to the associated computational burden of evaluating the CPD. To address this issue, we investigate tight lower bounds on R with the aim to provide a reduced search space, and hence to lessen the computational costs of the CPD evaluation. This is achieved by establishing a link between the maximum attainable lower bound on R and the dimensions of the matrix unfolding of the tensor with aspect ratio closest to unity (maximally square). Moreover, we demonstrate that, for a generic tensor, such lower bound can be attained under very mild conditions, whereby the tensor rank becomes detectable. Numerical examples demonstrate the benefits of this result.

Related

• A Generating Polynomial Based Two-Stage Optimization Method for Tensor Rank Decomposition
• New results in canonical polyadic decomposition over finite fields
• Tensor Networks for Latent Variable Analysis: Higher Order Canonical\n Polyadic Decomposition
• Guarantees for existence of a best canonical polyadic approximation of a noisy low-rank tensor
• Practical Leverage-Based Sampling for Low-Rank Tensor Decomposition