Structured Tensor Approximation from Lateral Slice Sampling via Basis and Manifold Priors

Technical Summary: Structured Tensor Approximation from Lateral Slice Sampling via Basis and Manifold Priors

Problem Formulation
The paper addresses the problem of reconstructing a third-order ground-truth tensor $\mathcal{H} \in \mathbb{R}^{m \times n \times m}$ from a limited number of observed lateral slices. Unlike standard tensor completion problems that assume random entry or fiber sampling, this work focuses on structured lateral slice sampling, where only a subset of slices $\mathcal{C} \in \mathbb{R}^{m \times d \times m}$ (with $d \ll n$) is available. This scenario is motivated by applications in quantum chemistry, specifically the reconstruction of Hessian matrices along a reaction pathway where computational costs limit evaluations to specific points on the trajectory rather than random observations.

The authors posit that such tensors exhibit two complementary structures:

1. Global Structure: Frontal slices evolve smoothly along a physical trajectory (e.g., reaction coordinate) and can be represented by structured basis functions (e.g., Legendre polynomials or Discrete Cosine Transform).
2. Local Structure: Neighboring slices exhibit strong similarity, suggesting an underlying low-dimensional manifold structure.

Methodology: BMTA Framework
The proposed Basis and Manifold prior Tensor Approximation (BMTA) algorithm integrates these two structural priors into a low-rank Tucker reconstruction framework. The method proceeds in three stages:

1. Quasi-Basis Coefficient Estimation:
   The algorithm first estimates a coefficient tensor $\mathcal{Q}$ by assuming the tensor admits a low-dimensional basis representation along the second mode: $\mathcal{H} \approx \mathcal{Q} \times_2 \mathcal{S}$, where $\mathcal{S}$ is a known basis matrix. This step is formulated as a tensor regression problem, yielding a closed-form solution using the Moore–Penrose inverse: $\hat{\mathcal{Q}} = \text{fold}_2(\Psi^\dagger \mathcal{C}_{(2)}) \times_2 \mathcal{S}^\dagger$.

2. Manifold-Guided Interpolation:
   To capture local geometric relationships, the algorithm constructs an interpolation matrix $\hat{\Lambda}_\Omega$. This is achieved by computing pairwise distances between trajectory points (reaction coordinates) and applying a Gaussian (RBF) kernel to estimate weights for unsampled slices based on sampled neighbors. This models the tensor evolution as a smooth manifold.

3. Low-Rank Tucker Optimization:
   The final stage jointly optimizes the Tucker factors (core tensor $\mathcal{G}$ and factor matrices $\mathcal{X}_1, \mathcal{X}_2$) to minimize a composite objective function. This function balances the fit to the quasi-structured prior ($\hat{\mathcal{Q}} \times_2 \mathcal{S}$) and the manifold-guided interpolation estimate ($\mathcal{C} \times_2 \hat{\Lambda}_\Omega$):
   $$\min_{\hat{\mathcal{G}}, \hat{\mathcal{X}}_1, \hat{\mathcal{X}}_2} \alpha \|\hat{\mathcal{Q}} \times_2 \mathcal{S} - \mathcal{H}_{\text{recon}}\|_F^2 + (1-\alpha) \|\mathcal{C} \times_2 \hat{\Lambda}_\Omega - \mathcal{H}_{\text{recon}}\|_F^2$$
   where $\mathcal{H}_{\text{recon}} = \hat{\mathcal{G}} \times_1 \hat{\mathcal{X}}_1 \times_2 \hat{\mathcal{X}}_2 \times_3 \hat{\mathcal{X}}_1$. The optimization is performed via alternating gradient descent.

Theoretical Analysis
The paper provides a non-asymptotic reconstruction error bound (Theorem 1) that characterizes the interplay between optimization convergence, sampling complexity, and model mismatch. Key theoretical findings include:

• Error Decomposition: The reconstruction error is decomposed into a contracting optimization term (which decays geometrically with iterations) and an irreducible approximation error induced by model mismatch (basis error and interpolation error).
• Sampling Complexity: The analysis establishes that the number of sampled slices $d$ must scale with the intrinsic dimension of the basis subspace ($n, l$) to ensure the sampling operator satisfies a subspace embedding property, thereby controlling the distortion introduced by partial observations.
• Convergence: Under specific initialization conditions (within a basin of attraction) and appropriate step sizes, the algorithm converges linearly to a neighborhood of the ground truth.

Experimental Results
The authors validate BMTA on synthetic and real-world datasets:

• Synthetic Data: Experiments on tensors generated from superpositions of polynomial and interpolative components show that BMTA consistently outperforms baselines (Tucker decomposition, TensorCUR, and ablation variants using only one prior) in low-to-moderate sampling regimes. BMTA demonstrates robustness to noise and model mismatch.
• Radio Map Reconstruction: In a synthetic spatio-temporal radio map task, BMTA achieves lower reconstruction error than competing methods when the number of observed slices is limited, effectively preserving spatial patterns that other methods smooth out or distort.
• Quantum Chemistry: Applied to real-world Hessian matrices from chemical reaction systems (e.g., CF3CH3, TSoxo), BMTA achieves the lowest reconstruction error compared to Polynomial-only, Interpolation-only, Tucker, and TensorCUR methods when only 5 slices are observed ($d=5$).

Significance and Claims
The paper claims that BMTA offers a significant improvement over existing tensor approximation methods specifically in scenarios constrained by structured lateral slice sampling. Its primary contribution is the integration of complementary global (basis) and local (manifold) priors, which allows for accurate reconstruction even when the number of observations is too small for standard low-rank methods to estimate subspaces reliably. The work establishes that leveraging domain-specific side information (such as reaction coordinates or known basis functions) is critical for recovering high-dimensional tensor data under severe sampling constraints. The theoretical bounds further clarify the trade-offs between sampling density, model accuracy, and optimization convergence.