Rank One Completion for Higher Order Tensors

Linghao Zhang, Ioana Dumitriu, Jiawang Nie · 2026

Read Rank One Completion for Higher Order Tensors by Linghao Zhang, Ioana Dumitriu, Jiawang Nie (2026) 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-2604-23104.txt.

Introduction

Zhang, Dumitriu, and Nie study how to fill in a tensor from partial entries when the full tensor has rank one, a problem spanning tensors of any order. They define rank one determinable tensors, explore their traits, and give a recursive method needing only linear solves and singular vectors. Without noise, the method returns a unique rank one completion under stated assumptions; with small noise, its output stays close to the exact completion. Numerical tests back the method's efficiency and accuracy.

Catalog record

CREATORLinghao Zhang, Ioana Dumitriu, Jiawang Nie
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80843
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.23104

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Rank One Completion for Higher Order Tensors Linghao Zhang, Ioana Dumitriu, Jiawang Nie Abstract . We study the rank one completion problem for tensors of arbitrary orders. The notion of rank one determinable tensors is introduced. We explore its properties and propose a recursive algorithm for computing rank one tensor completion. This algorithm only requires solving linear systems and computing singular vectors. In the absence of noise, it produces a unique rank one completion under some assumptions. In the presence of noise, we show that the computed rank one tensor completion is close to the exact one when the noise is sufficiently small. Numerical experiments demonstrate the efficiency and accuracy of the proposed method. 2020 Mathematics Subject Classification 15A69, 90C23, 65F99 1. Introduction A tensor \mathcal{A} of order m (a positive integer) and dimension (n_{1},\ldots,n_{m}) can be viewed as the multidimensional array such that \mathcal{A}\,=\,(\mathcal{A}_{i_{1}\cdots i_{m}})_{1\leq i_{1}\leq n_{1},\ldots,1\leq i_{m}\leq n_{m}}. We denote by \mathbb{R}^{n_{1}\times\cdots\times n_{m}} the space of real tensors as above. A rank one tensor is of the form u_{1}\otimes\cdots\otimes u_{m} for vectors u_{1}\in\mathbb{R}^{n_{1}},\ldots,u_{m}\in\mathbb{R}^{n_{m}} such that (u_{1}\otimes\cdots\otimes u_{m})_{i_{1}\cdots i_{m}}\,=\,(u_{1})_{i_{1}}\cdots(u_{m})_{i_{m}}. The rank of \mathcal{A} is the smallest number of rank one tensors whose sum equals \mathcal{A} . This is referred to as the Candecomp-Parafac (CP) decomposition in the literature [ 12 , 13 , 21 ] . There are various notions of tensor ranks (e.g., border rank, multilinear rank), and tensor ranks depend on the ground field. Moreover, determining tensor ranks is NP-hard [ 11 ] . We refer to [ 6 , 10 , 12 , 13 , 21 , 25 , 26 ] for related work on tensor decompositions and tensor ranks. The tensor completion problem (TCP) is to fill in missing entries of a partially observed tensor such that the completed tensor has some properties (e.g., it has a low rank). TCPs appear in a broad range of applications, including recommendation systems [ 9 , 16 ] , computer vision [ 29 , 30 ] , imaging and signal processing [ 22 , 23 , 39 ] ; see also [ 19 ] for more applications. In contrast to matrix completion problems, TCP is substantially more challenging. There exists a variety of methods for low rank tensor completions, including sum-of-squares relaxations [ 3 ] , tensor nuclear norm relaxations [ 24 , 27 , 34 , 35 , 37 ] , approaches based on CP and Tucker decompositions [ 1 , 2 , 30 , 39 ] , Riemannian-manifold optimization [ 8 , 20 , 32 , 33 ] , and methods based on tubal rank and t-SVD [ 14 , 17 , 36 , 38 ] . This paper focuses on the special but fundamental case of rank one tensor completion. Solving this problem sheds light on more general low rank completion problems, as rank one tensors exhibit rich algebraic and geometric problems. We consider an m th order partially observed tensor (p.o.t.) \mathcal{A} with the observation label set \Omega\subseteq[n_{1}]\times\cdots\times[n_{m}]\quad\text{where}\quad[n_{k}]\coloneqq\{1,\ldots,n_{k}\}, such that \mathcal{A}_{i_{1}\cdots i_{m}} is observed (given) for all (i_{1},\ldots,i_{m})\in\Omega . For convenience, we denote this p.o.t. by (\mathcal{A},\Omega) . The rank one tensor completion problem is to look for vectors u_{1},\ldots,u_{m} such that (1.1) \mathcal{A}_{i_{1}\cdots i_{m}}\,=\,(u_{1})_{i_{1}}\cdots(u_{m})_{i_{m}}\quad\text{for all}\quad(i_{1},\ldots,i_{m})\in\Omega. If such u_{1},\ldots,u_{m} exist, (\mathcal{A},\Omega) is said to be rank one completable , and u_{1}\otimes\cdots\otimes u_{m} is called a rank one completion for (\mathcal{A},\Omega) . Moreover, (\mathcal{A},\Omega) is said to have a unique rank one completion if for any two rank one completions u_{1}\otimes\cdots\otimes u_{m} and v_{1}\otimes\cdots\otimes v_{m} of (\mathcal{A},\Omega) , there exist nonzero scalars \alpha_{k} such that u_{k}=\alpha_{k}v_{k} for k=1,\ldots,m . The rank one tensor completion problem has been studied from several perspectives in the literature. Kahle et al. [ 15 ] investigate its algebraic and geometric properties. Some computational methods are proposed in [ 4 , 28 , 31 , 40 ] . The work [ 31 ] studies uniqueness for rank one tensor completion, and [ 4 ] gives a semidefinite programming (SDP) approach. The work [ 40 ] is motivated by the following observation for cubic order tensors: the rank one tensor a\otimes b\otimes c is a completion for (\mathcal{A},\Omega) if and only if the vectors a and b satisfy (1.2) \det\begin{bmatrix}\mathcal{A}_{ijk}&a_{i}b_{j}\\ \mathcal{A}_{i^{\prime}j^{\prime}k}&a_{i^{\prime}}b_{j^{\prime}}\\ \end{bmatrix}=0 for all (i,j,k),(i^{\prime},j^{\prime},k)\in\Omega . Equivalently, if we let X=ab^{T} , then (1.3) \mathcal{A}_{ijk}X_{i^{\prime}j^{\prime}}-\mathcal{A}_{i^{\prime}j^{\prime}k}X_{ij}=0\quad\text{for all}\quad(i,j,k),(i^{\prime},j^{\prime},k)\in\Omega. This gives a system of linear equations in X_{\bar{\Omega}}\coloneqq(X_{ij})_{(i,j)\in\bar{\Omega}}, where \bar{\Omega} denotes the projection of \Omega onto the first two indices. When the solution space of ( 1.3 ) is one-dimensional, the partial matrix X_{\bar{\Omega}} can be determined uniquely up to scaling. If (\mathcal{A},\Omega) is rank one completable, then X_{\bar{\Omega}} can be completed to a full matrix X of rank one. Then, we can obtain vectors a,b (up to scaling) from X , and thereby c from \mathcal{A}=a\otimes b\otimes c on \Omega . For such a case, (\mathcal{A},\Omega) is said to be strongly rank one completable in [ 40 ] . However, this approach is specific to cubic order tensors and does not extend naturally to the higher order case. Moreover, it is not applicable in the presence of noise. The follow-up work [ 28 ] considers noisy rank one completion for cubic order tensors. It formulates the problem as biquadratic optimization with sphere constraints and solves it by an SDP relaxation. This approach can be effective in practice, but the biquadratic optimization may not always be solved globally by that relaxation. Contributions In this paper, we propose an efficient approach for completing rank one tensors of arbitrary orders. Let (\mathcal{A},\Omega) be a p.o.t. of order m . Suppose it admits a rank one completion \mathcal{A}=u_{1}\otimes\cdots\otimes u_{m}. The tensor \mathcal{A} can be flattened into a matrix in various ways. For convenience of description, we flatten \mathcal{A} along the first m-1 indices, so it becomes a rank one matrix A=ab^{T}, where a is the vectorization of the tensor product u_{1}\otimes\cdots\otimes u_{m-1} and b=u_{m} . In this way, the p.o.t. (\mathcal{A},\Omega) induces a partially observed matrix (A,\Omega) . As shown in Section 2 , the vector a must satisfy a homogeneous linear system (1.4) Bx\,=\,0, where B depends on (\mathcal{A},\Omega) but not on b . Assume the solution space of ( 1.4 ) is one-dimensional, then a can be determined uniquely up to scaling. When the observed tensor entries are exact, we can recover a from a nontrivial solution x^{*} to ( 1.4 ). When these entries have noise, ( 1.4 ) may not have a nontrivial solution, but we can instead select x^{*} as the right singular vector corresponding to the smallest singular value of B . Once x^{*} is computed, the vector b can be recovered from the linear equation A_{ij}=x^{*}_{i}b_{j} on \Omega ; that is, u_{m} is obtained. Next, we reshape x^{*} to a p.o.t. of order m-1 , say, (\mathcal{A}_{1},\Omega_{1}) . We apply the above procedure to (\mathcal{A}_{1},\Omega_{1}) , and this yields the vector u_{m-1} . Repeating this process recursively, we obtain vectors u_{m-2},\ldots,u_{1} , which give a rank one completion. Our new method has several advantages. First, it applies to tensors of arbitrary orders. Second, it remains robust in the presence of noise. Third, our method only requires solving linear systems and computing singular vectors, hence it is very efficient for large-scale problems.

Read the complete text