Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan
Authors: Alejandro Gomez-Leos
Oscar Lopez
Venue: Accepted by TMLR ()

Abstract: We revisit the sample and computational complexity of the rank-1 tensor completion problem in $\otimes_{i=1}^{N} \mathbb{R}^{d}$, given a uniformly sampled subset of entries. We present a characterization of the problem which reduces to solving a pair of random linear systems. For example, when $N$ is a constant, we prove it requires no more than $m = O(d^2 \log d)$ samples and runtime $O(md^2)$. Moreover, we show that a broad class of algorithms require $\Omega(d\log d)$ samples, even under higher rank scenarios. In contrast, existing upper bounds on the sample complexity are at least as large as $d^{1.5} \mu^{\Omega(1)} \log^{\Omega(1)} d$, where $\mu$ can be $\Theta(d)$ in the worst case. Prior work obtained these looser guarantees in higher rank versions of our problem, and tend to involve more complicated algorithms.

Published in Transactions on Machine Learning Research (6/2025)
Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan
Alejandro Gomez-Leos
alergomeadesss@uueme.e.
Department of Electrical and Computer Engineering University of Teros Austin
Oscar López
lopezo Corezo&faa...o edu
Harbor Branch Oceanographic Institute Florida Atlantic University
Reviewed on OpenReview: openrvieew...... net/ pet//foum? id= ggāphfUU11
Abstract
We revisit. the sample and computational complexity of the rank-1 tensor completion prob- lem in R given a uniformly sampled subset of entries. We present a characterization of the problem which roduces solving a pair of random lincar systems. For example, when N a constant, we prove it requires no more than m O(d samples and runtime O(md)). Moreover, we show that broad class of algorithms require (dd d) samples, under higher-rank scenarios. In contrast, existing upper bounds on the sample com- plexity are at least as large as d' d log R(1) d, where can be ((d) in the worst case. Prior work obtained these looser guarantees in higher-rank versions of our problem, and tend to involve more complicated algorithms.
1 Introduction
Tensor completion is higher-order generalization of the well-known matrix completion problem (Candes & Tao 2010 Candes & Recht 2012). More precisely, N-fold, order d tensor U is multi-dimensional array whose entries U (()....éw) are specified by an ordered tuple of N indices, each in [d]:= := {l....,d} d}. We denote N Rd as the set of all such tensors. Stated loosely, the problem is to recover the entirety of tensor U
observing only a small subset of its entries.
U U is arbitrary, then this task is impossible without obscrving all dN entries of U. As in matrix completion, the siluation becomes interesting when has a low-runk structure. Conceptually, this means U's entries are described by an interaction of a small number of variables far fewer than dN In practice, the framework of tensor completion enjoys several applications in diverse areas such recommender systems (Nguyen & Uhlmann 2023), image and video processing (Wang al. 2025 and bioinformatics (Liu et al. 2022). We
refer to Kolda & Bader (2009); Song et. al. (2019) for an excellent overview of other applications.
In this work, we revisit the problem of rank-1 tensor completion. A tensor U E @N NN if there exists (u.....,uy C Rd such that
Rd is said to be rank-1
U (( = (ui),, (uz) ..... (un) (11, ix) E [d]
(1)
or U n uN, where denotes the vector outer product. Perhaps the most fundamental variant, we consider the setting in which the estimation algorithm only has access uniformly drawn entries and is required to be correct with bounded error probability. Specifically, study the following:

---

Published in Transactions on Machine Learning Research (6/2025)
Problem: Rank-1 Tensor Completion
Input: uniform samples (with replacement) from entries of rank-1 tensor U E @ Rd
Output:
Oracle access Ô where Ù w.p. (with probability) 2 2/3
Note that the choice of 2/3 is by convention rather than technicalities Given algorithm for the above consuming samples, one can use the standard method of amplification to obtain an algorithm using ((m log(s)) samples and succeeding with probability 2 1 - 6. Specifically, one would re-run the sampling procedure and algorithm on the same input and, for each entry, take majority across the outputs.
We are interested in the sample and time complexity of the above as dependent on and N. Our contributions include simple algorithm applicable to rank-1 tensors with nonzero entries and lower bounds against broad class of estimation algorithms.
Our main results are summarized as follows, assuming infinite precision arithmetic throughout. Suppose U is an arbitrary rank-1 tensor with nonzero entries, and N x 1 is a constant independent of d3
There exists an algorithm that solves Rank-1 Tensor Completion which draws m x de log samples and can be implemented in time $ md?
Moreover, m Z d'o d samples are informatiiontheoortiialll necessary for Rank-1 Tensor Com- pletion to be solvable.
The full results are detailed in Theorem
1.3 Theorem 1.5 and Corollary 1.6 The main technical novelty of our work is a reduction between Rank-1 Tensor Completion and a particular matrix sketch problem, detailed in Section ? In addition revealing an equivalence between the sample complexities of each problem, the algorithm therein serves as means of achieving novel analysis of the tensor completion problem.
A key challenge in our approach is that the matrix sketch must be performed over the field Fz-a problem which lacks a thorough study in the previous literature. Over IR, matrix sketching can be studied using tools from leverage score sampling (c.g. Cohen et al. (2015)). Unfortunately, these tools require the additive structure of IR, relying on matrix Chernoff bounds. We address this challenge by characteriving the sampling process random walk on a graph related to the matrix's rowspace. In this way, we relate the number of samples used by the algorithm to the walk's mixing time. This argument culminates in Lemma 2.2 which plays a key role in Theorem
For higher-rank tensor completion problems, it is well-known that the complexities above are impacted by the incoherence a of the input tensor class ppessape surprisingly, our bounds have no such dependence. This observation seems to have gone undescribed in the current literature. effect, this work serves to elucidate the sample complexity gap between the rank-1 and general rank problem variants. To properly contextualize these points, we review some basic definitions.
Definition 1.1 (c.g. Cai al. (2019); Singh et al. (020 The rank of a tensor U E R Rd is the minimum indeger such that U scalars {> C R.
de 41,6 @ uN holds for vectors {ui,k..... UN Rd and
Definition 1.2 (e.g, Liu & Moitra 20200; each of the following subspaces w-incoherent
Singh et (2020)). A rank-r tensor is called p-incoherent if
U2
UN k= 1,,,,,..,
span
(2)
|u
|
In the rank-1 case, u1 ... & un being j--incoherent simply mcans ||ull S vp/d Vi [d] (c.g.
Liu
& Moitral (2020): Singh et al. (2020)). )
1 Just as example, the well-known definitions of complexity classes BPP and R.. 2d So N in practice, with tensors of N > rarely seen in applications. Thus, focus dependence d.
2

---

Published in Transactions on Machine Learning Research (6/2025)
Prior Work The study of both rank-1 tensor completion and its sample complexity is novel pairing. Therefore, in this section we trace the literature separately from each angle.
On one hand, our problem is basic case of the well-studied exact tensor completion problem under uniform sampling. As such, we describe the prior bounds obtained for the rank-1 case. We note that some of these bounds are for the expected sample complexity under the Bernoulli model (Candes & Tao 2010). Rest assured, the comparison is not that imprecise due to standard Chernoff bounds for binomial random variables.
Popularly, the earliest guarantees for matrices (N = 2) were given in Candes & Tao 2010 Recht 201
Candes& & Recht
(2012). Notably, these exhibited a strong dependence of μ on the sample complexity, culmi-
nating in Chen 2015) establishing that & du log d samples sulfice for d1) failure probability lolerance.
For cubic tensors (N = 3), the works Jain & Oh (2014); Xia & Yuan 20119 Liu & Moitra (2020) indicate
a scaling increase to S d'.s log
0(1] d for comparative failure tolerance. The theory for N 2 4 has re-
ceived much less attention, with the first. results from Krishnamurthy & Singh (2013). although for adaptively chosen entries. These scaled as S d(o(N) (0(1) (0(1) log & for tolerance dó. Under varying structural assump- tions, the works Montanari Sun (2018): |Stephan & Zhu| (2024); (Haselyy et al. (2024) make significant advancements, but still with dependence on j ( Since j can be ((d) in the wonst case, this substantiates our assertion that our above results elucidate a complexity gap between Rank-1 Tensor Completion
and these more generic problems 3 We emphasize that these works do not focus rank-1 tensors, so it is reasonable to anticipate the improvements established in this work.
On the other hand, a distinct series of works Király et al. (2015); Kahle et al. [2017]: : Rendon Jaramillo
(2018); Singh et al. )2020); Zhou et al. (2024) have focused on the completabilily of a fixed, partially observed rank-1 1 tensor (i.e. the solution set for the polynomial system in equation D Perhaps as a testament to
the non-triviality of this problem, these works invoke advanced tools from algebraic geometry and matroid
theory (Király et al. 2015 Rendon Jaramillo 2018). We emphasize these do not study the sampling aspect of our problem.
The algorithms of these prior works tend to be quite intricate, alboit specialized for the harder problem of general rank tensor completion. A few popular methods are alternating minimization (Jain & Ohl 2014 Xia
& Yuaa 2019 Liu & Moitra 2020) and semidefinite programming / sum-of-squares hierarchies (Chen el al.
2015 Potechin & Steurer 2017 Zhou et al., 2024), amongst others. For more complete overview, we refer [019)] Liu & Moitra 20200 Haselby et al. (2024).
to Cai et al.
By contrast, in this work we describe a linear algebraic characterization, which was independently observed by Singh et al. (2020) and Stephan & Zhu (2024). However, the former did not leverage this to study the statistical hardness of our problem, and the latter's discussion was limited to symmetric Boolcan tensors. In this work we address both of these limitations, showing Rank-1 1 Tensor Completion admits an extremely simple algorithm, whose main bottleneck is solving a ((d) x Ô(d) system over F2. As consoquence, the toolbox for our analysis only consists of elementary linear algebraic and probabilistic arguments. Before detailing our results, we overview the notation to be used throughout this work.
Notation Throughout, F2 denotes the finite field of order 2. For a, E R, we write S if a S CB for some absolute constant C> 0, and = B if a S 8 and 8 a. We reserve bold \mathsfit for tensors (e.g. U), upper-case \mathbf for matrices (e.g. U), and lower-case \mathbf for vectors (e.g. u). All vectors are conventionally column vectors, unless otherwise stated. We denote e for k E [d] as the indicator row vector for [d], interpreting the ey 's having entries in F2 or E, wherever clear from context. For two row vectors x and y, we denote [x, as their concatenation. For a n1 X22 matrix A and the vector b with ni elements, we denote their induced linear system over a field KK by the augmented matrix [A] ]k, regardless of whether the system is consistent or not. For scalar-valued function f applied to tensor, matrix, or vector, we mean eitry-wise. For a matrix B, we denote B, as its ith row. We denote the rowspace of matrix B over field K by (B). The Frobenius norm of a tensor is given by || E(t.... U? ((....i))) We denote the set of all N-fold, order tensors with nonzero entries as N #0- For random variables X and
Twoo lower bounds are given in Candes Tao 2010): Singh et al. 2020 (Theorem 1.7 and Theorem 5, resp.). These seem to suggest multiplicative y (NNN) missing from our upper bound, but their hard instances do not apply.
3

---

Published in Transactions on Machine Learning Research (6/2025)
Y admitting joint distribution, H( X) denotes the conditional entropy of random variable Y given X. For two scalar-valued functions / and 9, f oog denotes their composition.
Our Results In this work, we show the following.
Theorem 1.3. If UUC oo R RR is rank-1 1 tensor, then there exists algorithm solving Rank-1 Tensor Completion using m I (dN)) logd uniformly drown entries, and can be implemented in time S qN + mdd, where q is the number of queried entries of U.
To prove it, in Section 2 we show every rank-1 tensor in R Rd in correspondence with a pair of linear systems- over F2, and the other over R. The former system "encodes information' about the signs of the tensor's entries, whereas the latter system does so for their magnitude. In a precisc sense, we show that the "information" revealed by sampling an entry corresponds to the "information" encoded by one row of the associated augmented matrix. These systems are overdetermined, so it suffices to obtain just a small subset of their rows. In essence, this characterization illuminates that the sample complexity can studied through a matrix row skotch problem over Fz. Unfortunately, the structure of these linear systems also imply that the resulting algorithm cannot. be trivially extended to higher-rank versions of our problem. heless this reduction is highly valuable in our problem setting.
We also present lower bound against a broad class of estimation algorithms, defined below, which matches the above result. up to a factor in d when N = 1. As a result, the proposed analysis only shows the above is nearly-optimal in d, although the analysis is indeed optimal if U is required to be unsigned we elaborate on this subtle point at the end Section 2 For the same reason, we believe this is an artifact of our particular upper bound technique, rather than the high-level approach. We leave its resolution as an open problem.
Definition 1.4 (randomized estimation algorithm). We say A is a randomized estimation algorithm for random tensor U, random observation subset S S [d]" and internal random bits B {0, 1) if its output is determined by the oulcome of all three, i.c. A(U, B) satisfies H(A(U, S, B) U, B) 0. Moreover, we say the estimator draws m samples if [S| m.
Theorem 1.5. Let o > 0. There erists a distribution D over rank-1 1 lensors in {U E 1 |||| S }} and absolute constants ny E N and C > 0 such that, for d. 2 nu, any randomized estimator Ô drawing less than Colog dN samples from U ~ D suffers error | U|l 2 av w.p. >1/3. Therefore, there is no algorithm to solue Rank-1 Tensor Completion when is below this threshold.
Lower bounds in the field are usually stated in different sense that if too few samples are taken, then there would likely exist distinct tensors agreeing on the observed entries. The standard conclusion is that any algorithm that solely bases its decision on the observed entries must fail (Candes Tao 2010 Krishnamurthy & Singh 2013). However, this conclusion might be unsalisfying since does not quantily the error, nor clarifies whether extra randomness is useful. This motivates the style of our bound.
Notably, Theorem 1.5 extends to higher-rank tensors, under benign "consistency" assumption. Due to its highly technical statement, expound Assumption 6.2 in Section 6 To summarize, it roughly asserts that the estimator's 's error is weakly incrcasing for perturbations to its input. In some sense, this class captures algorithms whose precision worsens with higher 'noise". For such algorithms, the following lower bound holds.
Corollary 1.6. Let a > 0. Let no and C be as in Theorem 1.5 and assume d.N 2 nn. If Hadamard matria of order d ezist then there exists distribution over tensors of rank 2 r in {U R ||U]| S of such that any randomized estimator 0 satisfying Assumption 6.2 and drawing less than Co dN samples suffers error ||ù U|F ovaN-1 w.p. 1133.
Concluding our main results, we delve into characterization of rank-1 tensors in & Rdd which forms the foundation of our algorithm and its analysis.
Recall such matrix d d, has entries (+1), ), and admits mutually orthogonal columns.
4

---

Published in Transactions on Machine Learning Research (6/2025)
2 Nonzero Rank-1 Tensors in Exponential Form
In this section, we describe characterization of rank-1 tensors in @ R which is at the core of Algo-
rithm Suppose that U E R satisfies equation define x E IR IRdN as
for some column vectors ui..... uN Rd Let
(u1)1
U1
(ui)a/
12
x
(3)
(ux))
uN
(ux)a/
Setting this aside, we focus on U, which we can re-write as follows for all (i1,...,áN) ldj.
U ((idammdd sign II N
(ue)ie)
II (ue)ie
III sign ((ue)ie)
N
exp Σ N
log ((ue)se)
U (in
exp
U
(4)
Noting that U V --1 iff an odd number of the variables (u1), ... (uN)i, are negative, we observe that the entry U (i..2.....N resembles the parity function on the sign of these variables. Hence, using an appropriate 1-1 transformation & between {+1} and {0.1} (e.g. sa()) == - - 1)), we obtain that the {u) solve the following linear systems over E2 and R:
(pp ((ig)(((uui)))) (pp sign) (U ((n
mod?
= (log o abs) (U (U(h)ii....))))
We now describe the coefficient matrix of these systems. Let æ : [d] + [dN] denote a fixed bijection throughout. Defining each row as A ((t....)))) == [ci, Cig...., Ciyl for all (i.,...,áN) E [d], we have
A A (9p (x) (yp o sign) (U ((nndamm))))) mod! 2
A Aath Ax) (log (x) (log abs) (U (b1)22m)d))))
Hence, there is unique 1-1 tensor-to-vecton map vec, such that the above is equivalent to
A (p o sxgn) = (p o sign) (vec, U)
mod 2
A (log o abs) = (log o abs) (vec, U).
To avoid overloading notation throughout, we let f == yp sign vec,, and f == log abs vec,, A(p sign) f(U) mod 2
A (log aabs) f(U).
Notably, A's rows enumcrate all d possible vectors of size dN obtained by concatenating N row vectors from (ex heed (each row corresponds to unique tensor entry). This observation enables a simple proof of result extensively that A has the same rank considered matrix over F2 or R.
Lemma 2.1. The matrix A salisfies ranks, (A) rank ( (A) dN (N 1).
5

---

Published in Transactions on Machine Learning Research (6/2025)
Proof. See Section
3
In summary of the previous observations, we have the following. Observation 1. For any tensor U E @ R
U is rank-1 linear systems Furthermore, if for a rank-1 tensor E 1
[A f(U) and [A] f(U) are both consistent.
(5)
R the joint solution sets of
(T) lx) and (IA f(U) l,,, [A (())
(6)
are equivalent, then U =
Indeed, equation f is the consequence of the following procedure. Supposing we had access to solution of Y1 of [A] f(U) B2. and a solution Y2 of A f(U) JR. then could recover the tensor from
= vec, (Ay)) @ exp(Ay)))
where @ denotes the Hadamard product. Therefore, the crux of the issue is accessing these solutions. Fortunately, we'll formalize, this can be achieved by observing sufficiently many random entries of U.
To preface, for each subset S C [d][>, we define the row selection matric Dg as the matrix such that
DsA Ar(iLm.ii))
iN)
(7)
where the rows adhere to the ordering induced by æ. We similarly define D for the complement S: [d][d] [d] As a result, there always a row permutation matrix Ps E 1) xaN where
D AgA
PsA
(8)
As we've established, since each entry corresponds with a particular row of augmented systems, we have the next observation.
Observation 2. Let U
R be rank-1 1 tensor, and let S S [d Then the subset of entries (U ( (s are in correspondence with the pair of linear systems
DsA Dsf(U))e, [DsA Dsf(())
Combining Obscrvation 2 and Obscrvation 1 the same joint solution set ([A) ((U)]r [A] [(U) to complete the tensor via. the aforementioned
it is immediate that just needs satisfy that equation has
procedure.
In Scction we show the sufficient conditions are rows, AD = rows, v, (A) and (owg(DsA) rowa(A)
In other words, given that these hold, any joint solution to equation 9 yields joint solution of the overall systems. The exact procedure is described in the pseudocode for A Algorithm
Hence, we can use Algorithm to solve Rank-1 Tensor Completion by simply running it for a randomly drawn S. Clearly then, we only need show these conditions hold with sufficient probability. To this end, prove the following lemma, which states O(d log samples suffice, although conjecture it can be improved to loglog) Since the result below is crucial for Theorem I.3 elaborate on this conjecture following our overview of the proof technique.
Lemma 2.2. Let S be the subset of indices induced by m uniformly drawn rous of A, with replacement. Then, m S (dN)2 log d samples suffice to ensure both simultaneously hold w.p. 2 2/3.
rows, rows,DsAA) (DsA) roww, (A), rowg (Dwa() rowR(A))
(10)

---

Published in Transactions on Machine Learning Research (6/2025)
Algorithm Rank-1 Linear System Solver
Input: Tensor entries
for S S [d]>
Output: 0 ((r.nnn))) for each desired (fi....,dy) iN) E [d]
Y1 - any solution y Ds (U) over 22
2: Y2 - any solution y to Ay = fU) over R
3: return Ü (in...nk)) = (()((((((....))))))))) exp( ((h)..dw);;))))) for (f1,...,,yy (x) E [d]
Proof. See Section
At a high-level, our proof views rowe, (D as the result of a sequentially constructed subspace W of A's rowspace. We correspond the sample paths of this random process to trajectories on Markov chain whose states are indexed by (dim W, W). Due to the first state coordinate, the chain jumps new state no more than ranky, (A) times before hitting the absorbing state (ranky, (A), (A)). As result, the mcasure of the "bad" event (rows, AA) * rowe, (A)) is given by the cumulative meastre of the "bad' trajectories, i.e. those that stagnate and never hit the absorbing state.
It turns out to be simple to prove the chain self-loops w.p. 11 1/d. Moreover, by pigeonholing, every 'bad' trajectory of length T > ranke, has Q(T' - r0rn2, (A)) self-loops. Thus, the measure of each 'bad" trajectory shrinks exponentially with rate rate _ - (A)). A counting argument shows there are no more than dN ranks,(A) (A) "bad" trajectories, from which we show Old d ranke,(A)) = ((dN)) log d) samples suffice. To handle the other condition (over IR), we show it readily follows from the next fact tandem with Lemma 2.
Fact 2.3. For any binary matriz B, ranky, (B) S rankk (B).
Therefore, it is clear that the bottleneck for improvement is the sample complexity sketching A over F2: supposing that U was unsigned, then A would only need to be sketched as real matrix. By well-known results in leverage score sampling (e.g. Cohen et al. (2015)), one only needs observe O(d log d) rows of a casily verify
rank (dd real matrix to recover its rowspace, if it has uniform leverage scores. And that A satisfies this condition. This implies that the algorithm would be optimal in d for this special case, leaving no particular reason to believe the F2 sketch requires (dd log d). For the interested reader, we refer to Lemma 4.1 as the candidate for improvement.
In the remaining sections, we build up towards Theorem the next section.
1.3 beginning with establishment of A's rank
3 Proof of Lemma 2.1
To give a preview, our strategy is to construct a considerably simpler matrix whose rowspace is identical to A's. We then show that this matrix has the claimed rank. Additionally, the structure of these matrices will a useful reference to streamline the proofs in the next sections. We now provide details the proof.
To start, fix an arbitrary row (e.,..., Civl (A ..x..,,,,)))) } and let & (0, (3 (d-I) 11N+1xdN be the following Fa-vel matrix:

---

Published in Transactions on Machine Learning Research (6/2020)
C
2/2
Cig
Cin
+ e2
0g
0g
0g
+ eg
0g
0,
0,
e1
+ Pa
0a
0a
e1
+ e2
0,8
0,8
PO
e1
+ e3
00
0,
Giv
00
1l + Pa
00
0.
L1
D2
(11)
0
0,
+ e2
0,8
0a
0a
01
+ eg
0.
d n
0.
0,
el
+ e
0a
0a
Oa
0a
C2
0.
0a
0,
0d
0d
0a
+ Cd
For the next claims, recall that A's rows consist of all dN possible vectors of size dN obtained by concate- nating N row vectors from xel])
Lemma 3.1. rows, ()) rowF, (A).
Proof of Lemma 3. By the above assertion, the first row of a row of A. Consider any other row t. This row can be expressed as the sum (el, el) e1, ek: e| ei] mod for some k E [d] both of which are also rows of A. Hence, each individual row contained in rowe, (A), so rowz, (Φ) C rows, (A). On the other hand, for arbitrary row [ej....., :.n. of A, can write
le ejvl (e.,. ......... C.y N
Oo...... Oa, (ei +ew (e1 + (je,),0a O....... 0a] mod 2.
Each of the summands are evidently in the rowspace of &. Hence, rowp, (A) rowp, (.).
Lemma 3.2. dim rown, (.) dN (N 1)
Proof of Lemma 3.2 We first establish that each submatrix 4, for i E [N] has full row rank. Without loss of generality, consider the rows of Φ1. Assume by contradiction e (ci,..., .., ca-1) # O Fn- describes trivial linear combination of them, iee.
Ci + Σ d-1
[e
== 4, Oa...., 0.] = OaN mod 2.
Since no subset of .,,..., sums to 0₂, Σd- G, must be identically Oa, but this necessitates that e = 0a-1, contradiction. An analogous argument applies for every submatrix. Thus, rankz, (Φ1) ranke, (4x) 1.
It easy see that any linear combination of rows in $1...., PN result in nonzero vector. Hence, the stacked matrix (#;; - xx) constitutes linearly independent set of size (d 1)N. We elucidate

---

Published in Transactions on Machine Learning Research (6/2025)
that the first vector is also linearly independent of this stacked matrix. To this end, assume by contradiction that there exists some linear combination of rows in 11.... &N that sum to - Biyl: with coefficients
c [c c² ,,,......c"" ((c)....,cl c.- ..... ((c)...., ,.11)))) FFF-d1)
F2 ((d-1)N
Picking any k E [M] the hth column-blood block satisfics
01 Σn o + EE1 C Ci+1 Ci2
mod
If es, ei, then the first sum dictates of ......; c2_1 must have odd parity and contributes single bit overall. But then the second sum contributes odd mumber of bits. This yiclds mismatch between the parity both sides. If e,, ee,, then second sum must have all ct's zero except for one of them, but then the first sum contributes a single bit, a contradiction for the same reason as before. Thus, the (d 1) + 1 rows of & span linear space of dimension d.N (N - 1).
Lemma 3.2 and Lemin 3.1 together imply rowp, (A) dN -N -N-1), -1. For easy reference, we state a trivial corollary following from the fact. that (ei,:-..; PiN] was initially picked arbitrarily.
Corollary 3.3. For any (ei.................... Bix] E (Ai...., Axx) chosen to construct $, the rows of t in equation consist of basis of rowe,(A)
To handle the case of I, one can apply an almost identical proof to establish the analogous claims for a R-valued matrix I which instead contains rows of the form (Oa...., Od e1 C Oa...., Oa]. We relegate the full matrix description to the Appendix B Following this, the proof of Lemma 2,1 is complete.
4 Proof of Lemma 2.2
To prove Lemmn 2.2 can view the rowspace of A the the cumulative span of the random variable sequence Y1, Y2...., Ym where Y, itd Uni Agy.......)).) ))
Importantly, by Fact 2.3 and Lemma 2.1 whenever we have rowp, (DgA) rowr, (A) we also have rowR (D)
Therefore, to prove our choice of m suffices it is enough show dim simmpannYy ... Ym] ranks, (A) w.p. 2 2/3. Before proceeding to the proof, we assume the next claim holds, which we verify in the sequel.
rows(A)
Lemma 4.1. Suppose W is subspace of rowr, (A) and W contains at least one element of (Ai..... Agv If dim W < (A), then there are at least d rows of A which are each linearly independent of W.
The main message of the above is that as long as W is 'missing a direction" in A's rowspace, there are at least 1/d fraction of rows that would increase its dimensionality.
Let Y1, Yg,.. where Y, sid suffice to ensure dim shanppa
Lemma 4.2.
~ Uni[([AI...... Aax We have that m S (dN) samples Yn) = ranky, (A) w.p. 2 2/3.
Proof of Lemma Let m be a positive integer. To each sequence = (y...... Ym) E (Ai,..., A Jm we associate another sequence ft = (hi,..., (tm) where hü == sp.. is the cumulative span of the first t vectors of the sequence y. Consider the directed graph G (V, E) which
V = {(a, W) a [ranks, (A)], W is subspace of row,, (A))
The edgeset E' is defined as follows. For each m E Noo and each y E {AI..... Aav Jm we include in E the directed edge
(dim N², h?), (dim h441: (Y V
for all t im - 1), emphasizing that self-loops are allowed. Plainly stated, the construction places paths on the graph tracking the cumulative span and its dimension for every possible sequence. Notably, V includes

---

Published in Transactions on Machine Learning Research (6/2025)
the vector o² (ranky, (A), rowez (A)) because A trivially has sequence of rankg, (A) vectors whose span is rowe, (A). In particular, v² has only a single outgoing edge, which is also self-loop.
It follows that the joint distribution of Y1, Y,.... defines a time-homogeneous Markov chain V1, .2.... on the state space V. For each (V1,.... Um) E Paths(G), denote (Ø1,..., "a....,ū))))). as the truncated path obtained by removing self-loops, i.e. any vertex whose previous vertex is identical itself, and in = #1- It follows that the probability dim span(Yi,.... Y o ranke,(A) is at most
Pm # 0²)= = (et P(X1 = UI.... Xm = Um)
(a) Σ (ha. [RE(m) P(X1 = 21 Xm = Um)
www. IP(X1 01 X = 3m x
II
P (uk is self-loop) [ vu is self-loop]
k=1
self-loops (e1...... Mm))
21
mh mrrnanky (A)-1
Σ
Ean [kk[(m]
(0)
m--ronkg, (A)+1 N ranky, (A)
2 1/3
where (a) follows since is an absorbing state; (b) follows by the Markov property and time-homogeneityy (c) uses the observation that P(X++1
X, v) 1 dd" for V \ {u*} by Lemma 4.1 (d) self-loops in paths never reaching v", otherwise > (m - 1) (m - ranke, (A) + 1) ranky, - 2 of the edges are associated with an increase of the cumulative span's dimension implying the chain has to reach v"; (e) uses the observation that there are at most < d' sequences in {A Agv }mh cach of which contributes to at most one length m loop-less walk the graph. Since the path mustn't terminate at v", m rankr, (A), from which the bound follows. Finally, (f) follows from choosing m ranke, (A) 1+ [d (dlog((3)) (3d ranke, (A))), which is ((dN22 log()) since
uses the observation that there are 2 rankr, (A)
rankæ, (A) (ddN) (c.f. Lemma 2.1
Now, il just remains to verify Lemma 4.1
Proof of Lemma 4-1 Consider the set of vectors
= 10 Oa e1 tl ......O.f (0, 1j
1ith position
which are definod for all i [d] \ {1} and n E [N]. There must exist a of which is lincarly independent of W. Otherwise W contains the subspace rowF, (Φ) (ob is defined in equation 11 but rows, (6) rown, (A) by Corollary 3.3, which contradicts the dimension of W. For this df, consider the set of unordered vector + b of mod! 2).
pairs {{a, b) E A
Notably, this set contains exactly N- pairs, as one must. fix the column-block in the th position to be e for one, which fixes the other to be e; varying over the last - column-blocks with d choices for each. For each pair, least one of a or b must be linearly independent of W, for otherwise it contradicts that of is not in the subspace W. Hence, one can find 2 d rows of A, each individually linearly independent of W.
In the next section, we prove the correctness of Algorithm
10

---

Published in Transactions on Machine Learning Research (6/2025)
5 Proof of Theorem 133
Let m denote the quantity in Lemma 4.2 of the previous section. The algorithm asserted in Theorem I.3 simply draws m' = mm, dN) - (((dN))log d) samples, takes S as the set of associated indices, and runs Algorithm I for this input S.
The runtime is immediate. Indcod, the systems in steps (1) and (2) are size m' dN and consistent, so Gauss-Jordan on each terminates in time 0(m'(dN33) The algorithm lakes additional O(N) time per queried entry in step (3), thus OggN m' m'dd))² overall.
We now turn towards establishing the correctness of Algorithm 1 As our choice of m' satisfies Lemma 2.2 we have that rowp, (D5 A) (A) and rowR rowR(D5A) AD5 = rown A) holds w.p. 2 2/3. Thus, it suffices lo prove the following.
Lemma 5.1. Let U 8N R be a ronk-1 tensor. Assume the input S satisfies both
rowp, (DaA) (A), now:(DsA) rowa(A).
Then, the output of Algorithm satisfies Ú U=U.
To start, we establish a useful helper lemma.
Lemma 5.2. Suppose Ax = b is consistent linear system over a field IK, for which
A
bb
A
b
A2
b2
Suppose rowx(A)) = rowx(A), If x* satisfies Aix* = bi, then A2x* b2 holds (and evidently Ax* = b).
By consistency there exists a z such that A₁2 = b1 and A = b Since x* satisfies A₃x" b1, we have x" z E (erg((A) = rowg row)(A,) rowx(A) korg(A). Hence, A(x* z) 0, i.c.
Proof of Lemma 2.2
Ax" Az implying Aax" A2z b2-
Now, we have all the tools prove Lemma 5.1
From equation g let Ps E {0, 10 x
Proof of Lemma
5.1
be a permutation matrix such that
DsA) A
Psf(U) = (Df((U) ( Psf(U) = (sf(U))
(u)(())
PsA-
(12)
By Observation both systems [D5A Dsf(U) and [D Ds)(U) are consistent hence steps (1) and (2) return a Y1 and Y2 for which Ds = (U) and Ds Dsf(U).
We invoke Lemma 5.2 to the two systems induced by equation 12 Specifically, assign A PsA, b (U) and use that DsAy1 Duf(U), upon which the lemmaa lets us conclude PsAy: Psf(U). Had we instead taken b < Psf(U) and used DgAyz Dsf(U), we would conclude PsAyz Psf(U). Since Ps is a row permutation, this implies
Ay1 = f(U), Hence, recalling the map & and the definition of f and f.
Ay: f(U).
x- (Ay = (sign vec, v exp(Ay2) (abs vec, vec.) (U)
Evidently,
yi)) exp U (k = (A(h,) which is what we wanted to show.
= - ((h....
11

---

Published in Transactions on Machine Learning Research (6/2025)
6 Proof of Theorem 1.5g Corollary 1.6
As we'll describe, the lower bound in Theorem 1.5 is consequence of the following.
Lemma 6.1. Consider a variant of the coupon collector problem in which there are N E N>o uris each containing E No0 unique balls. Suppose each draw is given by a uniformly random choice of one ball from each and every urn, for a total of N balls per draw.
There erists absolute constants no E N and C > such that dN 2 ng implies that if less than Cdlog dN drows are laken, then al least one ball is mássed w.p. > 2/3.
By the classic variant, it is easy to see ((d d) is necessary. Since our main result strives for optimal d dependence, this would be enough. For this reason leave the proof to Appendix A which involves recursively applying Hoelldding's lemuna to a particular martingale sequence. However, we feel this result clarifies the 'coupon collector effect" frequently referred to in the tensor completion literature-off often as a remark used to justify the presence of logarithmic factors in the upper bounds. In contrast, our lower bound explicitly uses such an argument. We now detail the lower bound's proof.
Proof of Theorem 1.5 Let M,...., Un ad Unif((=o** }dy and let the random tensor U be given by U := U1 ..... @ uN. Recalling each entry of U is dependent on N out of d.N variables (c.f. equation D we say sampled entry U (x)...x)) collects the variable (ux)e if the former is dependent on the latter. We correspond the samples with the coupon collecting procedure in Lemma 6.1 Concretely, we assign each to the urn i, and each coordinate variable (u:), with the jth ball in the th urn. Let m denote the quantity indicated by (the proof of) Lemma 6.1 Supposing the algorithm collects less than m samples, i.e. |S| < m, then by Lemma 6.1 the algorithm won't collect some variable (ug) ) w.p. > 2/3. We condition on this event for the rest of the proof.
Denote UK'e (w) as U conditioned on the assignment of all the variables in ui...., uy except (ux)) to values specified by outcome Similarly, let U e''t (w) and U (w) denote the nonrandom tensor obtained from these by then fixing (u to +o and -a N respectively. For each w, k (w) and U (w) are vectors in the R'd' inner product space (& Rd. ll...)). Hence, they are bisected by the hyperplane (T, T (w)- separated by distance
K' (w)) 0,
(w) (O)(l)) = 11 vv c²) @ (i = 120 (Vo N-1
| (w) U
20VaN-1
Fixing the outcomes of S and B (where S outcomes are restricted to the aforementioned event), we have that the algorithm output is constant under outcomes UKL and ( (w), and must lie one side of hyperplane. However, w.p. 2 1/2 the target tensor is the other side of the hyperplane, incurring error 2 LovdN- w.p. > (2/3)- (1/2) 1/3.
Under the following assumption, we now prove Corollary 1.6 by approximating the support of the above distribution by tensors of rank 2 r. Recall this property essentially asserts the estimator's error is weakly increasing for perturbations to its input.
A(: Assumption 6.2. Let D, D two distributions over , Rd The randomized estimator A(,SS, B) satisfies a.s. falmost surely) over randomness in S, B, and drows U
D,T D
|| S, B) U|l < |IA(U + T. T.S, B) -
We fix an arbitrary c E (0. Consider Hadamard basis over dimension d. From this basis we may obtain a set of d mutually orthogonal rank-1 tensors with entries in +1, say T. We let Vi...., V, denote an arbitrary but fixed r-size subset of T.
Proof of Corollary 1.6
sid Unif((+(a - =)1/3dd) and let the random tensor Vo be given by Vo 111 uN-
Let U1 un
12

---

Published in Transactions on Machine Learning Research (6/2025)
For each K E Ry0 and outcome w, define (x(w)= = Vo(w) + K Ei=1 V.. Let Di be the distribution of the random variable Ux- Notably, for K 2 r/c we have a.s. that |Ux loo S and Ux is at least rank-(r-1). due to possible cancellations.
Suppose by contradiction that A is a randomized estimator where m is below the threshold in Theorem but w.p. > 2/3 we have that (,, S, B) Ux l| < (1/2)ovdN-1 where and B are as definition 1.4 By reverse triangle incquality, |A(U S, B) - Voll= [VV - Ux S (1/2)ovd dN-I, implying
||A(Ux, Voll= s (1/2)oV
Villa
K
= =(1/2)oVdN-14
Vil[F K
= =1/2)ooVd--++
VdN K
Taking K> 2r/d/a, we have a contradiction to Theorem 1.5
since w.p. 2/3
AA,.. Volle
|A(UK S, Voll 0~ VdN-1.
V
7 Conclusion and Open Questions
This paper presents novel analysis of the rank-1 tensor completion problem, which recasts it in terms of a special pair of linear systems and leverages this viewpoint to improve upon the previously establishod sample complexity bounds. When N x 1, we prove that (dd log d) uniformly observed entries are sufficient to exactly recover rank-1 tensor with nonzero entries (c.f. Theorem 1.3 while S?d d) samples are Notably, neither quantity
necessary (c.I. Theorem L.5), even for higher-rank tensors (c.f. Corollary 1.6
depends on the incoherence μ..
One of our main challenges involves a novel matrix sketch problem over F2, leading to the sample complexity upper bound's quadratic dependence on d. As asserted at the end of Section 2 we conjecture the upper bound can be improved to Ood d) to match the lower bound, primarily by refining Lemma 4.1 This is motivated by the observation that the algorithm is optimal in d when the input tensor is unsigned, as detailed the end of Section We leave the resolution of this conjecture to the future work.
References
Changxiao Cai, Gen Li, H Vincent Poor, and Yuxin Chen. Nonconvex low-rank tensor completion from noisy data. Advances in neural information processing systems, 32, 2019.
Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization. Communications of the ACM, 55(6):111-119, 2012.
Emmanuel J Candes and Terence Tao. The power of convex relaxation: Near-optimal matrix completion.
IEEE Iransactions on information theory, 56(5):2053 2080, 2010.
Yudong Chen. Incoherence-optimal matrix completion. IEEE Trunsactions on Information Theory, 61((): 2909-2923, 2015.
Yudong Chen, Srinadh Bhojanapalli, Sujay Sanghavi, and Rachel Ward. Completing any low-rank matrix, provably. The Journal of Machine Learning Research, 16(1):2999 3034, 2015.
Michael B Cohon, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation. In Proceedings of the 2015 conference on innovations in theoretioal computer science, pp. 181-190, 2015.
13

---

Published in Transactions on Machine Learning Research (6/2025)
Cullen Haselby, Mark Iwen, Santhosh Karnik, and Rongrong Wang. Tensor deli: Tensor completion for low op-rank tensors via random sampling. arXie preprint arXiv24433009082 2024.
Prateek Jain and Sewoong Oh. Provable tensor factorization with missing data. Advances in Neural Infor- mation Processing Systems, 27, 2014.
Thomas Kahle, Kaie Kubjas, Mario Kummer, and Zvi Rosen. The geometry of rank-one tensor completion. SIAM Journal on Applied Algebra and Geometry, 1(1):200 221, 2017.
Franz J Király, Louis Theran, and Ryota Tomioka. The algebraic combinatorial approach for low-rank matrix completion. J. Mach. Learn. Res., 16(1):1391 1436, 2015.
Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51(3):455 500, 2009.
Akshay Krishnamurthy and Aarti Singh. Low-rank matrix and tensor completion via adaptive sampling. Advances in neural information processing systems, 26, 2013.
Allen Liu and Ankur Moitra. Tensor completion made practical. Advances in Neural Information Processing Systems, 118905-18916 2020.
Pei Liu, Jiawei Luo, and Xiangtao Chen. mircom: Tensor completion integrating multi-view information to deduce the potential disease-related mirna-mirne pairs. IEEE/ACM Transactions Computational Biology and Bioinformatics, 19(3):1747-1759) 2022. doi: 1T111///TCBBB2200.33337777
Andrea Montanari and Nike Sun. Spectral algorithms for tensor completion. Communications on Pure and Applied Mathematics, 71(11)2238122255, 2018.
Tung Nguyen and Jeffrey Uhlmann. Tensor completion with provable consistency and fairness guarantoes for recommender systems. ACM Trans. Recomun. Syst., 1(3), August 2023. doi: 10.1145/360466 URL
Aaron Potechin and David Steurer. Exact tensor completion with sum-of sum-of-squares. In Conference on Learning Theory, pp. 1619-1673. PMI.R, 2017.
Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12), 2011.
Matco Rendon Jaramillo. An algebraic and combinatorial perspective on rank-one tensor completion. Mas- ter's thesis, 2018.
Mohit Singh, Alexander Shapiro, and Rui Zhang. Rank one tensor completion problem. arXiv preprint arXiv:2009.1055 2020.
Qingquan Song, Hancheng Ge, James Caverlee, and Xia Hu. Tensor completion algorithms in big data analytics. ACM Transactions on Knowledge Discovery from Data (TKDD), 13(1):1-48, 2019.
Ludovic Stephan and Yizhe Zhu. A non-backtracking method for long matrix and tensor completion. In The Thirly Seventh Annual Conference Learning Theory, pp. 4636-4690 PMLR, 2024.
Xiang- Yu Wang, Xiao-Peng Li, Nicholas D. Sidiropoulos, and Hing Cheung So. Tensor completion network for visual data. IEFF Transactions on Signal Processing, 73:386-400) 2025. doi:
Dong Xia and Ming Yuan. On polynomial time methods for exact low-rank tensor completion. Foundations of Computational Mathematics, 19(6):1265 1313, 2019.
Jinling Zhou, Jiawang Nie, Zheng Peng, and Guangming Zhou. The rank-1 completion problem for cubic tensors. Xiv preprint ar Xiix:2444.0817,, 2024.
14

---

Published in Transactions on Machine Learning Research (6/2025)
A Appendix A Proof of Lemma 6.1
In this section, prove Lemma 6.1
Let z for E [N] denote the random variable counting the remaining balls in urn yet to be seen by and including the tth draw.
Let 1i for E [N] denote the indicator random variable which is '1' if the 8th draw sees previously unseen ball in urn i, and is '0' otherwise.
Let Fe denote the natural filtration generated by the random variables {Z,, 22. ... 1ii=1
Finally, denote Z : E Zi and 4 = Ei-1 Li. In what follows, it is helpful to note that Ze+1 Zi 1441-
Lemma A.1. For any s > 0, d 2 2, and E N we have
E(e ( S 2g (11)))11))'
(13)
Proof. Denoting a 1- 2'
(e ol(+1) = B(E(E ((( (2 Fi))
= -Ele #2 E(e sle4 Ft))
N
(a)
B(e
El Fi))
t=1
E
N
e B E
AN
c +22
E
i=1
3N
21 +
3 E
6
2N E (c
-00%))
(8) AN
S 6 c (e sa' (=-=0²2)-1)
28 (1ta +lta2ta"+---d 1))B c (o-aaz2)
6e
( 28 ("ttaa to sa' (d-(d-1)N
38 (ltata to sa (d- I)N
< e
PAN -sa' 4N
where (a) follows since each urn is sampled from independently; (b) applies Hoeffding's lemma; (c) uses the obscrvation that, given the filtration up to time f, the 7th urn at time + "sces" a new ball if sampling one of Zi uncollected balls out of d; (d) the first recursive application of the bound; and (e) uses the simple observation that the first draw always "sees' N balls, so a.s. Z1 (d 1)N.
We in a position to prove Lemma 6.1
15

---

Published in Transactions on Machine Learning Research (6/2025)
Proof of Lemma 6.1 Fix 3 (0, to be decided later. Assume that the following holds
t Bd dN.
(14)
We have (1 41' 2 e 2 (d so that for any s >> 0 and > 0, by Lemma A.1
P(Z++ S E E (0011))) S e 22N - -111-1) S cee+ PaN (
Let us constrain E (0,2(d))) and take 8= aN (2(d)) - - 6) to give
2 (dN))=1 -0) )
PlZz+ Se) S exp (-an aN
Suppose (dN)=- and dN 2 7 so that
(- ((dN))-22
P(Zz-1 - (dN)) exp
8
In particular, for 3 = 1/4 and d. 2 78, this implies
P(Z++ 5 S P(Z S 1 $ (aN))//4 s exp
VdN
1
8
3
Thus, P(Z > 1) z/b In other words, w.p. 2/3 there remains unseen ball if equation 14 holds for B = 1/4 and dN 2 78.
B Appendix B: + for Proof of Lemma 2.1
In establishing the E rank of A, the following matrix is referred to.
Ci2
Cig
Civ
e2
0g
0,
0g
e3
0g4
0,
0,
cd
0.
0,
0,8
00
e
e2
0.
0.
0
C
C3
0,
0,
ei
eivl
0
1l
Pa
008
0,8
L1
D2
008
e2
0.
0.d
00
0,
4 n
0,a
0,
e,
0,8
:
0a
0a
0a
C2
0.a
0,
0,
e
e3
:
0,
0.
0,
Cd
16


Reviews:
[{"review_id": "ziRZsTBKKr", "reviewer": "Reviewer_WGnL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\nThe presented problem reformulation converts the tensor completion problem into solving two linear systems:\n1. A binary system over $\\mathbb{F}_2$ (for signs)\n2. A real system over $\\mathbb{R}$ (for magnitudes)\nThis separation makes the problem more tractable algorithmically.\n\n**Weaknesses:**\n\nThe paper reads like a collection of small, fragmented definitions and results, and lacks coherent flow and organisation. I would strongly recommend that the paper be rewritten before submission for publication. In particular, various environments including “Theorem”, “Definition”, “Fact”, “Claim” are overused.\n\nBy “nearly-optimal” do you mean the sample complexity is near-optimal in d? However your upper and lower bounds are factor of d apart. I wonder how this can be used to support the near-optimality claim.\n\nIntroduction: “several applications” can you elaborate?\n\nI understand that $\\otimes_{i=1}^N \\mathbb{R}^d_{\\ne 0}$ means you want to exclude the all-zero vector, but I’m unsure how universal this notation is. Better define notation here.\n\nTheorem 1.1 seems unclear to me: why is it an informal version of *three* results simultaneously? Maybe it suffices to describe the theorem in text rather than using the Theorem environment if you are being informal here. What do you mean by “solves rank-1 completion”? I guess you mean by recovering each entry of U correctly with probability at least 2/3? But why failure probability is used later on instead as a measure of the quality of recovery? Also the sample size m should be defined earlier when rank-1 completion is defined. Use $m\\gtrsim d\\log d$ in the last sentence. I think it’s better to call the problem “rank-1 tensor completion” throughout.\n\nbelow Theorem 1.1: incoherence $\\mu$ needs to be defined and references where the definition is drawn from need to be added.\n\nDefinition 1.2: what does CPD stand for?\n\nFootnotes are overused in the paper, and they also appear wordy and unclear, please streamline them. Footnote 1-2: what is BPP? why 2/3 rather than $1-\\delta$ for an arbitrarily small constant $\\delta$? The four footnotes on p.2 can be largely compressed or stated in text IMO. Footnote 7 can also be absorbed into the Notation paragraph. Footnote 8 should also be defined inline. Also make the writing more formal, avoiding colloquial phrases like “blowup” or “the comparison is not that imprecise….”.\n\nThis paper uses extensive notation, so the Notation paragraph on p.3 should be moved much earlier to help readers.\n\nTheorem 1.3: Why introduce q here rather than directly referencing the uniform sampling probability? Also, again, how is the precision of tensor completion defined in this theorem?\n\nAbove Definition 1.4: “We believe this is an artifact of our upper bound”. Is there any reason/ related references to back this claim? If not, it is possible the derived lower bound is loose.\n\nDefinition 1.4: The joint entropy here does not make sense. Shouldn’t it be the conditional entropy H(A|U,S,B) = 0? meaning Given knowledge of U, S, and B, there is no uncertainty about A's output?\n\nTheorem 1.5: I do not understand this lower bound here. What happens with probability 2/3? Since this is a lower bound ie hardness result, the reader would expect that it holds with high probability. Also in text following this theorem, Assumption 6.3 hasnt been stated at this point, which hinders the readability of the results.\n\nCorollary 1.7: can you define what a Hadamard matrix of order d is?\n\nWhile I have not verified the proofs in detail, they appear to rely on elementary probabilistic and linear algebraic arguments that seem sound. However, I would like to better understand the technical contributions. Could you clarify what the main novelties and technical challenges are in your proofs? What are the key insights or non-trivial steps that distinguish this work from others?\n\nThe clarity and organisation of the proofs could be improved. For instance, assumption 6.3 should be stated much earlier on. The various “Claim”s and proofs of the “Claim”s are non-standard and could be omitted.\n\nI’m not sure if the literature review in this paper is sufficient. For instance, what is the closest prior work to the current paper? I wasn’t able to backtrack.\n\nCan your algorithm be straightforwardly extended to the rank>1 case? I guess no, right?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper achieves near-optimal sample complexity for rank-1 tensor completion by introducing a novel linear algebraic characterisation that decomposes the problem into two coupled linear systems over $\\mathbb{F}_2$ and $\\mathbb{R}$. The resulting algorithm requires only $O(d^2 \\log d)$ samples with $O(md^2)$ runtime—a significant improvement over existing sample complexity upper bounds of $d^{1.5} \\mu^{\\Omega(1)} \\log^{\\Omega(1)} d$, where $\\mu$ is the incoherence parameter. The presented upper bound has no dependence on $\\mu$, revealing a complexity gap between rank-1 and higher-rank problems. The authors calculate the computational complexity of the algorithm via Gauss-Jordan. The authors also provide an $\\Omega(d \\log d)$ lower bound for the sample complexity against broad classes of algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the weaknesses described above.", "broader_impact_concerns": "N.A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ow0iyaLeUe", "reviewer": "Reviewer_EHqm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. All theoretical claims are proved.\n2. Related works are discusses.\n3. The tightness of the bound is discussed, even if no intuition about the factor $d$ mismatch between the upper and lower bounds is provided.\n\nWeaknesses\n\n1. No real-world application examples of the rank-1 tensor completion problem are provided.\n2. No experiment corroborating the theoretical results nor real-worlds experiment is provided.\n3. In my opinion, the presentation of the paper lacks clarity.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the rank-1 tensor completion problem. In fact, the problem is to recover the entirety of a rank-1 tensor observing only a small subset of its entries. The authors provide an algorithm to do so boiling down to solving a pair of random linear systems. They show sample and time complexity bounds for it. Moreover, they show a sample complexity lower bound for a broader class of algorithms, highlighting that their method is close-to-optimal.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am not familiar with this literature, however it would be nice to add some experiments, either supporting the theoretical claims or using the proposed algorithm on a real-world application.\n\nMoreover, regarding the presentation of the paper I would suggest:\n1. adding some real-world application examples of the rank-1 tensor completion problem in the introduction of the paper;\n2. I would not introduce the theorems 1.3, 1.5 and corollary 1.7 in the introduction section. I would use it to present the problem, discuss the prior work and present the contributions concisely and clearly at the end of it (as well as the notations eventually);\n3. adding a conclusion at the end of the paper.", "broader_impact_concerns": "No concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oNOi9okoPY", "reviewer": "Reviewer_VEAs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\n- The main strength of the submission is to propose an efficient algorithm which achieves much less computational complexity and much less sample complexity. The existing algorithms have complexity with an exponential dependency on the incoherence. The paper shows that this dependency can be removed.\n\n- The proposed algorithm is simple to implement as it only requires to solve two linear systems of equations. As a comparison, the existing algorithms are much more complicated as they invoke tools from algebraic geometry and matroid theory.\n\n**Weakness**\n- The paper only considers the rank-1 tensor completion problems. This limits the application domain of the proposed algorithms as the practical problems often have low-rank structures with larger ranks.\n- It seems that the paper only considers the noiseless case. It is not clear to me whether the proposed algorithm can still enjoy the improved sample and computational complexity if there are noises in the system.\n- The submission is too technical and difficult to follow as it introduces mathematically-heavy deductions without enough explanations in the derivation of the algorithm. It would be better to introduce more explanations. \n- The paper does not contain empirical verifications of the proposed algorithms. Therefore, it is not clear how the proposed algorithm compares with existing methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of tensor-completion under low rank constraints. Specifically, the paper assumes that the true tensor is of rank-1 and the aim is to recover the true tensor upon the observation of some uniformly sampled entries. The main contribution is to propose an efficient and simple algorithm with less sample complexity and computational complexity. Specifically, the paper shows that it requires $m=O(d^2\\log d)$ samples and run $O(md^2)$ to recover the tensor with probability $\\geq2/3$, where $d$ is the dimension. The basic idea is to reduce the problem to two linear system solvers, one on the field $\\mathbb{F}_2$ and one one $\\mathbb{R}$. These two systems can be efficiently addressed by the Gauss-Jordan method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The paper proposed an interesting algorithm, and gave some theoretical analysis. It is interesting to include an empirical verification of the proposed algorithm, and do some experimental comparison with existing methods to show that it really works in practice.\n\n- What is the challenge to extend the discussion from rank-1 problem to general low-rank problems. It would be beneficial to add some discussions. Furthermore, the comparison of the sample complexity and computational complexity is on the general low-rank problems of existing methods. How does the proposed algorithm compare to existing studies of the rank-1 problem in terms of sample and computational complexity?\n\n- It would be helpful to add more explanations on the derivation of the algorithms. Some notations should be explained clearly. For example, people in applied field may not be familiar with abstract algebra. Therefore, the meaning of $\\mathbb{F}$ should be given clearly\n\n- There are many typos in the paper. Below are some examples.\n\nRemark 1.6: \"exists distinct tensors\"\n\nAbove Eq (6): \"this is can\"\n\nBelow Eq (6): \"rows adheres\"\n\nbottom of Page 5: \"conditions holds\"\n\nSection 5: 'lets $S$\"\n\nLemma 6.1: \"There exists absolute constants\"", "broader_impact_concerns": "I do not see broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)