Robust Completion for Rank- 1 1 Tensors with Noises
Jiawang Nie, Xindong Tang, Jinling Zhou · 2025
Read Robust Completion for Rank- 1 1 Tensors with Noises by Jiawang Nie, Xindong Tang, Jinling Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-00398.txt.
Introduction
Jiawang Nie, Xindong Tang, and Jinling Zhou study how to fill in a partly seen data cube when the readings carry noise. The cubes, called tensors, should follow the simplest pattern, rank one, in their test case. Missing entries must be guessed from the rest. Noise makes naive filling brittle.
The authors build a robust optimization model shaped to resist that noise. When the observed cube sits close to rank one, they prove the model recovers an accurate completion. Solving the model directly is hard, so they relax it into a convex form that standard software can handle. If a key matrix splits cleanly, the exact answer drops out. Otherwise a spectral step gives a close stand-in. Numerical tests probe how well the whole chain performs.
Catalog record
| CREATOR | Jiawang Nie, Xindong Tang, Jinling Zhou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-00398
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Robust Completion for Rank- 1 1 Tensors with Noises Jiawang Nie, Xindong Tang, Jinling Zhou Abstract . This paper studies the rank- 1 1 tensor completion problem for cubic tensors when there are noises for observed tensor entries. First, we propose a robust biquadratic optimization model for obtaining rank- 1 1 completing tensors. When the observed tensor is sufficiently close to be rank- 1 1 , we show that this biquadratic optimization produces an accurate rank- 1 1 tensor completion. Second, we give an efficient convex relaxation for solving the biquadratic optimization. When the optimizer matrix is separable, we show how to get optimizers for the biquadratic optimization and how to compute the rank- 1 1 completing tensor. When that matrix is not separable, we apply its spectral decomposition to obtain an approximate rank- 1 1 completing tensor. The software SDPNAL+ is applied to solve the resulting large size semidefinite programs. Numerical experiments are given to explore the efficiency of this biquadratic optimization model and the proposed convex relaxation. 2020 Mathematics Subject Classification 15A69, 90C23, 65F99 1. Introduction Let \mathbb{R} be the real field. A real tensor \mathcal{A}\in\mathbb{R}^{n_{1}\times\cdots\times n_{m}} of order m can be viewed as the multi-array indexed such that \mathcal{A}=(\mathcal{A}_{i_{1}\cdots i_{m}})_{\begin{subarray}{c}1\leq i_{1}\leq n_{1},\ldots,1\leq i_{m}\leq n_{m}.\end{subarray}} When m=3 , the \mathcal{A} is called a cubic tensor. We focus on cubic tensors in this paper. For vectors a,b,c , the notation a\otimes b\otimes c denotes the rank- 1 tensor such that (a\otimes b\otimes c)_{ijk}\,=\,a_{i}b_{j}c_{k} for all indices i,j,k in the range. For the tensor \mathcal{A} , its Candecomp-Parafac (CP) rank [ 21 ] is the smallest integer r such that \mathcal{A}=\mathcal{A}_{1}+\cdots+\mathcal{A}_{r}, where each \mathcal{A}_{i} is a rank- 1 tensor. The CP rank is sometimes just referenced as rank. There also exist other notions of tensor ranks. We refer to [ 8 , 13 , 17 , 21 , 22 , 31 ] for related work. For a partially given tensor, the tensor completion problem (TCP) concerns how to fill its missing entries so that the whole tensor has some attractive properties, e.g., its rank is low. The whole tensor with all its missing entries filled is called a tensor completion or completed tensor. There are wide applications for tensor completions, such as recommendation systems [ 15 , 25 ] , imaging and signal processing [ 29 , 30 , 51 ] . More applications can be found in [ 27 ] . TCPs are natural generalizations of matrix completions [ 7 , 9 ] . Solving TCPs is generally more challenging. Indeed, it is shown in [ 12 ] that for rank- 1 matrix completions, if the associated bipartite graph is connected, then the second order Moment-SOS relaxation is tight when the observed matrix is noise-free. However, there does not exist similar results for rank- 1 tensor completions, to the best of the authors’s knowledge. There are different methods for doing tensor completions, based on different tensor decompositions, such as CP-decompositions [ 4 , 38 , 51 ] , Tucker decomposition [ 3 , 39 ] , tensor singular value decomposition [ 26 , 50 ] , tensor tubal rank [ 23 , 33 ] and multi-rank [ 26 ] . There exist computational methods based on tensor nuclear norm relaxations [ 35 , 45 , 49 ] and Riemannian-manifold optimization [ 6 , 14 , 16 , 28 , 41 , 44 ] . Most tensor computation problems are NP-hard [ 20 ] . In the earlier work, most tensor completion methods assume the observed tensor entries are noise-free, i.e., the exact values of those entries are known. However, in applications, there almost always exist noises. It is rather desirable to predict tensor data from both noisy and incomplete observations. In contrast to the abundant literature of noise-free TCPs, there exist relatively less work for noisy TCPs. For noisy rank- 1 matrix completion, stable completions can be computed by the second order Moment-SOS relaxations [ 12 ] . Tensor decomposition and total variation regularization based models have been proposed to solve noisy TCPs [ 1 , 53 ] . Tensor tubal rank based methods for solving third-order noisy TCPs are introduced in [ 47 , 48 ] . Besides that, a semidefinite relaxation method based on the sum-of-squares hierarchy is given in [ 5 ] . Most tensor optimization problems can be formulated as polynomial optimization [ 36 ] . Nuclear norm relaxations can be used to get tensor completions [ 35 , 45 , 54 ] . Low rank symmetric tensor approximations can be obtained by solving equations about generating polynomials [ 34 ] . Rank- 1 tensor completion. A particularly interesting class of TCPs is the rank- 1 tensor completion, i.e., finding a rank- 1 tensor that matches all partially given entries. The rank- 1 TCP has very special properties. It is shown in [ 54 ] that this problem is equivalent to a special rank- 1 matrix recovery problem. The geometric properties of the rank- 1 tensor completion problem are well studied by Kahle et al. [ 24 ] . For a positive integer n , denote the index set [n]\coloneqq\{1,\ldots,n\} . A cubic tensor \mathcal{A}\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}} is said to be partially given if there exists a set \Omega\subseteq[n_{1}]\times[n_{2}]\times[n_{3}] such that the entry \mathcal{A}_{ijk} is given for each triple (i,j,k)\in\Omega , while it is not given for (i,j,k)\not\in\Omega . As shown in [ 54 ] , \mathcal{A}=a\otimes b\otimes c is a rank- 1 tensor completion if and only if the vectors a,b satisfy (1.1) \mathcal{A}_{i_{s}j_{s}k}a_{i_{t}}b_{j_{t}}-\mathcal{A}_{i_{t}j_{t}k}a_{i_{s}}b_{j_{s}}\,=\,0 for all (i_{s},\,j_{s},\,k),(i_{t},j_{t},k)\in\Omega . Based on this observation, a rank- 1 tensor completion can be obtained by solving the quadratic system of equations like ( 1.1 ). Nuclear norm and moment relaxation methods are given in [ 54 ] to solve ( 1.1 ). Under some general conditions, the moment method can find a rank- 1 tensor completion if there exists one, or it detects nonexistence of rank- 1 completions if it does not exist. Contributions. In the work [ 54 ] , the partially given tensor entries are supposed to have no noises. However, observation of tensor entries often has noises. In this paper, we consider the rank- 1 TCP such that the observed tensor entries \mathcal{A}_{ijk} for (i,j,k)\in\Omega have noises. That is, there is a rank- 1 tensor \widehat{\mathcal{A}}\coloneqq\hat{a}\otimes\hat{b}\otimes\hat{c} such that (1.2) \mathcal{A}=\widehat{\mathcal{A}}+\delta\mathcal{A}, where \delta\mathcal{A} is the noise tensor. Our purpose is to recover the rank- 1 tensor \hat{a}\otimes\hat{b}\otimes\hat{c} . Due to the existence of the noise \delta\mathcal{A} , which is unknown, the tensor \hat{a}\otimes\hat{b}\otimes\hat{c} cannot be uniquely determined. This is because for any small perturbation (\delta\hat{a},\delta\hat{b},\delta\hat{c}) , it holds \mathcal{A}=(\hat{a}+\delta\hat{a})\otimes(\hat{b}+\delta\hat{b})\otimes(\hat{c}+\delta\hat{c})+\delta\widehat{\mathcal{A}}, with \delta\widehat{\mathcal{A}} also small. For this reason, it is more practical for us to look for a rank- 1 tensor a^{*}\otimes b^{*}\otimes c^{*} such that (1.3) (\mathcal{A}-a^{*}\otimes b^{*}\otimes c^{*})_{ijk}\quad\mbox{is small for}\quad(i,j,k)\in\Omega. Due to the noise, the vectors a^{*},b^{*},c^{*} for ( 1.3 ) typically do not satisfy equations in ( 1.1 ). This is because \mathcal{A} itself typically does not have an exact rank- 1 completion. Thus, the methods in [ 54 ] are not applicable for finding a rank- 1 tensor completion required for ( 1.3 ). Alternatively, one may consider to solve the nonlinear least squares