# Interpolating Convex and Non-Convex Tensor Decompositions via the Subspace Norm

arXiv: https://arxiv.org/abs/1503.05479 · HTML: https://mlsanity.com/paper/1503.05479/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2015.

## Built on by (most cited first, 1 of 1)

- [Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Lifting](https://mlsanity.com/paper/2602.05887/) (2026)

## Abstract (arXiv)

We consider the problem of recovering a low-rank tensor from its noisy observation. Previous work has shown a recovery guarantee with signal to noise ratio O(nlceil K/2 rceil /2) for recovering a Kth order rank one tensor of size n× cdots × n by recursive unfolding. In this paper, we first improve this bound to O(nK/4) by a much simpler approach, but with a more careful analysis. Then we propose a new norm called the subspace norm, which is based on the Kronecker products of factors obtained by the proposed simple estimator. The imposed Kronecker structure allows us to show a nearly ideal O(√n+√HK-1) bound, in which the parameter H controls the blend from the non-convex estimator to mode-wise nuclear norm minimization. Furthermore, we empirically demonstrate that the subspace norm achieves the nearly ideal denoising performance even with H=O(1).