PaperlayerView exact revision on arXiv

Source-linked AI summary

Semidefinite Relaxations for Best Rank-1 Tensor Approximations

Jiawang Nie, Li Wang

arXiv:1308.6562v2math.NAcs.NAmath.OC

TL;DR

Best rank-1 tensor approximation is NP-hard, and established methods may yield local solutions whose global optimality is difficult to verify. This paper applies SOS-based semidefinite relaxations to polynomial formulations of symmetric and nonsymmetric tensor approximation, and reports that its algorithms often find best approximations that can be checked mathematically.

  • Problem

    Computing best rank-1 approximations is NP-hard, and common methods may produce only local or stationary solutions whose global optimality is difficult to verify.

    Source: §1 · p. 2, §1.1 · p. 3

  • Method

    The paper formulates symmetric and nonsymmetric approximation as polynomial optimization and solves the problems with SOS-based semidefinite relaxations, using a Newton-CG augmented Lagrangian method for large programs.

    Source: §1.3 · p. 4

  • Results

    The three relaxation-based algorithms very often produce best rank-1 approximations, which can be checked mathematically.

    Source: §4 · p. 22

  • Takeaways & Limitations

    The reported approach often yields best approximations with mathematical checks, providing a practical route within the paper's tested scope.

    Source: §4 · p. 22

    When the optimal matrix has rank greater than one, the extracted tensor is not necessarily best for odd symmetric and nonsymmetric cases.

    Source: §2.2 · p. 9, §2.3 · p. 11

Abstract

from arXiv · show

This paper studies the problem of finding best rank-1 approximations for both symmetric and nonsymmetric tensors. For symmetric tensors, this is equivalent to optimizing homogeneous polynomials over unit spheres; for nonsymmetric tensors, this is equivalent to optimizing multi-quadratic forms over multi-spheres. We propose semidefinite relaxations, based on sum of squares representations, to solve these polynomial optimization problems. Their properties and structures are studied. In applications, the resulting semidefinite programs are often large scale. The recent Newton-CG augmented Lagrangian method by Zhao, Sun and Toh is suitable for solving these semidefinite relaxations. Extensive numerical experiments are presented to show that this approach is practical in getting best rank-1 approximations.

1. Introduction

Best rank-1 tensor approximations exist but are NP-hard to compute, and established methods can leave global optimality difficult to verify. The paper formulates symmetric and nonsymmetric cases as polynomial optimization problems and proposes SOS-based semidefinite relaxations.

1. Introduction

  • Best rank-1 approximations always exist, although computing them is NP-hard; in contrast, best rank-r approximations may be ill-posed when r > 1.Source: §1 · p. 2

1.1. Nonsymmetric tensor approximations.

  • Nonsymmetric rank-1 approximation is equivalent to multilinear optimization over multiple spheres, while common iterative methods may return only local optima or stationary points.Source: §1.1 · pp. 2–3

1.2. Symmetric tensor approximations.

  • For symmetric tensors, the paper uses a symmetric rank-1 minimizer and reduces the search to maximizing the associated homogeneous form on the unit sphere, checking both signs.Source: §1.2 · p. 3

1.3. Contributions of the paper.

  • The paper applies SOS-based semidefinite relaxations to both formulations; these are often tight, and Newton-CG augmented Lagrangian methods address the resulting large programs.Source: §1.3 · p. 4

2. Semidefinite Relaxations and Algorithms

This section formulates best rank-1 tensor approximation as sphere-constrained polynomial optimization and develops SOS-based semidefinite relaxations for even- and odd-order symmetric tensors and nonsymmetric tensors. For nonsymmetric tensors, it describes the relaxation’s upper bound and the conditions under which a rank-one solution certifies a best approximation.

2.1. Symmetric tensors of even orders.

  • Even-order symmetric relaxations optimize sphere-constrained maxima and minima through moment SDPs with SOS duals, then recover candidates from their optimizers and refine them nonlinearly when moment matrices have rank above one.Source: §2.1 · pp. 5–7
  • For even-order symmetric tensors, the relaxations are always tight when m=2 or (n,m)=(3,4), often tight in experiments, and yield a best approximation when both optimizers have rank-one moment matrices.Source: §2.1 · p. 7

2.2. Symmetric tensors of odd orders.

  • Odd-order symmetric forms are lifted to even degree using an extra variable, enabling an SOS semidefinite relaxation whose rank-one solution is exact; higher rank yields only a candidate, often refined by nonlinear optimization.Source: §2.1 · p. 8, §2.2 · pp. 8–9

2.3. Nonsymmetric tensors.

  • Assuming n_m=max_j n_j, linearity in x_m gives |F(x_1,...,x_m)|≤F_sq(x_1,...,x_{m−1})^(1/2)||x_m||; an SDP relaxation maximizes ⟨F_sq,w⟩ subject to K(w)⪰0 and ⟨h,w⟩=1.Source: §2.3 · pp. 9–10
  • F_sdp_max ≥ F_max; equality defines a tight relaxation.Source: §2.3 · p. 10
  • When rank K(w*)=1, the extracted unit vectors maximize (2.13), and Algorithm 2.4 returns a best rank-1 approximation.The algorithm solves the relaxation, extracts the vectors, and sets the output coefficient to F(u1, …, um).Source: §2.3 · pp. 10–11
  • For rank K(w*)>1, extracted vectors may not globally maximize (2.13), so Algorithm 2.4 initializes nonlinear refinement with them; its output is not guaranteed best.Before refinement, the algorithm forms the final factor by normalizing the vector of tensor contractions; approximation quality is analyzed in [23, Section 3].Source: §2.3 · pp. 10–11
  • If F_max·h − F_sq is a smooth point of the cone boundary, then every maximizer w* has rank K(w*)=1.Source: §2.3 · p. 11

3. Numerical Experiments

The numerical experiments evaluate semidefinite-relaxation algorithms for finding best rank-1 approximations of symmetric and nonsymmetric tensors, including their performance on large relaxations.

3. Numerical Experiments

  • The experiments used SDPNAL for large semidefinite programs and applied fmincon when relaxation matrices were not rank one, to improve the resulting approximations.The reported implementation used Matlab 7.10 and default SDPNAL parameters.Source: §3 · p. 11, §3.2 · p. 18

3.1. Symmetric tensor examples.

  • For Examples 3.5 (n=10–55) and 3.6 (n=5–60), Algorithms 2.3 and 2.1 found best rank-1 approximations with very tiny errors; reported runtimes ranged from under a minute to around one hour.For Example 3.5, ratios were around three quarters; for Example 3.6, they were near two thirds.Source: §3.1 · pp. 13–14, Table 1 · p. 14, Table 2 · p. 14
  • Across the reported instances, the algorithms generally produced accurate best rank-1 approximations; most computed matrices M(y*) and M(z*) had rank one, while a few higher-rank cases had errors around 10^-3 or 10^-2, probably because the semidefinite relaxations were not tight.Source: §3.1 · pp. 15–16
  • In the SHOPM comparison, the semidefinite algorithms found best approximations in every reported case, while SHOPM did so only for (n, m) = (35, 3), though its residuals were not significantly larger.The semidefinite algorithms took up to a few minutes, compared with tens of seconds for SHOPM; (20, 4) was omitted because SDPNAL encountered numerical trouble.Source: §3.1 · pp. 16–17, Table 5 · p. 17, Table 6 · p. 17

3.2. Nonsymmetric tensor examples.

  • The reported best rank-1 approximations had errors 8.9e-10 and 3.9e-8, taking about 0.3 second and less than one second, respectively.Their approximation ratios were 0.5194 and 0.9017, respectively.Source: §3.2 · pp. 17–18
  • For n = 5 to 40, all computed K(w*) matrices had rank one and yielded best approximations, but the n = 40 relaxation was too large for SDPNAL to solve accurately.At n = 40, the matrices had length 1600 and the relaxation had 672399 variables; approximation errors were generally very small.Source: §3.2 · pp. 18–19, Table 7 · p. 19
  • For n = 5 to 12, all computed K(w*) matrices had rank one and approximation errors were tiny, while runtime rose to about four hours at n = 12.Runtime was a few seconds for n ≤ 8 and a couple of minutes for n = 9, 10, 11; at n = 12 the relaxation had matrices of length 1728 and 474551 variables.Source: Table 8 · p. 19, §3.2 · p. 19
  • For n = 4, 5, 6, all computed matrices had rank one and yielded best approximations with tiny errors; n = 6 took about 20 minutes.The reported (N, M) pair measures matrix length and number of variables in the semidefinite relaxation.Source: §3.2 · pp. 19–20, Table 9 · p. 20
  • In Example 3.17, K(w*) had rank 4 rather than one, and the SDP upper bound 3.0972 exceeded the best value Fmax = 3; fmincon refinement yielded a best rank-1 approximation.The reported ratio was ρ(F) = 0.4083.Source: §3.2 · p. 20
  • For most random instances with m = 3, 4, 5, Algorithm 2.4 found best rank-1 approximations accurately within reasonable time, though a few errors were around 10^-2.The authors suggest those larger errors may reflect relaxations that are not sufficiently tight.Source: Table 10 · p. 21, Table 11 · p. 21, Table 12 · p. 21

4. Conclusions and discussions

The proposed semidefinite relaxations often yield mathematically checkable best rank-1 approximations, and the paper discusses extensions and computational trade-offs. Large-scale or degenerate semidefinite programs can challenge the solver, while higher-order relaxations and low-rank methods offer further options.

4. Conclusions and discussions

  • The three semidefinite-relaxation algorithms often produce best rank-1 approximations, which can be checked mathematically.The algorithms address even-order symmetric, odd-order symmetric, and nonsymmetric tensors.Source: §4 · p. 22
  • When a relaxation is not tight, higher-order relaxations form a convergent hierarchy that almost always converges within finitely many steps.The paper cites Lasserre and for these convergence results.Source: §4 · p. 22
  • SDPNAL solves most tested relaxations successfully, but numerical troubles and slow convergence can occur for degenerate semidefinite programs.The authors identify efficient methods for large-scale, possibly degenerate, tensor-approximation programs as future work.Source: §4 · p. 23
  • When the relaxation's optimal matrix has rank one, Burer–Monteiro methods may be efficient, but their local nonlinear optimization does not guarantee an optimal solution.The paper cites Burer and Monteiro.Source: §4 · p. 23
  • If the computed matrices have rank greater than one, nonlinear optimization can improve the resulting rank-1 approximation.The experiments use Matlab's fmincon; the paper also mentions the Quasi-Newton method of Savas and Lim [29].Source: §4 · p. 23
Loading 1308.6562v2…