A Novel Tensor Factorization-Based Method with Robustness to Inaccurate Rank Estimation
This work solves computational efficiency and robustness issues in tensor completion for applications like data analysis, but it is incremental as it builds on existing tensor factorization methods.
The paper tackles the problem of tensor completion by addressing over-reliance on accurate rank estimation and high computational costs, proposing a new tensor norm with dual low-rank constraints that reduces computational complexity from O(n^4) to O(n^3 log n + kn^3) and shows superior performance on synthetic and real-world data.
This study aims to solve the over-reliance on the rank estimation strategy in the standard tensor factorization-based tensor recovery and the problem of a large computational cost in the standard t-SVD-based tensor recovery. To this end, we proposes a new tensor norm with a dual low-rank constraint, which utilizes the low-rank prior and rank information at the same time. In the proposed tensor norm, a series of surrogate functions of the tensor tubal rank can be used to achieve better performance in harness low-rankness within tensor data. It is proven theoretically that the resulting tensor completion model can effectively avoid performance degradation caused by inaccurate rank estimation. Meanwhile, attributed to the proposed dual low-rank constraint, the t-SVD of a smaller tensor instead of the original big one is computed by using a sample trick. Based on this, the total cost at each iteration of the optimization algorithm is reduced to $\mathcal{O}(n^3\log n +kn^3)$ from $\mathcal{O}(n^4)$ achieved with standard methods, where $k$ is the estimation of the true tensor rank and far less than $n$. Our method was evaluated on synthetic and real-world data, and it demonstrated superior performance and efficiency over several existing state-of-the-art tensor completion methods.