Tensor principal component analysis for the spiked tensor model

ALGORITHM: Tensor principal component analysis for the spiked tensor model
PROBLEM: In the spiked tensor model, an unknown signal vector v_sig in R^N of magnitude √N is hidden inside a p-th order tensor T0 = λ v_sig^⊗p + G, where G is noise whose entries are chosen independently from a Gaussian distribution of zero mean and unit variance and λ is a scalar representing a signal-to-noise ratio; the task called recovery is to infer v_sig to some accuracy given T0, and the simpler task called detection is to distinguish the case λ = 0 from λ = λ̄ for some λ̄ > 0, again just given T0. The paper treats the symmetrized and non-symmetrized cases as reducible to each other, and says that for odd p it is convenient in the analysis not to symmetrize T0 and to take complex G. Recovery is information-theoretically possible for λ much larger than N^((1-p)/2), but no polynomial-time algorithm is known that achieves that performance; the two best known algorithms are spectral and sum-of-squares, and for even p the spectral method works for λ much larger than N^(-p/4), with a variant conjectured to perform similarly for odd p. The regime this record is about is the hard one at and below that spectral threshold: write λ = α N^(-p/4), and the question is what recovery costs as α shrinks.
IDEA: Hastings turns the spiked-tensor problem into a many-body eigenvector problem. The tensor T0 defines a Hamiltonian H(T0) on some number nbos of qudits of dimension N, restricted to their symmetric subspace so that the nbos qudits behave as bosons, and mean-field theory suggests that for large nbos the leading eigenvector can be approximated by a product state; the paper proves that for this statistical model the mean-field approximation becomes accurate with high probability at much smaller nbos than the bounds for arbitrary pairwise Hamiltonians would require. It is careful about what that buys. It does not prove that the nbos-fold tensor product of the single-particle state built from v_sig approximates the leading eigenvector, only that it is a good approximation to some state in an eigenspace with large eigenvalue, and section 5 opens by emphasizing that it is not necessary to find the leading eigenvector itself. Theorems 3 and 5, for even and odd p, then show that any state whose energy exceeds (1 + c′) Emax has, with high probability, a single-particle density matrix whose normalized overlap with v_sig is at least (c′ − o(1)) Emax/E0, so recovery reduces to producing some vector in the eigenspace above the cut. Classically that is the power method on a vector of dimension D(N, nbos), the dimension of the symmetric subspace, which the paper approximates by N^nbos / nbos! and which costs time and space of that order. The quantum algorithm instead phase estimates with H(T0) on a prepared input state and keeps the run only when the eigenvalue lands above the cut: a random input succeeds with probability very close to 1/D(N, nbos), so the plain version buys nothing over classical, amplitude amplification takes the expected time down to D(N, nbos)^(1/2), and a second idea — using the tensor T0 itself to prepare an input state with larger projection onto the target eigenvector — gives a further quadratic speedup, D(N, nbos)^(1/4), which is the quartic. Raising nbos buys recovery at smaller λ at exponentially higher cost, and the abstract sums up the classical side as algorithms with an improved threshold for recovery that work for both even and odd order tensors.
REPORTED COST: Both sides of the comparison are indexed by nbos, and the object whose size sets the cost is D(N, nbos), the dimension of the symmetric subspace of nbos qudits of dimension N, which the paper approximates by N^nbos / nbos! for N much greater than nbos; Emax is its high-probability bound on the largest eigenvalue of the noise Hamiltonian H(G) and E0 the signal energy scale, with the algorithms analysed for E0 at least (1 + c) Emax. Classically, one iteration of the power method on H(T0) takes time Õ(D(N, nbos)) in space Õ(D(N, nbos)), and O(log(D(N, nbos)) / log(E0/Emax)) iterations suffice for detection and recovery, so the paper's total is Õ(D(N, nbos))O(1 / log(E0/Emax)) with space exponential in nbos. Theorem 6 bounds the quantum algorithm's expected runtime by poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε)) exp(O(nbos)) log(N)^(4 nbos) (N^(-p/4)/λ)^(nbos/p) D(N, nbos)^(1/4); the intermediate versions of the same algorithm cost D(N, nbos) and D(N, nbos)^(1/2) times that same poly factor, with plain phase estimation and with amplitude amplification respectively. The polynomial-space claim is not part of theorem 6: it is section 5.2's statement that, in contrast to the classical algorithms above, all these quantum algorithms take only polynomial space. The quartic is a statement about exponents in a stated limit — the log of the quantum runtime divided by the log of the classical runtime approaches 1/4 as N → ∞ at fixed N^(-p/4)/λ, that is, at fixed α. The regime is Assumption 1 together with the paper's standing assumption on λ: nbos = O(N^θ) for a p-dependent constant θ > 0 chosen sufficiently small, λ = Ω(N^(-θ′)) for a p-dependent constant θ′ > p/4, and λ = O(N^(-p/4)) — above that last bound the paper says simple spectral methods already succeed. Below the threshold the price is paid in nbos, which the paper states increases polynomially in λ^(-1) as polylog(N)(N^(-p/4)/λ)^(4/(p-2)) while the runtime increases exponentially. The Zoo's own form for the classical cost, exponential in α^(-1), is the one the paper gives for the sum-of-squares sequence and for the Kikuchi-hierarchy spectral algorithms of Wein, El Alaoui and Moore, not for Hastings's own nbos ladder, whose exponent 4/(p-2) equals 1 only at p = 6.
BASIS: Abstract of arXiv:1907.12724, read off the arXiv abs page: "The quantum algorithm achieves a quartic speedup while using exponentially smaller space than the fastest classical spectral algorithm, and a super-polynomial speedup over classical algorithms that use only polynomial space." What "quartic" is defined to mean is in section 1.2 of the same paper: "The runtime bound for the fastest quantum algorithm is in theorem 6. This theorem gives a quartic improvement in the runtime compared to the fastest classical spectral algorithm; more precisely the log of the runtime with the quantum algorithm divided by the log of the runtime of the classical algorithm approaches 1/4 as N → ∞ at fixed N^(-p/4)/λ." Theorem 6: "Let Assumption 1 hold. For E0 ≥ Emax · (1 + c), for any c > 0, with high probability, the expected runtime of the algorithm is at most poly(N, nbos, 1/(E0 − Emax, log(D(N, nbos)/ε)) exp(O(nbos)) log(N)^(4 nbos) (N^(-p/4)/λ)^(nbos/p) D(N, nbos)^(1/4)." (The unbalanced bracket after 1/(E0 − Emax is the source's own and is reproduced here as printed rather than repaired; subscripts and superscripts are flattened by pdftotext and restored, and the ε was checked against the ar5iv MathML of the same theorem, which spells that symbol out as epsilon inside the same expression.) Classical side, section 5.1: "The space required is then only Õ(D(N, nbos)). The time required for a single iteration of the power method is Õ(D(N, nbos))", and "So, the time is Õ(D(N, nbos))O(1/ log(E0/Emax))". Polynomial space is claimed in section 5.2, not in theorem 6: "In contrast to the classical algorithms above, all these algorithms take only polynomial space." Intermediate quantum bounds, section 5.2.1: "with high probability the time for phase estimation is poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε)), giving an algorithm runtime D(N, nbos) poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε))", and "applying amplitude amplification, with high probability the algorithm succeeds in expected time D(N, nbos)^(1/2) poly(N, nbos, 1/(E0 − Emax), log(D(N, nbos)/ε))". Regime, Assumption 1 in section 1.1: "We assume that nbos = O(N^θ) for some p-dependent constant θ > 0 chosen sufficiently small. We will also assume that λ is Ω(N^(-θ′)) for some p-dependent constant θ′ > p/4.", followed by "Finally, we assume that λ = O(N^(-p/4)). Remark: there is of course no reason to consider λ larger than this since simple spectral methods succeed if λ is ω(N^(-p/4))". Cost of dropping below the threshold, section 1: "the required nbos increases polynomially in λ^(-1) as polylog(N)(N^(-p/4)/λ)^(4/(p-2)), but the runtime increases exponentially." The exponential-in-α^(-1) form belongs to different algorithms, same section: "The sum-of-squares method [4, 5] for this problem gives rise to a sequence of algorithms [6, 7], in which one can recover at λ smaller than N^(-p/4) at the cost of runtime and space increasing exponentially in polylog(N)N^(-p/4)/λ. In Ref. [1], a sequence of spectral algorithms with similar performance was shown." Symmetric-subspace dimension, section 3.1: "For N ≫ nbos, we can approximate D(N, nbos) ≈ N^nbos/nbos!". Recovery guarantee, theorem 3 (even p) and the word-for-word identical theorem 5 (odd p): "Given any vector Ψ such that ⟨Ψ|H(T0)|Ψ⟩ ≥ (1 + c′)Emax for any scalar c′ > 0, then with high probability the corresponding single particle density matrix ρ1 obeys ⟨vsig|ρ1|vsig⟩ / N ≥ (c′ − o(1)) Emax/E0." The Zoo entry "Tensor Principal Component Analysis" does its own arithmetic on the same quantities: "Consider λ = α N^(-p/4). The best classical algorithms succeed when α ≫ 1 and have time and space complexity that scale exponentially in α^(-1). The quantum algorithm of [424] solves this problem in polynomial space and with runtime scaling quartically better in α^(-1) than the classical spectral algorithm."
PRIMARY SOURCE: M. B. Hastings (2019), Classical and Quantum Algorithms for Tensor Principal Component Analysis — https://arxiv.org/abs/1907.12724

This is a literature reference record, not an executable circuit.