Learning Unbalanced and Sparse Low-Order Tensors

Efficient techniques are developed for completing unbalanced and sparse low-order tensors, which cannot be effectively completed by popular matrix-rank optimization based techniques such as compressed sensing and/or the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell _{q}$</tex-math></inline-formula> -matrix-metric. We use our previously developed 2D-index encoding technique for tensor augmentation in order to represent these incomplete low-order tensors by high-order but low-dimensional tensors with their modes building up a coarse-grained hierachy of correlations among the incomplete tensor entries. The concept of tensor-trains is then exploited for decomposing these augmented tensors into trains of balanced and sparse matrices for efficient completion. More explicitly, we develop powerful algorithms exhibiting an excellent performance vs. complexity trade-off, which are supported by numerical examples by relying on matrix data and third-order tensor data derived from color image pixels.