PaperlayerView exact revision on arXiv

Source-linked AI summary

Worst-Case Completion of Tensors with Approximately Few ANOVA Terms

Simon Foucart, Jingchun Shao

arXiv:2609.38749v1math.NAcs.NA

TL;DR

The paper asks how to complete tensors from incomplete entry observations under an approximate low-order ANOVA assumption. It applies worst-case Optimal Recovery theory and adapts the computations to tensor dimensions. In the stated setting, every regularization map in the family is globally optimal for full recovery, without solving a semidefinite program.

  • Problem

    Optimal Recovery procedures for tensor completion are difficult to construct and evaluate at the ambient dimension, which grows exponentially with the number of modes and makes storing the operator unsuitable.

    Source: §3.2 · p. 13

  • Method

    The paper uses worst-case Optimal Recovery with an ANOVA approximability model and applies the relevant operator through iterative regularized computations when it cannot be stored as a matrix.

    Source: §1 · p. 3, §3.2 · pp. 13–14

  • Results

    For T = ε^-1P_V⊥, U = η^-1Id, and ΛΛ* = Id, every σ ∈ [0, 1] yields a globally optimal regularization map for full recovery, with error independent of σ.

    Source: §4.1 · p. 17, §4.2 · p. 19

  • Takeaways & Limitations

    In that full-recovery setting, the global worst-case error is independent of σ, so no semidefinite program is needed to choose σ.

    Source: §4.1 · p. 17

    In the local setting, linear terms make the S-procedure inexact, so the correct worst-case error is unavailable and only an upper bound is provided.

    Source: §4.1 · p. 16

Abstract

from arXiv · show

In this article, the problem of completing a tensor from some incomplete knowledge of its entries is treated by adopting a worst-case perspective, given the realistic assumption that the tensor's low-order ANOVA terms are dominant. We survey and leverage some recent all-purpose results from the field of Optimal Recovery to provide solutions on a theoretical level. But the accompanying constructions of optimal completion procedures, which often feature semidefinite programs, are not directly applicable in the tensor case due to the huge dimensions involved. To resolve the issue, we put forward a storage-friendly way to produce low-order ANOVA projections based on the fast Fourier transform (FFT), while exploiting the specificities of the completion problem to efficiently compute regularizers and extremal eigenvalues. Numerical experiments on synthetic tensors and real-world datasets demonstrate the accuracy and scalability of our FFT-based method.

1 Introduction

The paper studies worst-case completion of tensors from observed entries when their low-order ANOVA terms provide an approximate model. It adapts Optimal Recovery theory to address the computational and storage challenges posed by tensor dimensions.

1 Introduction

  • The task is to complete a tensor from observed entries, assuming it is approximated within ε by its order-s ANOVA projection.The observations are entries indexed by a set O, and the work adopts a worst-case perspective.Source: §1 · pp. 1–2
  • Tensor completion methods based on low rank provide a contrast: tensor rank and nuclear-norm computations are generally NP-hard.The paper instead uses low-order ANOVA terms as its structural assumption.Source: §1 · p. 2
  • Optimal Recovery frames the task using a model set for prior information, a linear observation map for data, and a recovery map for the quantity of interest.The paper seeks recovery maps that are globally or locally optimal under worst-case error criteria.Source: §1 · p. 2
  • Although existing Optimal Recovery results largely solve the theory, their computational recipes are impractical for tensors with huge dimensions and potentially prohibitive storage needs.The paper surveys theoretical results and adapts computations for the tensor setting.Source: §1 · p. 3

2 The ANOVA Decomposition

The section formalizes low-order ANOVA structure as an approximability model and develops a Fourier-based route to computing its projections. It also identifies observation sets that make recovery well-posed at minimal size.

2 The ANOVA Decomposition

  • ANOVA applies to functions on product probability spaces, with finite tensors as the special case of discrete domains equipped with normalized counting measures.This provides a common notation for general functions and tensors.Source: §2 · p. 4

2.1 Traditional and alternative views

  • An alternative ANOVA view represents components using mutually orthogonal projectors, with the averaging operators commuting.The paper presents this view as a basis for efficient computation.Source: §2.1 · pp. 4–5

2.2 The ANOVA-based approximability set

  • The model assumes terms of order at most s dominate and allows approximation error ε; Condition 6 requires the observation map to be injective on V_s.This implies dim(V_s) ≤ |O|, and the specified set I_{d,s} satisfies the condition at that minimal size.Source: §2.2 · pp. 5–7

2.3 Efficient computations of the ANOVA projections

  • The order-s ANOVA projection can be computed by a Fourier-based method whose cost remains that of the d-dimensional Fourier transform and its inverse.The approach reduces the cost of the naive recursive computation.Source: §2.3 · pp. 8–9
  • The support of the order-s Fourier mask gives an observation set of size dim(V_s) that satisfies Condition 6.A cyclic shift changes the index criterion to having at most s coordinates different from n_j.Source: §2.3 · p. 9

3 Optimal Completion from Accurate Observations

Under accurate observations, known optimal-recovery formulas identify the Chebyshev center, but tensor-scale dimensions make direct semidefinite programs and matrix inversion impractical. The section adapts these formulas to tensor completion through FFT-generated bases and matrix-free computations.

3.1 Summary of known results

  • Known optimal-recovery theory makes the Chebyshev-center map locally optimal and therefore globally optimal, but standard semidefinite programs are impractical at tensor-space dimensions.The tensor space has dimension N = n1 · · · nd, which grows exponentially with d.Source: §3.1 · p. 12, §3.2 · p. 13
  • Finite-dimensional formulas reduce matrix inversions from ambient dimension N to observation and model-subspace sizes; for entry observations, ΛΛ*=Id makes G the identity.The reduced sizes are m for range(Λ) and k for V.Source: §3.1 · p. 13, §3.2 · p. 14

3.2 Tensor computations

  • Conjugate gradient applies matrix-free operators and regularized unconstrained problems; when ΛΛ*=Id, two such solves recover the exact Chebyshev center.The projection-complement action is computed via the ANOVA projection, while Λ*Λ zeros entries outside the observed set.Source: §3.2 · p. 14
  • The preferred tensor construction uses entry-coordinate representers and an FFT-generated orthonormal basis of V_s to realize the Chebyshev-center formula.Producing the basis costs k_s n^d ln(n^d) operations.Source: §3.2 · p. 14
  • The total center-computation cost is O(k_s n^d ln(n^d)) when s is fixed and the number of observations is approximately k_s.This is not much larger than the O(n^d ln(n^d)) cost of one ANOVA projection.Source: §3.2 · p. 14
  • A representer-based optimization alternative is described, but its computational advantage with iterative solvers was not explored.The authors specifically leave open whether conjugate gradient would help solve that program.Source: §3.2 · pp. 14–15
  • The minimal local worst-case error can be computed from a largest-eigenvalue problem, using the power method rather than an oversized semidefinite program.The relevant operators need not be stored as matrices; their actions can be computed iteratively.Source: §3.2 · p. 15

4 Optimal Completion from Inaccurate Observations

This section develops optimal recovery for tensor completion from inaccurate observations with bounded uncertainty, covering results tailored to the observation and uncertainty structure as well as matrix-free methods for high-dimensional tensors and the calculation of minimal worst-case errors.

4.1 Summary of known results

  • In finite dimensions, a globally optimal recovery map can be constructed by regularization, with its optimal parameter determined by a semidefinite program.The map is Γ∘Δσ♯, where σ♯=b♯/(a♯+b♯).Source: §4.1 · pp. 16–17
  • For local full recovery under the tensor assumptions, the true Chebyshev center is a regularizer; finding its parameter by Newton’s method initially entails repeated minimum-eigenvalue calculations [Foucart and Liao, 2023].The optimal τ♯ lies between 1/2 and ε/(ε+η).Source: §4.1 · pp. 17–18

4.2 Two novel results

  • Under the tensor assumptions, every regularization map is globally optimal when Γ=Id or when range(Γ*) is contained in ker(Λ).For Γ(X)=X|U on unobserved entries U⊆O^c, the worst-case error is also independent of the regularization parameter.Source: §4.2 · pp. 19, 21
  • For full recovery with ΛΛ*=Id, the locally optimal map uses a parameter τ♯ that is the unique root of a sextic equation in the stated interval.The interval is between 1/2 and ε/(ε+η); the equation uses c and δ as defined in the theorem.Source: §4.2 · p. 21

4.3 Tensor computations

  • Conjugate gradient computes each regularizer in O(tmax nd ln(nd)) operations, with tmax≤N and matrix-free projection and observation actions costing O(nd ln(nd)) and O(m), respectively.Each iteration uses two applications of the positive-definite normal-equation operator; tmax was typically much smaller than N in the experiments.Source: §4.3 · p. 23
  • In the stated special case, the accurate-scenario Chebyshev center fy is obtained exactly from two regularizers as fy=2fy,1/3−fy,2/3; more generally, fy,τ tends toward fy.The regularizers can themselves be approximately computed by conjugate gradient.Source: §4.3 · p. 23
  • Under the stated assumptions, any τ∈[0,1] is globally optimal for the specified recovery maps; locally, τ♯ solves sextic equation (30) using δ and a single power-method precomputation for c.The quantity δ is available from any computed fy,τ, while c is determined from eigmin(PV⊥+Λ*Λ).Source: §4.3 · pp. 23–24
  • For k ≥ 25 ln(2/θ) and t ≥ ln(9N)/ln(1+ι), the estimator satisfies λmax ≤ bλk,t ≤ (1+ι)λmax with failure probability at most θ.Source: §4.3 · p. 25
  • For Γ=Id under the stated assumptions, the global minimum worst-case error can be obtained from the local minimum at y=0, avoiding an impractical high-dimensional semidefinite program.The local error at any y follows from τ♯, the corresponding minimal eigenvalue, and equation (24).Source: §4.3 · pp. 25–26

5 Numerical Experiments

The experiments assess FFT-based ANOVA projection accuracy and speed, then compare global and local recovery on synthetic and real-world data. Across the datasets, results include faster FFT projections and test errors that vary with interaction order and response.

5.1 Fast ANOVA via the fast Fourier transform

  • The FFT-based projection agrees with the recursive construction to machine precision and is faster in every tested case as tensor order increases.The relative error ranges from 3.09×10−16 to 2.19×10−15; the timing comparison fixes n = 4 and s = 2 while varying d from 5 to 12.Source: §5.1 · pp. 26–27, Figure 1 · p. 27

5.2 Global and local recoveries for Sobol’s function

  • For Sobol’s function, locally optimal recovery has smaller worst-case error than global recovery and slightly reduces full-grid error, while unobserved-grid error is unchanged.With s = 3, the ANOVA approximation error is 2.2759% for the 6,561-entry tensor; the local parameter τ is found by solving a sextic equation.Source: §5.2 · pp. 27–28, Table 1 · p. 28

5.3 Global and local recoveries on the Energy Efficiency dataset

  • Testing error falls from 3.98% to 2.48% for Y1 but rises from 6.66% to 8.71% for Y2 as s increases from 1 to 2.Local worst-case errors are smaller than global ones, while their testing errors coincide because changing τ affects observed entries.Source: §5.3 · pp. 28–29, Table 2 · p. 29

5.4 Global recovery on the Multinary Perovskite Oxides dataset

  • Testing relative error falls from 4.33% to 3.38% when second-order interactions are included; both low-order models stay below 5%.The globally optimal procedure was used on a 39×38×39×38 grid with 2,196,324 entries; the locally optimal procedure was not deployed because it remained too costly at this scale.Source: Table 3 · p. 29, §5.4 · p. 29
Loading 2609.38749v1…