Introduction
A common subspace can retain substantial energy from several observations while losing an entire direction in one of them. A determinant detects this loss: it vanishes as soon as the compressed observation becomes singular. This makes volume preservation a natural objective when every direction of a selected subspace must remain represented.
Let A 1 , … , A m A_1,\ldots,A_m A 1 , … , A m P P P k k k
Mean p , w [ det ( P ∗ A i P ) 1 / k ] , P ∗ P = I k . \operatorname{Mean}_{p,w}\left[\det(P^*A_iP)^{1/k}\right], \qquad P^*P=I_k. Mean p , w [ det ( P ∗ A i P ) 1/ k ] , P ∗ P = I k . where Mean p , w \operatorname{Mean}_{p,w} Mean p , w k k k A i A_i A i x ∗ A i x x^*A_ix x ∗ A i x
One motivating example is the Martin mean of subspaces [60 ] . For observed orthonormal frames U i U_i U i − log ∣ det ( U i ∗ P ) ∣ 2 -\log|\det(U_i^*P)|^2 − log ∣ det ( U i ∗ P ) ∣ 2 A i : = U i U i ∗ A_i:=U_iU_i^* A i := U i U i ∗
We give two answers to the question of how much is lost when a solution of a matrix relaxation is rounded to one subspace. For general instances, we determine the optimal approximation factor independent of the ambient dimension, for every fixed selected dimension and rational power at most one, conditional on N P ⊈ B P P \mathrm{NP}\not\subseteq\mathrm{BPP} NP ⊆ BPP − k / 2 -k/2 − k /2 R \mathbb{R} R − k -k − k C \mathbb{C} C ( k , p ) = ( 1 , 1 ) (k,p)=(1,1) ( k , p ) = ( 1 , 1 ) p = 1 p=1 p = 1 § 5 ).
For two rank-k k k k k k
Both results use the same determinant-sensitive trace relaxation. Its domain is T n : = { X ⪰ 0 : tr X = 1 } \mathcal{T}_n:=\{X\succeq0:\operatorname{tr}X=1\} T n := { X ⪰ 0 : tr X = 1 } A A A
f A ( X ) : = k e k ( A 1 / 2 X A 1 / 2 ) 1 / k , f A ( P P ∗ / k ) = v A ( P ) , f_A(X):=k e_k\left(A^{1/2}XA^{1/2}\right)^{1/k}, \qquad f_A(PP^*/k)=v_A(P), f A ( X ) := k e k ( A 1/2 X A 1/2 ) 1/ k , f A ( P P ∗ / k ) = v A ( P ) , where e k e_k e k A = U D U ∗ A=UDU^* A = U D U ∗ k k k U ∗ U = I k U^*U=I_k U ∗ U = I k d : = det ( D ) 1 / k d:=\det(D)^{1/k} d := det ( D ) 1/ k Y : = k X Y:=kX Y := k X f A ( X ) = d det ( U ∗ Y U ) 1 / k f_A(X)=d\det(U^*YU)^{1/k} f A ( X ) = d det ( U ∗ Y U ) 1/ k
Martin means illustrate both conclusions. The geometric-power approximation becomes a sharp dimension-free additive bound for the Martin loss. For two observed subspaces, purification reduces the problem to scalar maximizations in their principal-angle blocks, giving an explicit global solution.
Relation to earlier work
Known scalar factors and Yuan’s subspace proposal. Barvinok [4 ] studied approximation of quadratic images by their convex hulls in relative entropy. Yuan and Parrilo’s 2021 preprint [62 ] gives the rank-sensitive scalar geometric-mean factor (Theorem 1.3) and matching relaxation gaps (Theorem 5.1). These are also Theorems 4.1.3 and 4.5.1 of Yuan’s dissertation [61 ] . Its Theorem 5.4.2 gives the scalar positive-power factors for 0 < p ≤ 1 0 < p \le1 0 < p ≤ 1 1 / p 1/p 1/ p α r , 1 ( p ) \alpha_{r,1}(p) α r , 1 ( p )
More directly, Section 5.6 of the dissertation formulates the common-subspace log-determinant problem, derives a trace relaxation, and proposes independent Gaussian columns followed by polar normalization. It leaves the approximation analysis for future work. That trace relaxation can lose an arbitrarily large factor for determinant volume, even for one positive-definite observation (Section 4.1). Our concave relaxed score instead agrees with the determinant score at every subspace. We establish its sharp approximation and hardness thresholds across the power-mean scale.
The related PSD-permanent literature includes the covariance relaxation of Anari et al. [2 ] and the product-of-linear-forms results of Yuan and Parrilo [63 ] . Anari and Ebrahimnejad’s 2026 preprint [1 ] obtains the optimal exponential approximation exponent, assuming P ≠ N P P \ne NP P = N P
Gaussian rounding and sharp constants. Gaussian rounding is central to semidefinite approximation [40 , 53 ] . For matrix objectives, Nemirovski [39 ] and Naor, Regev and Vidick [38 ] developed semidefinite approximation under orthogonality constraints and noncommutative Grothendieck rounding. Bandeira, Kennedy and Singer [3 ] combine Gaussian matrix rounding and polar projection in the real and complex settings. Their constants involve mean Gaussian singular values, with matching relaxation gaps. Their objective is quadratic in several orthogonal or unitary blocks; our determinant-root means require determinant moments. Briët, de Oliveira Filho and Vallentin [11 ] obtain Gamma-ratio approximation constants for the PSD Grothendieck problem with a Gram-rank constraint, with optimality under the Unique Games Conjecture. That Gram rank differs from the covariance rank in our rounding bound.
Sharp NP-hardness thresholds governed by Gaussian moments also occur in geometric approximation [26 ] . Our reductions use the real and complex norm-hardness results of Briët, Regev and Saket [12 ] and the block-subspace promise in the full version of Ebrahimnejad, Nagda and Oveis Gharan [18 ] . The Yuan–Parrilo product-of-forms hardness theorem [62 ] , Theorem 7.1 has factor ( 1 − ε ) 1 / d (1-\varepsilon)^{1/d} ( 1 − ε ) 1/ d d = Ω ( n ) d = \Omega(n) d = Ω ( n ) [61 ] , Theorem 4.7.1); it does not identify a sharp constant-factor threshold. Tensor amplification also appears in norm hardness [8 ] ; our arithmetic-power argument controls coefficient energies across tensor orientations. General Stiefel and Grassmann hardness [29 , 30 ] concerns broader objective classes.
Elementary-symmetric volume criteria. The concavity of elementary-symmetric roots [6 , 21 , 34 ] and Gaussian determinant moments [20 , 23 , 37 , 41 ] are established ingredients. Pronzato, Wynn and Zhigljavsky [47 ] interpret elementary symmetric polynomials of covariance eigenvalues through expected squared simplex volumes and study their concave roots. Mariet and Sra [35 ] use elementary symmetric polynomials as partial-volume criteria in experimental design. These give geometric and statistical context for our relaxed score e k 1 / k e_k^{1/k} e k 1/ k [25 ] ; Saunderson and Parrilo [49 ] give polynomial-size semidefinite representations of the associated derivative cones. Our algorithm uses the evaluation and separation oracles proved in Appendix § 12 ; a cone representation alone does not formulate the full power-mean objective.
Two-observation exactness. Fair dimensionality reduction [48 , 54 ] studies several retained-energy criteria. Tantipongpipat et al. [54 Theorem 1.2] prove exactness for two affine criteria under a concave aggregation nondecreasing in at least one argument. Li and Xie [32 Corollary 4] recover two-criterion fair-PCA exactness within a general theory of partial convexification and rank bounds. Their fair-PCA relaxation includes an eigenvalue cap. Shen et al. [50 ] exploit hidden convexity to solve two-group fair PCA through eigenvalue optimization of reconstruction-loss trace criteria. Randomized SDP rank reduction [52 ] controls relative deviations in linear measurements.
Our two-view purification theorem instead simultaneously preserves two nonlinear determinant scores from the full trace-k k k k k k [10 , 27 ] . The author’s 2026 preprint [46 ] gives scalar exactness under a lower-envelope convexity condition, automatic for two real forms (Proposition 3.2 and Corollaries 4.1–4.2). Those scalar results allow general observation ranks; the two-view determinant theorem here assumes rank-k k k
Subspace means and optimization methods. Stiefel and Grassmann optimization has a classical geometric foundation [19 ] ; a recent account is [7 ] . Feasible manifold methods [58 ] and nonlinear eigenvalue methods [31 ] provide iterative algorithms; the convergence guarantees in the latter framework are to stationary points under its assumptions. Semidefinite methods for quadratic frame objectives [14 , 15 , 22 ] also relax orthogonality. Cory-Wright and Pauphilet’s extended version [15 arXiv version 4] gives a 1/3 approximation using Gaussian polar rounding. These objectives are quadratic in a frame; ours are generally nonlinear and invariant under changes of basis. Xu’s 2026 preprint [59 ] uses a smooth minimum of compressed log determinants, equivalently a logarithmic negative-power-mean objective, and develops stationary-point methods for the continuous subspace stage.
The Martin loss originates in a metric for ARMA processes [36 ] , with its subspace-angle interpretation developed in [16 ] . Yang and Hospedales [60 ] explicitly optimize the finite-dimensional Martin mean. Our results give a global approximation guarantee and an explicit solution for two subspaces. The relaxed weighted log-determinant problem belongs to the MAXDET and weighted determinant-maximization families [55 , 56 ] . Binet–Cauchy kernels [57 ] use determinant overlaps; averaging squared overlaps corresponds to power p = k p=k p = k [5 ] instead minimize squared geodesic distances, which gives a different loss from Martin’s logarithmic determinant.
Discrete determinant selection. Subdeterminant maximization and largest-simplex approximation [17 , 33 , 42 , 43 ] select vectors from a finite collection. Brown et al. [13 ] develop constructive matroid-intersection algorithms for determinant maximization. Experimental design [44 , 51 ] aggregates selected information matrices; the partial-volume criteria of [35 ] connect this literature to elementary symmetric polynomials. Here every fixed observation is compressed to the same variable subspace. Constants depend on normalization: a factor b b b b k b^k b k
Organization. § 2 fixes notation and the computational model. § 3 states the classification and its uniform-input algorithmic form. § 4 develops the trace relaxation and Gaussian rounding; § 5 gives matching hardness and its transfer to subspace observations. § 6 proves two-view purification, and § 7 derives the Martin consequences. Full technical proofs and numerical guarantees are in Appendices § 9 –§ 18 .
Notation and problem formulation
Notation
The field F \mathbb{F} F R \mathbb{R} R C \mathbb{C} C A ∗ A^* A ∗ A ⪰ 0 A \succeq0 A ⪰ 0 A ≻ 0 A \succ0 A ≻ 0 A ⪰ B A \succeq B A ⪰ B A − B ⪰ 0 A-B \succeq0 A − B ⪰ 0 A 1 / 2 A^{1/2} A 1/2 A A A ∥ ⋅ ∥ op \lVert\cdot\rVert_{\operatorname{op}} ∥ ⋅ ∥ op ∥ ⋅ ∥ F \lVert\cdot\rVert_F ∥ ⋅ ∥ F
An orthonormal k k k St ( n , k ) : = { P ∈ F n × k : P ∗ P = I k } \operatorname{St}(n,k):=\{P\in\mathbb{F}^{n\times k}:P^*P=I_k\} St ( n , k ) := { P ∈ F n × k : P ∗ P = I k } k k k P P ∗ PP^* P P ∗ P ⊥ P_\perp P ⊥
For a positive semidefinite d × d d\times d d × d C C C λ 1 , … , λ d \lambda_1,\ldots,\lambda_d λ 1 , … , λ d
e j ( C ) : = ∑ 1 ≤ i 1 < ⋯ < i j ≤ d λ i 1 ⋯ λ i j , e 0 ( C ) : = 1. e_j(C):=\sum_{1\le i_1<\cdots<i_j\le d}\lambda_{i_1}\cdots\lambda_{i_j},\qquad e_0(C):=1. e j ( C ) := 1 ≤ i 1 < ⋯ < i j ≤ d ∑ λ i 1 ⋯ λ i j , e 0 ( C ) := 1. Thus e 1 ( C ) = tr C e_1(C)=\operatorname{tr} C e 1 ( C ) = tr C e d ( C ) = det C e_d(C)=\det C e d ( C ) = det C det ( I d + z C ) = ∑ j = 0 d e j ( C ) z j \det(I_d+zC)=\sum_{j=0}^{d}e_j(C)z^j det ( I d + z C ) = ∑ j = 0 d e j ( C ) z j e k ( C ) e_k(C) e k ( C ) k × k k\times k k × k C C C
We use natural logarithms and the functions
Γ ( x ) : = ∫ 0 ∞ t x − 1 e − t d t , ψ ( x ) : = d d x log Γ ( x ) ( x > 0 ) . \Gamma(x):=\int_{0}^{\infty}t^{x-1}e^{-t}\,\mathrm{d}t,\qquad\psi(x):=\frac{\mathrm{d}}{\mathrm{d}x}\log\Gamma(x)\qquad(x>0). Γ ( x ) := ∫ 0 ∞ t x − 1 e − t d t , ψ ( x ) := d x d log Γ ( x ) ( x > 0 ) . Set β : = 1 / 2 \beta:=1/2 β := 1/2 R \mathbb{R} R β : = 1 \beta:=1 β := 1 C \mathbb{C} C ( ξ + i ζ ) / 2 (\xi+i\zeta)/\sqrt{2} ( ξ + i ζ ) / 2 ξ , ζ \xi,\zeta ξ , ζ E \mathbb{E} E Pr \Pr Pr
Volume scores and their means
Fix 1 ≤ k ≤ n 1\le k\le n 1 ≤ k ≤ n n × n n\times n n × n A 1 , … , A m ⪰ 0 A_1,\ldots,A_m\succeq0 A 1 , … , A m ⪰ 0 w i w_i w i A i A_i A i observations ; in applications they may be covariance or second-moment matrices, or orthogonal projections onto observed subspaces. For nonnegative scalars, the weighted power mean is
Mean p , w [ a 1 , … , a m ] : = { ( ∑ i = 1 m w i a i p ) 1 / p , p ≠ 0 , ∏ i = 1 m a i w i , p = 0. (1) \operatorname{Mean}_{p,w}[a_1,\ldots,a_m]:=
\begin{cases}
\left(\sum_{i=1}^{m}w_i a_i^p\right)^{1/p}, & p\ne0,\\
\prod_{i=1}^{m}a_i^{w_i}, & p=0.
\end{cases} \tag*{(1)} Mean p , w [ a 1 , … , a m ] := { ( ∑ i = 1 m w i a i p ) 1/ p , ∏ i = 1 m a i w i , p = 0 , p = 0. (1) At zero coordinates we use the continuous extension: if any positive-weight coordinate vanishes, the mean is zero for p ≤ 0 p\le0 p ≤ 0 Mean p , w [ a i ] \operatorname{Mean}_{p,w}[a_i] Mean p , w [ a i ] Mean p \operatorname{Mean}_p Mean p
The compression P ∗ A P P^*AP P ∗ A P k k k
v A ( P ) : = det ( P ∗ A P ) 1 / k = ( ∏ j = 1 k λ j ( P ∗ A P ) ) 1 / k , (2) v_A(P):=\det(P^*AP)^{1/k}=\left(\prod_{j=1}^{k}\lambda_j(P^*AP)\right)^{1/k}, \tag*{(2)} v A ( P ) := det ( P ∗ A P ) 1/ k = ( j = 1 ∏ k λ j ( P ∗ A P ) ) 1/ k , (2) OPT p , k ( A , w ) : = max P ∈ St ( n , k ) Mean p , w [ v A i ( P ) ] . \operatorname{OPT}_{p,k}(A,w):=\max_{P\in\operatorname{St}(n,k)}\operatorname{Mean}_{p,w}[v_{A_i}(P)]. OPT p , k ( A , w ) := P ∈ St ( n , k ) max Mean p , w [ v A i ( P )] . Replacing P P P P U PU P U U U U R \mathbb{R} R det ( P ∗ A P ) \det(P^*AP) det ( P ∗ A P ) k k k A 1 / 2 A^{1/2} A 1/2 A A A
There are two distinct averages: the geometric mean within one compressed observation and the chosen power mean across observations. The identity
Mean p , w [ d i 1 / k ] k = Mean p / k , w [ d i ] \operatorname{Mean}_{p,w}[d_i^{1/k}]^k=\operatorname{Mean}_{p/k,w}[d_i] Mean p , w [ d i 1/ k ] k = Mean p / k , w [ d i ] also shows why arithmetic averaging of raw determinants corresponds to p = k p=k p = k p = 1 p=1 p = 1
Input, output, and guarantees
Computational statements use rational matrix entries, rational powers, and positive rational weights. Over C \mathbb{C} C B o u t B_{\mathrm{out}} B out B o u t ( B o u t ∗ B o u t ) − 1 B o u t ∗ B_{\mathrm{out}}(B_{\mathrm{out}}^{*}B_{\mathrm{out}})^{-1}B_{\mathrm{out}}^{*} B out ( B out ∗ B out ) − 1 B out ∗
A factor ρ ∈ [ 0 , 1 ] \rho\in[0,1] ρ ∈ [ 0 , 1 ] ρ OPT p , k \rho\operatorname{OPT}_{p,k} ρ OPT p , k 2 / 3 2/3 2/3 k k k p p p ρ \rho ρ N P ⊈ B P P \mathrm{NP} \not\subseteq\mathrm{BPP} NP ⊆ BPP
Sharp approximation guarantees
The computational threshold
For the fixed field parameter β \beta β p ≤ 1 p \le1 p ≤ 1
α k ( p ) : = { 0 , p ≤ − k β , 1 k β [ ∏ j = 1 k Γ ( j β + p / k ) Γ ( j β ) ] 1 / p , p > − k β , p ≠ 0 , 1 k β exp ( 1 k ∑ j = 1 k ψ ( j β ) ) , p = 0. (3) \alpha_k(p) :=
\begin{cases}
0, & p \le-k\beta,\\
\frac{1}{k\beta}\left[\prod_{j=1}^{k}\frac{\Gamma(j\beta+p/k)}{\Gamma(j\beta)}\right]^{1/p}, & p>-k\beta,\quad p\ne0,\\
\frac{1}{k\beta}\exp\left(\frac{1}{k}\sum_{j=1}^{k}\psi(j\beta)\right), & p=0.
\end{cases} \tag*{(3)} α k ( p ) := ⎩ ⎨ ⎧ 0 , k β 1 [ ∏ j = 1 k Γ ( j β ) Γ ( j β + p / k ) ] 1/ p , k β 1 exp ( k 1 ∑ j = 1 k ψ ( j β ) ) , p ≤ − k β , p > − k β , p = 0 , p = 0. (3) For p > − k β p>-k\beta p > − k β ∣ det H ∣ 2 / k / k |\det H|^{2/k}/k ∣ det H ∣ 2/ k / k H H H p = − k β p=-k\beta p = − k β
Theorem 3.1 (Sharp approximation classification). Fix the field, an integer k ≥ 1 k \ge1 k ≥ 1 p ≤ 1 p \le1 p ≤ 1 For problem (2) :
If p > − k β p>-k\beta p > − k β ( k , p ) ≠ ( 1 , 1 ) (k,p)\ne(1,1) ( k , p ) = ( 1 , 1 ) α k ( p ) OPT p , k \alpha_k(p)\operatorname{OPT}_{p,k} α k ( p ) OPT p , k
For every fixed ρ \rho ρ α k ( p ) < ρ < 1 \alpha_k(p)<\rho<1 α k ( p ) < ρ < 1 ρ \rho ρ p ≤ − k β p\le-k\beta p ≤ − k β
The hardness holds for equally weighted rational PSD observations of rank at most k k k k k k p = 0 p=0 p = 0 ( k , p ) = ( 1 , 1 ) (k,p)=(1,1) ( k , p ) = ( 1 , 1 )
Table 1. The parameters held fixed in the approximation statements.
The proof is assembled in Section B.8. Under NP ⊈ \not\subseteq ⊆ n n n m m m p = − k β p=-k\beta p = − k β negative-moment boundary , since it is where the inverse-power Gaussian determinant moment ceases to be finite. A zero universal factor does not say that all instance optima vanish: it excludes one fixed positive relative guarantee over the entire family.
A single algorithm with dimension and power as inputs
Theorem 3.1 fixes k k k p p p 0 < δ < 1 0 < \delta< 1 0 < δ < 1
− ( 1 − δ ) k β ≤ p ≤ 1. (4) -(1-\delta)k\beta\le p \le1. \tag*{(4)} − ( 1 − δ ) k β ≤ p ≤ 1. (4) Theorem 3.2 (Attainment of the threshold). Fix the field and 0 < δ < 1 0 < \delta< 1 0 < δ < 1 α k ( p ) \alpha_k(p) α k ( p ) k , p k,p k , p ( k , p ) = ( 1 , 1 ) (k,p)=(1,1) ( k , p ) = ( 1 , 1 ) ( k , p ) = ( 1 , 1 ) (k,p)=(1,1) ( k , p ) = ( 1 , 1 ) 1 − ε 1-\varepsilon 1 − ε max ( 1 , 1 / ε ) \max(1,1/\varepsilon) max ( 1 , 1/ ε )
The proof is in Section B.8, with the scalar near-one estimate in Section B.7. Attainment means that the displayed factor has no additional subtracted error allowance. The Gamma constant appears only in the analysis; rational-output limitations at ( k , p ) = ( 1 , 1 ) (k,p)=(1,1) ( k , p ) = ( 1 , 1 ) p < 1 p<1 p < 1 p p p 1 / ( 1 − p ) 1/(1-p) 1/ ( 1 − p )
Table 1 distinguishes this assertion from the finite-dimensional guarantee of § 4 and the hardness theorem.
The determinant relaxation and Gaussian rounding
A subspace determines a normalized projection matrix. We relax that matrix to an arbitrary PSD matrix of trace one, while retaining the determinant information in every observation. Gaussian sampling then converts the fractional solution back to one subspace.
A determinant-sensitive trace relaxation
Let
T n : = { X ⪰ 0 : tr X = 1 } . (5) \mathcal{T}_n := \{X \succeq0 : \operatorname{tr} X = 1\}. \tag*{(5)} T n := { X ⪰ 0 : tr X = 1 } . (5) For A ⪰ 0 A \succeq0 A ⪰ 0
f A ( X ) : = k e k ( A 1 / 2 X A 1 / 2 ) 1 / k . (6) f_A(X) := k e_k\left(A^{1/2} X A^{1/2}\right)^{1/k}. \tag*{(6)} f A ( X ) := k e k ( A 1/2 X A 1/2 ) 1/ k . (6) We call f A f_A f A relaxed score of observation A A A [34 ] makes this function concave on the PSD cone. It is nonnegative, Loewner-increasing, and homogeneous of degree one. Monotonicity follows from eigenvalue monotonicity. These properties extend to the boundary by continuity. If rank A < k \operatorname{rank} A < k rank A < k f A f_A f A
For an orthonormal k k k P P P A 1 / 2 P P ∗ A 1 / 2 A^{1/2}PP^*A^{1/2} A 1/2 P P ∗ A 1/2 P ∗ A P P^*AP P ∗ A P
f A ( P P ∗ / k ) = det ( P ∗ A P ) 1 / k = v A ( P ) . (7) f_A(PP^*/k) = \det(P^*AP)^{1/k} = v_A(P). \tag*{(7)} f A ( P P ∗ / k ) = det ( P ∗ A P ) 1/ k = v A ( P ) . (7) Since the power mean is concave and coordinatewise increasing for p ≤ 1 p \le1 p ≤ 1
F ( X ) : = Mean p , w [ f A i ( X ) ] F(X) := \operatorname{Mean}_{p,w}[f_{A_i}(X)] F ( X ) := Mean p , w [ f A i ( X )] is concave on T n \mathcal{T}_n T n S ⋆ S^\star S ⋆ S ⋆ ≥ OPT p , k S^\star\ge\operatorname{OPT}_{p,k} S ⋆ ≥ OPT p , k k k k X ⪯ I / k X \preceq I/k X ⪯ I / k [45 ] ; the domain (5) omits this spectral cap.
Why the relaxed score must retain determinants. The trace constraint does not make this a linear trace surrogate. For A : = diag ( 1 , ε , ε ) A := \operatorname{diag}(1,\varepsilon,\varepsilon) A := diag ( 1 , ε , ε ) k = 2 k = 2 k = 2 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 ε \sqrt{\varepsilon} ε max X ∈ T 3 tr ( A X ) = 1 \max_{X \in\mathcal{T}_3} \operatorname{tr}(AX) = 1 max X ∈ T 3 tr ( A X ) = 1 [61 Section 5.6] does not repair this gap: X : = diag ( 1 / 2 , 1 / 2 , 0 ) X := \operatorname{diag}(1/2,1/2,0) X := diag ( 1/2 , 1/2 , 0 ) X ⪯ I / 2 X \preceq I/2 X ⪯ I /2 tr X = 1 \operatorname{tr} X = 1 tr X = 1 ( 1 + ε ) / 2 (1+\varepsilon)/2 ( 1 + ε ) /2 (7) is the essential property of our relaxed score.
The finite-rank rounding factor
For a relaxed matrix of rank r ≥ k r \ge k r ≥ k − k β < p ≤ 1 -k\beta< p \le1 − k β < p ≤ 1
α r , k ( p ) : = r k [ ∏ j = 1 k Γ ( j β + p / k ) Γ ( ( r − j + 1 ) β ) Γ ( j β ) Γ ( ( r − j + 1 ) β + p / k ) ] 1 / p (8) \alpha_{r,k}(p) := \frac{r}{k}\left[\prod_{j=1}^{k}\frac{\Gamma(j\beta+ p/k)\Gamma((r-j+1)\beta)}{\Gamma(j\beta)\Gamma((r-j+1)\beta+ p/k)}\right]^{1/p} \tag*{(8)} α r , k ( p ) := k r [ j = 1 ∏ k Γ ( j β ) Γ (( r − j + 1 ) β + p / k ) Γ ( j β + p / k ) Γ (( r − j + 1 ) β ) ] 1/ p (8) (p ≠ 0 p \ne0 p = 0
α r , k ( 0 ) ≔ r k exp ( 1 r ∑ j = 1 k [ ψ ( j β ) − ψ ( ( r − j + 1 ) β ) ] ) . (9) \alpha_{r,k}(0) \coloneqq\frac{r}{k}\exp\left(\frac{1}{r}\sum_{j=1}^{k}\left[\psi(j\beta)-\psi((r-j+1)\beta)\right]\right). \tag*{(9)} α r , k ( 0 ) : = k r exp ( r 1 j = 1 ∑ k [ ψ ( j β ) − ψ (( r − j + 1 ) β ) ] ) . (9) Its limit as r → ∞ r \to\infty r → ∞ α k ( p ) \alpha_k(p) α k ( p )
Theorem 4.1 (Gaussian rounding) Let A 1 , … , A m ⪰ 0 A_1,\ldots,A_m \succeq0 A 1 , … , A m ⪰ 0 w i > 0 w_i > 0 w i > 0 X ∈ T n X \in\mathcal{T}_n X ∈ T n r ≥ k r \ge k r ≥ k Z Z Z n × k n \times k n × k − k β < p ≤ 1 -k\beta< p \le1 − k β < p ≤ 1 Z Z Z P : = G ( G ∗ G ) − 1 / 2 P := G(G^*G)^{-1/2} P := G ( G ∗ G ) − 1/2 G : = X 1 / 2 Z G := X^{1/2}Z G := X 1/2 Z
Mean p , w [ v A i ( P ) ] ≥ α r , k ( p ) Mean p , w [ f A i ( X ) ] . (10) \operatorname{Mean}_{p,w}[v_{A_i}(P)] \ge\alpha_{r,k}(p)\operatorname{Mean}_{p,w}[f_{A_i}(X)]. \tag*{(10)} Mean p , w [ v A i ( P )] ≥ α r , k ( p ) Mean p , w [ f A i ( X )] . (10) The factor obeys α k ( p ) ≤ α r , k ( p ) ≤ 1 \alpha_k(p) \le\alpha_{r,k}(p) \le1 α k ( p ) ≤ α r , k ( p ) ≤ 1 r = k r = k r = k X X X
The proof is in Section A.2. Here X X X § 9 .
Cauchy–Binet writes each Gaussian numerator det ( G ∗ A i G ) \det(G^*A_iG) det ( G ∗ A i G ) det ( G ∗ G ) \det(G^*G) det ( G ∗ G )
The change of measure is a proof device. The algorithm draws ordinary Gaussian matrices. Section A supplies a success probability that is polynomially bounded uniformly in the covariance and the input power, away from the negative moment boundary.
The finite-dimensional algorithm
Theorem 4.2 (Finite-dimensional approximation) Fix the field and 0 < δ < 1 0 < \delta< 1 0 < δ < 1 1 ≤ k < n 1 \le k < n 1 ≤ k < n − ( 1 − δ ) k β ≤ p ≤ 1 -(1-\delta)k\beta\le p \le1 − ( 1 − δ ) k β ≤ p ≤ 1 ε > 0 \varepsilon> 0 ε > 0 2 / 3 2/3 2/3
( α n , k ( p ) − ε ) OPT p , k (\alpha_{n,k}(p)-\varepsilon)\operatorname{OPT}_{p,k} ( α n , k ( p ) − ε ) OPT p , k in time polynomial in the complete input bit length and max ( 1 , 1 / ε ) \max(1,1/\varepsilon) max ( 1 , 1/ ε )
The proof, including numerical precision, is in Section B.5. The procedure is:
Approximately maximize F F F T n \mathcal{T}_n T n
Draw independent Gaussian columns with that covariance and keep their span.
Repeat polynomially many times and retain the subspace with the largest computed objective value.
The polynomial det ( I + t X A i ) \det(I+tXA_i) det ( I + tX A i )
The finite-rank factor is strictly larger than α k ( p ) \alpha_k(p) α k ( p ) ( k , p ) = ( 1 , 1 ) (k,p)=(1,1) ( k , p ) = ( 1 , 1 ) k ≥ 2 k\ge2 k ≥ 2
α n , k ( p ) α k ( p ) ≥ exp ( k − 1 2 n ) . \frac{\alpha_{n,k}(p)}{\alpha_k(p)} \ge\exp\left(\frac{k-1}{2n}\right). α k ( p ) α n , k ( p ) ≥ exp ( 2 n k − 1 ) . Together with a separate scalar estimate, this surplus pays for optimization and output precision, yielding the exact factor in Theorem 3.2. As p ↑ 1 p \uparrow1 p ↑ 1 α n , 1 ( p ) − α 1 ( p ) \alpha_{n,1}(p)-\alpha_1(p) α n , 1 ( p ) − α 1 ( p ) 1 − α 1 ( p ) 1-\alpha_1(p) 1 − α 1 ( p ) 1 − p 1-p 1 − p
Matching computational hardness
The approximation factors in § 3 are sharp for each fixed selected dimension and power. The reductions below use equal weights and have perfect completeness: in the YES case, one subspace gives the identity compression for every observation. All parameters in the theorem statements are fixed before the input size grows. We write Mean p \operatorname{Mean}_p Mean p
Theorem 5.1 (Hardness for p < 1 p<1 p < 1 Fix the field, k ≥ 1 k\ge1 k ≥ 1 p < 1 p<1 p < 1 0 < ε < 1 − α k ( p ) 0<\varepsilon<1-\alpha_k(p) 0 < ε < 1 − α k ( p )
There is P ∈ St ( n , k ) P\in\operatorname{St}(n,k) P ∈ St ( n , k ) P ∗ A i P = I k P^*A_iP=I_k P ∗ A i P = I k i i i
Every P ∈ St ( n , k ) P\in\operatorname{St}(n,k) P ∈ St ( n , k )
Mean p [ ν A 1 ( P ) , … , ν A m ( P ) ] ≤ α k ( p ) + ε . \operatorname{Mean}_p\left[\nu_{A_1}(P),\ldots,\nu_{A_m}(P)\right]\le\alpha_k(p)+\varepsilon. Mean p [ ν A 1 ( P ) , … , ν A m ( P ) ] ≤ α k ( p ) + ε . The observations have rank at most k k k
The proof is in Appendix § 15 .§ 2 ; the rational encoding and positive definite perturbation are in Appendix § 15 .§ 4 . In particular, when p ≤ − k β p\le-k\beta p ≤ − k β
Theorem 5.2 (Hardness at p = 1 p=1 p = 1 Fix the field, k ≥ 2 k\ge2 k ≥ 2 0 < ε < 1 − α k ( 1 ) 0<\varepsilon<1-\alpha_k(1) 0 < ε < 1 − α k ( 1 )
There is P ∈ St ( n , k ) P \in\operatorname{St}(n,k) P ∈ St ( n , k ) P ∗ A i P = I k P^{*}A_iP = I_k P ∗ A i P = I k i i i
Every P ∈ St ( n , k ) P \in\operatorname{St}(n,k) P ∈ St ( n , k )
1 m ∑ i = 1 m v A i ( P ) ≤ α k ( 1 ) + ε . \frac{1}{m}\sum_{i=1}^{m} v_{A_i}(P) \le\alpha_k(1) + \varepsilon. m 1 i = 1 ∑ m v A i ( P ) ≤ α k ( 1 ) + ε . The observations have rank at most k k k
The proof is in Appendix C.3, with the same encoding and perturbation arguments in Appendix C.4. The excluded case k = 1 k = 1 k = 1 p = 1 p = 1 p = 1
Both proofs begin with the block-subspace promise of Briët, Regev, and Saket [12 ] , in the form given by Ebrahimnejad, Nagda, and Oveis Gharan [18 ] . Randomization over a finite family of rational unitary matrices makes coefficients spread among many coordinates obey a central limit comparison with Gaussian determinant moments. For p < 1 p < 1 p < 1 p = 1 p = 1 p = 1
The arithmetic reduction takes a fixed number d d d α k ( 1 ) \alpha_k(1) α k ( 1 ) d d d max { α k ( 1 ) , 1 / d } \max\{\alpha_k(1), 1/d\} max { α k ( 1 ) , 1/ d } 1 / d ≤ α k ( 1 ) 1/d \le\alpha_k(1) 1/ d ≤ α k ( 1 )
The reductions are deterministic and polynomial for each fixed ( p , k , ε ) (p,k,\varepsilon) ( p , k , ε ) P ≠ N P P \ne NP P = N P N P ≠ R P NP \ne RP N P = R P N P ≠ B P P NP \ne BPP N P = B P P
Hardness already holds for subspace observations
A rank-k k k
Lemma 5.3 (Projective normalization) Let A i ⪰ 0 A_i \succeq0 A i ⪰ 0 k k k Π i \Pi_i Π i d i : = e k ( A i ) 1 / k > 0 d_i := e_k(A_i)^{1/k} > 0 d i := e k ( A i ) 1/ k > 0 p ≠ 0 p \ne0 p = 0 S : = ∑ i w i d i p S := \sum_i w_i d_i^p S := ∑ i w i d i p w ~ i : = w i d i p / S \widetilde{w}_i := w_i d_i^p/S w i := w i d i p / S
Mean p , w [ v A i ( P ) ] = S 1 / p Mean p , w ~ [ v Π i ( P ) ] ( P ∈ St ( n , k ) ) . (11) \operatorname{Mean}_{p,w}[v_{A_i}(P)] = S^{1/p} \operatorname{Mean}_{p,\widetilde{w}}[v_{\Pi_i}(P)] \qquad(P \in\operatorname{St}(n,k)). \tag*{(11)} Mean p , w [ v A i ( P )] = S 1/ p Mean p , w [ v Π i ( P )] ( P ∈ St ( n , k )) . (11) At p = 0 p = 0 p = 0 ∏ i d i w i \prod_i d_i^{w_i} ∏ i d i w i p p p
The proof and the rational-weight estimate are in Section C.5. Perfect completeness lets the hardness reduction reject an instance containing a deficient-rank observation immediately. Otherwise all observations already have rank k k k
Theorem 5.4 (Hardness for subspace observations) Fix the field, k k k p ≤ 1 p \le1 p ≤ 1 ρ \rho ρ α k ( p ) < ρ < 1 \alpha_k(p) < \rho< 1 α k ( p ) < ρ < 1 ρ \rho ρ k k k p = 0 p = 0 p = 0 α k ( p ) = 0 \alpha_k(p) = 0 α k ( p ) = 0 p ≤ − k β p \le-k\beta p ≤ − k β
The proof is in Section C.5. This transfer concerns approximation ratios; its additional promise properties are discussed in Section C.5.
Exactness for two rank-k k k
For a rank-k k k A = U D U ∗ A = U D U^* A = U D U ∗ U ∈ St ( n , k ) U \in\operatorname{St}(n,k) U ∈ St ( n , k ) D ≻ 0 D \succ0 D ≻ 0 d : = det ( D ) 1 / k = e k ( A ) 1 / k d := \det(D)^{1/k} = e_k(A)^{1/k} d := det ( D ) 1/ k = e k ( A ) 1/ k
v A ( P ) = d ∣ det ( U ∗ P ) ∣ 2 / k , f A ( X ) = k d det ( U ∗ X U ) 1 / k . (12) v_A(P) = d \lvert\det(U^*P) \rvert^{2/k}, \qquad f_A(X) = k d \det(U^*XU)^{1/k}. \tag*{(12)} v A ( P ) = d ∣ det ( U ∗ P ) ∣ 2/ k , f A ( X ) = k d det ( U ∗ X U ) 1/ k . (12) Indeed, the nonzero eigenvalues of A 1 / 2 X A 1 / 2 A^{1/2} X A^{1/2} A 1/2 X A 1/2 D 1 / 2 U ∗ X U D 1 / 2 D^{1/2}U^*XUD^{1/2} D 1/2 U ∗ X U D 1/2 Y : = k X Y := kX Y := k X d det ( U ∗ Y U ) 1 / k d\det(U^*YU)^{1/k} d det ( U ∗ Y U ) 1/ k
Two-view purification
Theorem 6.1 (Two-view purification) Let U 1 , U 2 ∈ St ( n , k ) U_1,U_2 \in\operatorname{St}(n,k) U 1 , U 2 ∈ St ( n , k ) Y ⪰ 0 Y \succeq0 Y ⪰ 0 tr Y = k \operatorname{tr}Y=k tr Y = k P p u r ∈ St ( n , k ) P_{\mathrm{pur}} \in\operatorname{St}(n,k) P pur ∈ St ( n , k )
∣ det ( U i ∗ P p u r ) ∣ 2 ≥ det ( U i ∗ Y U i ) , i = 1 , 2. (13) \left|\det(U_i^*P_{\mathrm{pur}})\right|^2 \ge\det(U_i^*YU_i), \qquad i=1,2. \tag*{(13)} ∣ det ( U i ∗ P pur ) ∣ 2 ≥ det ( U i ∗ Y U i ) , i = 1 , 2. (13) The construction is deterministic and uses principal vectors and square roots of nonnegative scalars.
Proof. Changing the basis within either observation space leaves these determinants unchanged. The principal-angle decomposition [10 , 27 ] gives k k k E j E_j E j U 1 U_1 U 1 U 2 U_2 U 2
u j : = e j , v j : = cos ϕ j e j + sin ϕ j f j , 0 ≤ ϕ j ≤ π / 2. u_j := e_j,\qquad v_j := \cos\phi_j e_j+\sin\phi_j f_j,\qquad0\le\phi_j\le\pi/2. u j := e j , v j := cos ϕ j e j + sin ϕ j f j , 0 ≤ ϕ j ≤ π /2. where ϕ j \phi_j ϕ j j j j ϕ j = 0 \phi_j=0 ϕ j = 0 e j e_j e j e j , f j e_j,f_j e j , f j C j C_j C j Y Y Y E j E_j E j t j : = tr C j t_j := \operatorname{tr}C_j t j := tr C j ∑ j t j ≤ tr Y = k \sum_j t_j\le\operatorname{tr}Y=k ∑ j t j ≤ tr Y = k t j = 0 t_j=0 t j = 0 (13) vanish, so any frame suffices.
Otherwise, in a two-dimensional block take
w j : = ( C j ) 11 / t j e j + ( C j ) 22 / t j f j . w_j := \sqrt{(C_j)_{11}/t_j}\,e_j+\sqrt{(C_j)_{22}/t_j}\,f_j. w j := ( C j ) 11 / t j e j + ( C j ) 22 / t j f j . Positivity gives Re ( C j ) 12 ≤ ( C j ) 11 ( C j ) 22 \operatorname{Re}(C_j)_{12}\le\sqrt{(C_j)_{11}(C_j)_{22}} Re ( C j ) 12 ≤ ( C j ) 11 ( C j ) 22
∣ u j ∗ w j ∣ 2 = u j ∗ C j u j t j , ∣ v j ∗ w j ∣ 2 ≥ v j ∗ C j v j t j . \left|u_j^*w_j\right|^2=\frac{u_j^*C_ju_j}{t_j},\qquad
\left|v_j^*w_j\right|^2\ge\frac{v_j^*C_jv_j}{t_j}. u j ∗ w j 2 = t j u j ∗ C j u j , v j ∗ w j 2 ≥ t j v j ∗ C j v j . In a one-dimensional block take w j : = e j w_j:=e_j w j := e j w j w_j w j P p u r P_{\mathrm{pur}} P pur w j ∈ E j w_j\in E_j w j ∈ E j U 1 ∗ P p u r U_1^*P_{\mathrm{pur}} U 1 ∗ P pur U 2 ∗ P p u r U_2^*P_{\mathrm{pur}} U 2 ∗ P pur ( ∏ j t j ≤ 1 ) (\prod_j t_j\le1) ( ∏ j t j ≤ 1 )
det ( U 1 ∗ Y U 1 ) ≤ ∏ j u j ∗ C j u j ≤ ( ∏ j t j ) ∣ det ( U 1 ∗ P p u r ) ∣ 2 ≤ ∣ det ( U 1 ∗ P p u r ) ∣ 2 . \det(U_1^*YU_1)\le\prod_j u_j^*C_ju_j\le\left(\prod_j t_j\right)\left|\det(U_1^*P_{\mathrm{pur}})\right|^2\le\left|\det(U_1^*P_{\mathrm{pur}})\right|^2. det ( U 1 ∗ Y U 1 ) ≤ j ∏ u j ∗ C j u j ≤ ( j ∏ t j ) ∣ det ( U 1 ∗ P pur ) ∣ 2 ≤ ∣ det ( U 1 ∗ P pur ) ∣ 2 . The same argument applies to U 2 U_2 U 2 w j w_j w j e j e_j e j ϕ j \phi_j ϕ j w j w_j w j v j v_j v j [ 0 , ϕ j ] [0,\phi_j] [ 0 , ϕ j ] □ \square □
The argument covers common directions, orthogonal directions and vanishing compressed determinants, over either field. Exactness uses the rank-k k k
Exact objectives and efficient relative accuracy
Corollary 6.2 (Exactness for increasing aggregates). Let A 1 , A 2 ⪰ 0 A_1,A_2 \succeq0 A 1 , A 2 ⪰ 0 k k k U 1 , U 2 U_1,U_2 U 1 , U 2 d i : = e k ( A i ) 1 / k d_i := e_k(A_i)^{1/k} d i := e k ( A i ) 1/ k G : [ 0 , ∞ ) 2 → R G:[0,\infty)^2 \to\mathbb{R} G : [ 0 , ∞ ) 2 → R
sup P ∈ S t ( n , k ) G ( v A 1 ( P ) , v A 2 ( P ) ) = sup Y ⪰ 0 tr Y = k G ( d 1 det ( U 1 ∗ Y U 1 ) 1 / k , d 2 det ( U 2 ∗ Y U 2 ) 1 / k ) . (14) \sup_{P \in\mathrm{St}(n,k)} G(v_{A_1}(P),v_{A_2}(P))
=
\sup_{\substack{Y \succeq0\\ \operatorname{tr}Y=k}} G\left(d_1\det(U_1^*YU_1)^{1/k},d_2\det(U_2^*YU_2)^{1/k}\right). \tag*{(14)} P ∈ St ( n , k ) sup G ( v A 1 ( P ) , v A 2 ( P )) = Y ⪰ 0 tr Y = k sup G ( d 1 det ( U 1 ∗ Y U 1 ) 1/ k , d 2 det ( U 2 ∗ Y U 2 ) 1/ k ) . (14) If G G G G = Mean p , w G=\operatorname{Mean}_{p,w} G = Mean p , w p ≤ 1 p\leq1 p ≤ 1 ( 1 − ε ) OPT p , k (1-\varepsilon)\operatorname{OPT}_{p,k} ( 1 − ε ) OPT p , k 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 p p p log ( 1 / ε ) \log(1/\varepsilon) log ( 1/ ε )
The proof is in Section D.1, with the complete numerical argument in Section D.2.
Identity (6.3) uses only monotonicity of the aggregate; concavity is needed for the algorithm. The algorithm has no negative-moment restriction.
Martin means of subspaces
For observed frames U i ∈ S t ( n , k ) U_i \in\mathrm{St}(n,k) U i ∈ St ( n , k )
L ( P ) : = − ∑ i w i log ∣ det ( U i ∗ P ) ∣ 2 , P ∈ S t ( n , k ) . (15) \mathcal{L}(P):=-\sum_i w_i\log\left|\det(U_i^*P)\right|^2,\qquad P\in\mathrm{St}(n,k). \tag*{(15)} L ( P ) := − i ∑ w i log ∣ det ( U i ∗ P ) ∣ 2 , P ∈ St ( n , k ) . (15) The squared determinant is the product of the squared cosines of the principal angles between the two subspaces. A zero positive-weight overlap gives infinite loss. This is the finite-dimensional squared-Martin objective used in [60 ] , with origins in stochastic systems [16 , 36 ] . We optimize over the whole Grassmannian, without ARMA realization constraints.
Writing Π i : = U i U i ∗ \Pi_i:=U_iU_i^* Π i := U i U i ∗ L ( P ) = − k log Mean 0 , w [ v Π i ( P ) ] \mathcal{L}(P)=-k\log\operatorname{Mean}_{0,w}[v_{\Pi_i}(P)] L ( P ) = − k log Mean 0 , w [ v Π i ( P )]
Additive approximation
Projection observations permit a useful dimension reduction. If V i V_i V i Q Q Q U i U_i U i P P P
∣ det ( U i ∗ P ) ∣ 2 = ∣ det ( V i ∗ Q ) ∣ 2 . (16) \left|\det(U_i^*P)\right|^2=\left|\det(V_i^*Q)\right|^2. \tag*{(16)} ∣ det ( U i ∗ P ) ∣ 2 = ∣ det ( V i ∗ Q ) ∣ 2 . (16) For a unitary matrix, a minor and its complementary minor have equal modulus, by Jacobi’s identity [28 ] . Applying this to [ U i V i ] ∗ [ P Q ] [U_i\ V_i]^*[P\ Q] [ U i V i ] ∗ [ P Q ] s : = min ( k , n − k ) s := \min(k, n-k) s := min ( k , n − k )
Theorem 7.1 (Dimension-free Martin approximation). Let 1 ≤ k < n 1 \le k < n 1 ≤ k < n s : = min ( k , n − k ) s := \min(k, n-k) s := min ( k , n − k )
For rationally encoded observations and positive rational weights, a randomized polynomial-time algorithm returns, with probability at least 2 / 3 2/3 2/3
L ( P ) ≤ min R L ( R ) + Δ s , Δ s : = − s log α s ( 0 ) = s log ( s β ) − ∑ j = 1 s ψ ( j β ) . (17) \mathcal{L}(\mathrm{P}) \le\min_R \mathcal{L}(R) + \Delta_s,\qquad\Delta_s := -s \log\alpha_s(0) = s\log(s\beta) - \sum_{j=1}^{s} \psi(j\beta). \tag*{(17)} L ( P ) ≤ R min L ( R ) + Δ s , Δ s := − s log α s ( 0 ) = s log ( s β ) − j = 1 ∑ s ψ ( j β ) . (17) For fixed k k k 0 < ε < Δ k 0 < \varepsilon< \Delta_k 0 < ε < Δ k Δ k − ε \Delta_k - \varepsilon Δ k − ε
For rationally encoded observations, positive rational weights, and rational ε > 0 \varepsilon> 0 ε > 0
L ( P ) ≤ min R L ( R ) + Δ s , n + ε , (18) \mathcal{L}(\mathrm{P}) \le\min_R \mathcal{L}(R) + \Delta_{s,n} + \varepsilon, \tag*{(18)} L ( P ) ≤ R min L ( R ) + Δ s , n + ε , (18) where
Δ s , n : = − s log α n , s ( 0 ) = s log ( s / n ) + ∑ j = 1 s [ ψ ( ( n − j + 1 ) β ) − ψ ( j β ) ] . (19) \Delta_{s,n} := -s \log\alpha_{n,s}(0) = s\log(s/n) + \sum_{j=1}^{s} [\psi((n-j+1)\beta) - \psi(j\beta)]. \tag*{(19)} Δ s , n := − s log α n , s ( 0 ) = s log ( s / n ) + j = 1 ∑ s [ ψ (( n − j + 1 ) β ) − ψ ( j β )] . (19) Its time is polynomial in the input bit length and max ( 1 , 1 / ε ) \max(1, 1/\varepsilon) max ( 1 , 1/ ε ) 2 / 3 2/3 2/3
The proof is in Section D.3. The finite-dimensional statement is a guarantee of the Gaussian-rounding algorithm in the smaller projection dimension. The hardness assertion concerns improving Δ k \Delta_k Δ k k k k
An explicit two-view mean
Use the principal vectors u j u_j u j v j v_j v j E j E_j E j Theorem 6.1 .
Proposition 7.2 (Two-view Martin mean). For two observations with principal angles ϕ j ∈ [ 0 , π / 2 ] \phi_j \in[0,\pi/2] ϕ j ∈ [ 0 , π /2 ] w , 1 − w w,1-w w , 1 − w e j e_j e j cos θ j e j + sin θ j f j \cos\theta_j e_j + \sin\theta_j f_j cos θ j e j + sin θ j f j 0 < ϕ j < π / 2 0 < \phi_j < \pi/2 0 < ϕ j < π /2
tan θ j = 2 ( 1 − w ) tan ϕ j 1 + 1 + 4 w ( 1 − w ) tan 2 ϕ j . (20) \tan\theta_j = \frac{2(1-w)\tan\phi_j}{1+\sqrt{1+4w(1-w)\tan^2\phi_j}}. \tag*{(20)} tan θ j = 1 + 1 + 4 w ( 1 − w ) tan 2 ϕ j 2 ( 1 − w ) tan ϕ j . (20) At ϕ j = 0 \phi_j = 0 ϕ j = 0 θ j = 0 \theta_j = 0 θ j = 0 ϕ j = π / 2 \phi_j = \pi/2 ϕ j = π /2 cos 2 θ j = w \cos^2\theta_j = w cos 2 θ j = w
The proof in Section D.4 uses two-view purification to restrict to principal blocks and then maximizes one strictly concave logarithmic function in each block. Thus the same relaxation supports sharp general approximation and an explicit global solution in the two-view case.
Statements and declarations
Funding. The author received no funding for this work.
Competing interests. The author declares no competing interests.
Data availability. No empirical datasets were used or generated. All approximation factors are specified by exact formulas in the article.
AI acknowledgement. AI language models, including GPT-6 and Claude Opus, were used as supporting tools throughout the research, writing and editing process. The author retains full responsibility for the final content and conclusions.
Gaussian determinant rounding
We prove Theorem 4.1 and the ordinary-sampling estimates used by the algorithms. All Gaussian normalizations are those of Section 2.
Numerator and Gram determinant moments
For a square standard Gaussian matrix H ∈ F k × k H \in\mathbb{F}^{k \times k} H ∈ F k × k
D k , β ( u ) : = E ∣ det H ∣ 2 u = β − k u ∏ j = 1 k Γ ( j β + u ) Γ ( j β ) , u > − β . (21) D_{k,\beta}(u) := \mathbb{E}|\det H|^{2u} = \beta^{-ku} \prod_{j=1}^{k} \frac{\Gamma(j\beta+u)}{\Gamma(j\beta)}, \qquad u > -\beta. \tag*{(21)} D k , β ( u ) := E ∣ det H ∣ 2 u = β − k u j = 1 ∏ k Γ ( j β ) Γ ( j β + u ) , u > − β . (21) For Z ∈ F r × k Z \in\mathbb{F}^{r \times k} Z ∈ F r × k r ≥ k r \ge k r ≥ k u > − ( r − k + 1 ) β u > -(r-k+1)\beta u > − ( r − k + 1 ) β
R r , k , β ( u ) : = E det ( Z ∗ Z / r ) u = ( r β ) − k u ∏ j = 1 k Γ ( ( r − j + 1 ) β + u ) Γ ( ( r − j + 1 ) β ) . (22) R_{r,k,\beta}(u) := \mathbb{E}\det(Z^{*}Z/r)^u = (r\beta)^{-ku} \prod_{j=1}^{k} \frac{\Gamma((r-j+1)\beta+u)}{\Gamma((r-j+1)\beta)}. \tag*{(22)} R r , k , β ( u ) := E det ( Z ∗ Z / r ) u = ( r β ) − k u j = 1 ∏ k Γ (( r − j + 1 ) β ) Γ (( r − j + 1 ) β + u ) . (22) These are Bartlett’s real and complex Gram determinant formulas [20 , 23 ] . Each Gram determinant is a product of independent Gamma variables, with shape parameters ( r − j + 1 ) β (r-j+1)\beta ( r − j + 1 ) β β \beta β
Lemma A.1 Let A , X ⪰ 0 A, X \succeq0 A , X ⪰ 0 G : = X 1 / 2 Z G := X^{1/2}Z G := X 1/2 Z
C A ( X ) : = e k ( A 1 / 2 X A 1 / 2 ) > 0. C_A(X) := e_k(A^{1/2}XA^{1/2}) > 0. C A ( X ) := e k ( A 1/2 X A 1/2 ) > 0. Then
E det ( G ∗ A G ) u { ≥ D k , β ( u ) C A ( X ) u , 0 < u ≤ 1 , ≤ D k , β ( u ) C A ( X ) u , − β < u < 0. (23) \mathbb{E}\det(G^{*}AG)^u
\begin{cases}
\ge D_{k,\beta}(u)C_A(X)^u, & 0 < u \le1,\\
\le D_{k,\beta}(u)C_A(X)^u, & -\beta< u < 0.
\end{cases} \tag*{(23)} E det ( G ∗ A G ) u { ≥ D k , β ( u ) C A ( X ) u , ≤ D k , β ( u ) C A ( X ) u , 0 < u ≤ 1 , − β < u < 0. (23) Moreover,
E log det ( G ∗ A G ) ≥ log C A ( X ) + ∑ j = 1 k ψ ( j β ) − k log β . (24) \mathbb{E}\log\det(G^{*}AG) \ge\log C_A(X) + \sum_{j=1}^{k}\psi(j\beta) - k\log\beta. \tag*{(24)} E log det ( G ∗ A G ) ≥ log C A ( X ) + j = 1 ∑ k ψ ( j β ) − k log β . (24) Proof. For each k k k I I I B I B_I B I A 1 / 2 A^{1/2} A 1/2
det ( G ∗ A G ) = ∑ ∣ I ∣ = k ∣ det ( B I G ) ∣ 2 , C A ( X ) = ∑ ∣ I ∣ = k det ( B I X B I ∗ ) . \det(G^*AG)=\sum_{|I|=k}\left|\det(B_IG)\right|^2,\qquad C_A(X)=\sum_{|I|=k}\det(B_IXB_I^*). det ( G ∗ A G ) = ∣ I ∣ = k ∑ ∣ det ( B I G ) ∣ 2 , C A ( X ) = ∣ I ∣ = k ∑ det ( B I X B I ∗ ) . If c I : = det ( B I X B I ∗ ) > 0 c_I:=\det(B_IXB_I^*)>0 c I := det ( B I X B I ∗ ) > 0 ∣ det ( B I G ) ∣ 2 / c I \left|\det(B_IG)\right|^2/c_I ∣ det ( B I G ) ∣ 2 / c I c I = 0 c_I=0 c I = 0
det ( G ∗ A G ) = C A ( X ) ∑ I θ I D I , θ I : = c I / C A ( X ) , ∑ I θ I = 1 , \det(G^*AG)=C_A(X)\sum_I\theta_ID_I,\qquad\theta_I:=c_I/C_A(X),\qquad\sum_I\theta_I=1, det ( G ∗ A G ) = C A ( X ) I ∑ θ I D I , θ I := c I / C A ( X ) , I ∑ θ I = 1 , where every retained D I D_I D I ∣ det H ∣ 2 |\det H|^2 ∣ det H ∣ 2 □ \square □
Lemma A.2. If X ≻ 0 X\succ0 X ≻ 0 r × r r\times r r × r tr X = 1 \operatorname{tr}X=1 tr X = 1 u : = p / k u:=p/k u := p / k
E det ( Z ∗ X Z ) u { ≤ R r , k , β ( u ) , 0 < p ≤ 1 , ≥ R r , k , β ( u ) , − k β < p < 0. (25) \mathbb{E}\det(Z^*XZ)^u
\begin{cases}
\le R_{r,k,\beta}(u), & 0<p\le1,\\
\ge R_{r,k,\beta}(u), & -k\beta<p<0.
\end{cases} \tag*{(25)} E det ( Z ∗ X Z ) u { ≤ R r , k , β ( u ) , ≥ R r , k , β ( u ) , 0 < p ≤ 1 , − k β < p < 0. (25) Also,
E log det ( Z ∗ X Z ) ≤ − k log ( r β ) + ∑ j = 1 k ψ ( ( r − j + 1 ) β ) . \mathbb{E}\log\det(Z^*XZ)\le-k\log(r\beta)+\sum_{j=1}^{k}\psi((r-j+1)\beta). E log det ( Z ∗ X Z ) ≤ − k log ( r β ) + j = 1 ∑ k ψ (( r − j + 1 ) β ) . Proof. For fixed Z Z Z X X X 0 < p ≤ 1 0<p\le1 0 < p ≤ 1 p < 0 p<0 p < 0 ( p / k ) log det ( Z ∗ X Z ) (p/k)\log\det(Z^*XZ) ( p / k ) log det ( Z ∗ X Z ) X X X I r / r I_r/r I r / r X X X X ≻ 0 X\succ0 X ≻ 0 u > − β u>-\beta u > − β □ \square □
Proof of the rounding theorem
Proof (of Theorem 4.1). Write C i : = C A i ( X ) C_i:=C_{A_i}(X) C i := C A i ( X ) p ≤ 0 p\le0 p ≤ 0 C i = 0 C_i=0 C i = 0 p > 0 p>0 p > 0 C i > 0 C_i>0 C i > 0 X X X G : = X 1 / 2 Z G:=X^{1/2}Z G := X 1/2 Z P : = G ( G ∗ G ) − 1 / 2 P:=G(G^*G)^{-1/2} P := G ( G ∗ G ) − 1/2 N i ( G ) : = det ( G ∗ A i G ) N_i(G):=\det(G^*A_iG) N i ( G ) := det ( G ∗ A i G )
v A i ( P ) k = N i ( G ) det ( G ∗ G ) . (26) v_{A_i}(P)^k=\frac{N_i(G)}{\det(G^*G)}. \tag*{(26)} v A i ( P ) k = det ( G ∗ G ) N i ( G ) . (26) For p ≠ 0 p\ne0 p = 0 u : = p / k u:=p/k u := p / k
ω ( Z ) : = det ( Z ∗ X Z ) u E det ( Z ∗ X Z ) u (27) \omega(Z):=\frac{\det(Z^*XZ)^u}{\mathbb{E}\det(Z^*XZ)^u} \tag*{(27)} ω ( Z ) := E det ( Z ∗ X Z ) u det ( Z ∗ X Z ) u (27) relative to the ordinary Gaussian law. Under the resulting law ν \nu ν
E ν ∑ i w i v A i ( P ) p = ∑ i w i E N i ( G ) u E det ( Z ∗ X Z ) u . \mathbb{E}_{\nu}\sum_i w_i v_{A_i}(P)^p
=\frac{\sum_iw_i\mathbb{E}N_i(G)^u}{\mathbb{E}\det(Z^*XZ)^u}. E ν i ∑ w i v A i ( P ) p = E det ( Z ∗ X Z ) u ∑ i w i E N i ( G ) u . The two lemmas bound this expression below for p > 0 p>0 p > 0 p < 0 p<0 p < 0
D k , β ( u ) R r , k , β ( u ) ∑ i w i C i u . \frac{D_{k,\beta}(u)}{R_{r,k,\beta}(u)}\sum_i w_i C_i^u. R r , k , β ( u ) D k , β ( u ) i ∑ w i C i u . There is therefore a realization of Z Z Z 1 / p 1/p 1/ p p < 0 p<0 p < 0 f A i ( X ) = k C i 1 / k f_{A_i}(X)=kC_i^{1/k} f A i ( X ) = k C i 1/ k
For p > 0 p>0 p > 0 Z ∗ Z / r Z^*Z/r Z ∗ Z / r R r , k , β ( p / k ) ≤ 1 R_{r,k,\beta}(p/k)\leq1 R r , k , β ( p / k ) ≤ 1 p < 0 p<0 p < 0 α r , k ( p ) ≥ α k ( p ) \alpha_{r,k}(p)\geq\alpha_k(p) α r , k ( p ) ≥ α k ( p ) A = I r A=I_r A = I r X = I r / r X=I_r/r X = I r / r f I r ( I r / r ) = ( k / r ) 1 / k ( r k ) 1 / k f_{I_r}(I_r/r)=(k/r)^{1/k}\binom{r}{k}^{1/k} f I r ( I r / r ) = ( k / r ) 1/ k ( k r ) 1/ k
α k ( p ) ≤ α r , k ( p ) ≤ r k ( r k ) 1 / k ≤ 1. (28) \alpha_k(p)\leq\alpha_{r,k}(p)\leq\frac{r}{k\binom{r}{k}^{1/k}}\leq1. \tag*{(28)} α k ( p ) ≤ α r , k ( p ) ≤ k ( k r ) 1/ k r ≤ 1. (28) The last inequality follows by multiplying ( r − j ) / ( k − j ) ≥ r / k (r-j)/(k-j)\geq r/k ( r − j ) / ( k − j ) ≥ r / k 0 ≤ j < k 0\leq j<k 0 ≤ j < k X = P Λ P ∗ X=P\Lambda P^* X = P Λ P ∗ k k k
f A i ( X ) = k det ( Λ ) 1 / k v A i ( P ) ≤ v A i ( P ) , f_{A_i}(X)=k\det(\Lambda)^{1/k}v_{A_i}(P)\leq v_{A_i}(P), f A i ( X ) = k det ( Λ ) 1/ k v A i ( P ) ≤ v A i ( P ) , because tr Λ = 1 \operatorname{tr}\Lambda=1 tr Λ = 1
We now convert guarantees under the tilted law into guarantees for ordinary Gaussian samples. If ν ( E ) ≥ ρ \nu(E)\geq\rho ν ( E ) ≥ ρ E ω a ≤ C \mathbb{E}\omega^a\leq C E ω a ≤ C
Pr ( E ) ≥ ρ a / ( a − 1 ) C − 1 / ( a − 1 ) . (29) \Pr(E)\geq\rho^{a/(a-1)}C^{-1/(a-1)}. \tag*{(29)} Pr ( E ) ≥ ρ a / ( a − 1 ) C − 1/ ( a − 1 ) . (29) We now bound these density moments uniformly in the covariance.
Let D D D μ : = E D = k ! \mu:=\mathbb{E}D=k! μ := E D = k ! det ( Z ∗ X Z ) = e k ( X ) H X \det(Z^*XZ)=e_k(X)H_X det ( Z ∗ X Z ) = e k ( X ) H X H X H_X H X D D D E H X = μ \mathbb{E}H_X=\mu E H X = μ
D k ! = l a w ∏ j = 1 k Q j , Q j : = γ j j β , γ j ∼ Gamma ( j β , rate 1 ) \frac{D}{k!}\overset{\mathrm{law}}{=}\prod_{j=1}^k Q_j,\qquad Q_j:=\frac{\gamma_j}{j\beta},\qquad\gamma_j\sim\operatorname{Gamma}(j\beta,\text{ rate }1) k ! D = law j = 1 ∏ k Q j , Q j := j β γ j , γ j ∼ Gamma ( j β , rate 1 ) with independent factors. Thus Q j Q_j Q j j β j\beta j β γ j \gamma_j γ j
T ( t , k ) : = E D t / k ( k ! ) t / k = ∏ j = 1 k E Q j t / k . (30) T(t,k):=\frac{\mathbb{E}D^{t/k}}{(k!)^{t/k}}=\prod_{j=1}^k\mathbb{E}Q_j^{t/k}. \tag*{(30)} T ( t , k ) := ( k ! ) t / k E D t / k = j = 1 ∏ k E Q j t / k . (30) Lemma A.3 (Covariance-uniform density bounds) Fix 0 < δ < 1 0<\delta<1 0 < δ < 1 c = c δ , β > 0 c=c_{\delta,\beta}>0 c = c δ , β > 0 C = C δ , β ≥ 1 C=C_{\delta,\beta}\geq1 C = C δ , β ≥ 1 δ \delta δ r ≥ k ≥ 1 r\geq k\geq1 r ≥ k ≥ 1 − ( 1 − δ ) k β ≤ p ≤ 1 -(1-\delta)k\beta\leq p\leq1 − ( 1 − δ ) k β ≤ p ≤ 1
c ≤ α k ( p ) ≤ α r , k ( p ) ≤ 1. c\leq\alpha_k(p)\leq\alpha_{r,k}(p)\leq1. c ≤ α k ( p ) ≤ α r , k ( p ) ≤ 1. The lower constant c c c
E ω 2 ≤ 3 c − 2 , p > 0 , (31) \mathbb{E}\omega^2\leq3c^{-2},\qquad p>0, \tag*{(31)} E ω 2 ≤ 3 c − 2 , p > 0 , (31) E ω 1 + δ / 2 ≤ C k , p < 0. (32) \mathbb{E}\omega^{1+\delta/2}\leq Ck,\qquad p<0. \tag*{(32)} E ω 1 + δ /2 ≤ C k , p < 0. (32) Proof. Each Q j Q_j Q j j j j Q 1 Q_1 Q 1 u < 0 u<0 u < 0 E Q j u ≤ E Q 1 u \mathbb{E}Q_j^u\leq\mathbb{E}Q_1^u E Q j u ≤ E Q 1 u p p p
α k ( p ) = ( k ! ) 1 / k k T ( p , k ) 1 / p ≥ e − 1 Mean p / k [ Q 1 ] ≥ e − 1 Mean − ( 1 − δ ) β [ Q 1 ] > 0. \alpha_k(p)=\frac{(k!)^{1/k}}{k}T(p,k)^{1/p}\geq e^{-1}\operatorname{Mean}_{p/k}[Q_1]\geq e^{-1}\operatorname{Mean}_{-(1-\delta)\beta}[Q_1]>0. α k ( p ) = k ( k ! ) 1/ k T ( p , k ) 1/ p ≥ e − 1 Mean p / k [ Q 1 ] ≥ e − 1 Mean − ( 1 − δ ) β [ Q 1 ] > 0. Here ( k ! ) 1 / k / k ≥ e − 1 (k!)^{1/k}/k\geq e^{-1} ( k ! ) 1/ k / k ≥ e − 1 log ( k ! ) ≥ ∫ 1 k log x d x = k log k − k + 1 \log(k!)\geq\int_1^k\log x\,\mathrm{d}x=k\log k-k+1 log ( k !) ≥ ∫ 1 k log x d x = k log k − k + 1 p ≥ 0 p\geq0 p ≥ 0 c c c
For negative p p p a : = 1 + δ / 2 a:=1+\delta/2 a := 1 + δ /2 v : = − a p / k v:=-ap/k v := − a p / k v ∗ : = ( 1 − δ / 2 ) β v_*:=(1-\delta/2)\beta v ∗ := ( 1 − δ /2 ) β 0 < v ≤ v ∗ < β ≤ 1 0<v\leq v_*<\beta\leq1 0 < v ≤ v ∗ < β ≤ 1 E H X p / k ≥ μ p / k \mathbb{E}H_X^{p/k}\geq\mu^{p/k} E H X p / k ≥ μ p / k
E w a ≤ T ( a p , k ) = ∏ j = 1 k E Q j − v . \mathbb{E}w^a\leq T(ap,k)=\prod_{j=1}^{k}\mathbb{E}Q_j^{-v}. E w a ≤ T ( a p , k ) = j = 1 ∏ k E Q j − v . For j β > 1 j\beta>1 j β > 1 v v v
E Q j − v ≤ ( E Q j − 1 ) v = ( j β j β − 1 ) v . \mathbb{E}Q_j^{-v}\leq\left(\mathbb{E}Q_j^{-1}\right)^v=\left(\frac{j\beta}{j\beta-1}\right)^v. E Q j − v ≤ ( E Q j − 1 ) v = ( j β − 1 j β ) v . Write j 0 : = 1 / β ∈ { 1 , 2 } j_0:=1/\beta\in\{1,2\} j 0 := 1/ β ∈ { 1 , 2 } k ≥ j 0 k\geq j_0 k ≥ j 0 j = j 0 + 1 , … , k j=j_0+1,\ldots,k j = j 0 + 1 , … , k ( k j 0 ) ≤ k j 0 \binom{k}{j_0}\leq k^{j_0} ( j 0 k ) ≤ k j 0 E Q j − v ≤ E Q j 0 − v ∗ \mathbb{E}Q_j^{-v}\leq\mathbb{E}Q_{j_0}^{-v_*} E Q j − v ≤ E Q j 0 − v ∗
C : = ∏ j = 1 j 0 E Q j − v ∗ , C:=\prod_{j=1}^{j_0}\mathbb{E}Q_j^{-v_*}, C := j = 1 ∏ j 0 E Q j − v ∗ , the product is at most C k j 0 v ≤ C k Ck^{j_0v}\leq Ck C k j 0 v ≤ C k k < j 0 k<j_0 k < j 0
For positive p p p u : = p / k u:=p/k u := p / k 2 u ≤ 1 2u\leq1 2 u ≤ 1
E w 2 ≤ μ 2 u ( E D u ) 2 = T ( p , k ) − 2 ≤ c − 2 . \mathbb{E}w^2\leq\frac{\mu^{2u}}{(\mathbb{E}D^u)^2}=T(p,k)^{-2}\leq c^{-2}. E w 2 ≤ ( E D u ) 2 μ 2 u = T ( p , k ) − 2 ≤ c − 2 . Indeed α k ( p ) = [ ( k ! ) 1 / k / k ] T ( p , k ) 1 / p \alpha_k(p)=[(k!)^{1/k}/k]T(p,k)^{1/p} α k ( p ) = [( k ! ) 1/ k / k ] T ( p , k ) 1/ p T ( p , k ) ≥ c p ≥ c T(p,k)\geq c^p\geq c T ( p , k ) ≥ c p ≥ c k = 1 k=1 k = 1 1 / 2 < p ≤ 1 1/2<p\leq1 1/2 < p ≤ 1 E H X 2 p ≤ E D 2 p ≤ ( E D 2 ) 2 p − 1 ≤ 3 \mathbb{E}H_X^{2p}\leq\mathbb{E}D^{2p}\leq(\mathbb{E}D^2)^{2p-1}\leq3 E H X 2 p ≤ E D 2 p ≤ ( E D 2 ) 2 p − 1 ≤ 3 E H X p ≥ E D p ≥ c \mathbb{E}H_X^p\geq\mathbb{E}D^p\geq c E H X p ≥ E D p ≥ c □ \square □
Success probability, including powers near zero
Assume all relaxed scores f A i ( X ) f_{A_i}(X) f A i ( X ) X X X S ⋆ > 0 S^\star>0 S ⋆ > 0
Y : = Mean p , w [ v A i ( P ) ] S ⋆ , b : = α r , k ( p ) , L : = − log b . Y:=\frac{\operatorname{Mean}_{p,w}[v_{A_i}(P)]}{S^\star},\qquad b:=\alpha_{r,k}(p),\qquad L:=-\log b. Y := S ⋆ Mean p , w [ v A i ( P )] , b := α r , k ( p ) , L := − log b . Exactness at subspaces gives 0 ≤ Y ≤ 1 0\leq Y\leq1 0 ≤ Y ≤ 1 E ν Y p ≥ b p \mathbb{E}_\nu Y^p\geq b^p E ν Y p ≥ b p p > 0 p>0 p > 0 E ν Y p ≤ b p \mathbb{E}_\nu Y^p\leq b^p E ν Y p ≤ b p p < 0 p<0 p < 0 E log Y ≥ log b \mathbb{E}\log Y\geq\log b E log Y ≥ log b s > 0 s>0 s > 0 E : = { Y ≥ b e − s } E:=\{Y\geq be^{-s}\} E := { Y ≥ b e − s } Y Y Y E E E
ν ( E ) ≥ { e p s − 1 e p ( L + s ) − 1 ≥ s L + s , p > 0 , 1 − e − ∣ p ∣ s 1 − e − ∣ p ∣ ( L + s ) ≥ s L + s , p < 0 , s L + s , p = 0. (33) \nu(E)\geq
\begin{cases}
\dfrac{e^{ps}-1}{e^{p(L+s)}-1}\geq\dfrac{s}{L+s}, & p>0,\\[6pt]
\dfrac{1-e^{-|p|s}}{1-e^{-|p|(L+s)}}\geq\dfrac{s}{L+s}, & p<0,\\[6pt]
\dfrac{s}{L+s}, & p=0.
\end{cases} \tag*{(33)} ν ( E ) ≥ ⎩ ⎨ ⎧ e p ( L + s ) − 1 e p s − 1 ≥ L + s s , 1 − e − ∣ p ∣ ( L + s ) 1 − e − ∣ p ∣ s ≥ L + s s , L + s s , p > 0 , p < 0 , p = 0. (33) At zero, ν \nu ν 0 < p ≤ 1 0 < p \le1 0 < p ≤ 1 ( 1 − e − x ) / x (1-e^{-x})/x ( 1 − e − x ) / x p p p
By Lemma A.3, 0 ≤ L ≤ − log c 0 \le L \le-\log c 0 ≤ L ≤ − log c s : = − log ( 1 − ε ) s := -\log(1-\varepsilon) s := − log ( 1 − ε ) 0 < ε ≤ 1 / 2 0 < \varepsilon\le1/2 0 < ε ≤ 1/2 c ′ ε c'\varepsilon c ′ ε c ′ > 0 c' > 0 c ′ > 0
Pr { Y ≥ ( 1 − ε ) b } ≥ ( c ′ ε ) 1 + 2 / δ ( C k ) − 2 / δ . (34) \Pr\{Y \ge(1-\varepsilon)b\} \ge(c'\varepsilon)^{1+2/\delta}(Ck)^{-2/\delta}. \tag*{(34)} Pr { Y ≥ ( 1 − ε ) b } ≥ ( c ′ ε ) 1 + 2/ δ ( C k ) − 2/ δ . (34) For positive powers the lower bound is ( c ′ ε ) 2 c 2 / 3 (c'\varepsilon)^2c^2/3 ( c ′ ε ) 2 c 2 /3 c ′ ε c'\varepsilon c ′ ε k k k
Algorithms and numerical precision
We prove Theorems 4.2 and 3.2. All polynomial bounds may depend on the field and the fixed margin δ \delta δ [24 ] .
Zero scores and a positive optimization scale
If rank A i < k \operatorname{rank} A_i < k rank A i < k p ≤ 0 p \le0 p ≤ 0 p > 0 p > 0 p > 0 W > 0 W > 0 W > 0 W 1 / p W^{1/p} W 1/ p W = 0 W = 0 W = 0 W 1 / p W^{1/p} W 1/ p p p p
Assume henceforth that every retained A i A_i A i k k k k < n k < n k < n F ( X ) : = Mean p , w [ f A i ( X ) ] F(X) := \operatorname{Mean}_{p,w}[f_{A_i}(X)] F ( X ) := Mean p , w [ f A i ( X )]
T n θ : = { X ⪰ ( θ / n ) I : tr X = 1 } , 0 < θ ≤ 1 / 4. \mathcal{T}_n^\theta:= \{X \succeq(\theta/n)I : \operatorname{tr} X = 1\}, \qquad0 < \theta\le1/4. T n θ := { X ⪰ ( θ / n ) I : tr X = 1 } , 0 < θ ≤ 1/4. For any X ∈ T n X \in\mathcal{T}_n X ∈ T n X θ : = ( 1 − θ ) X + θ I / n X_\theta:= (1-\theta)X + \theta I/n X θ := ( 1 − θ ) X + θ I / n T n θ \mathcal{T}_n^\theta T n θ F ( X θ ) ≥ ( 1 − θ ) F ( X ) F(X_\theta) \ge(1-\theta)F(X) F ( X θ ) ≥ ( 1 − θ ) F ( X ) X ∈ T n θ X \in\mathcal{T}_n^\theta X ∈ T n θ
e k ( A i 1 / 2 X A i 1 / 2 ) ≥ ( θ / n ) k e k ( A i ) > 0. (35) e_k(A_i^{1/2}X A_i^{1/2}) \ge(\theta/n)^k e_k(A_i) > 0. \tag*{(35)} e k ( A i 1/2 X A i 1/2 ) ≥ ( θ / n ) k e k ( A i ) > 0. (35) A positive rational principal minor gives a polynomial-bit lower bound for e k ( A i ) e_k(A_i) e k ( A i ) log ( 1 / θ ) \log(1/\theta) log ( 1/ θ ) S 0 : = F ( I / n ) > 0 S_0 := F(I/n) > 0 S 0 := F ( I / n ) > 0
Lemma B.1 (Logarithmic stability and derivative bounds) For every finite real p p p a , b a,b a , b
∣ log Mean p , w [ a ] − log Mean p , w [ b ] ∣ ≤ ∥ log a − log b ∥ ∞ . (36) \left|\log\operatorname{Mean}_{p,w}[a]-\log\operatorname{Mean}_{p,w}[b]\right| \le\lVert\log a-\log b\rVert_\infty. \tag*{(36)} ∣ log Mean p , w [ a ] − log Mean p , w [ b ] ∣ ≤ ∥ log a − log b ∥ ∞ . (36) If a differentiable function F F F ρ > 0 \rho> 0 ρ > 0 X ⪰ a I X \succeq aI X ⪰ a I
∇ F ( X ) ⪰ 0 , tr ∇ F ( X ) ≤ ρ F ( X ) a . (37) \nabla F(X) \succeq0, \qquad\operatorname{tr}\nabla F(X) \le\frac{\rho F(X)}{a}. \tag*{(37)} ∇ F ( X ) ⪰ 0 , tr ∇ F ( X ) ≤ a ρF ( X ) . (37) Proof. The derivative of log Mean p , w \log\operatorname{Mean}_{p,w} log Mean p , w log a i \log a_i log a i w i a i p / ∑ j w j a j p w_i a_i^p/\sum_j w_j a_j^p w i a i p / ∑ j w j a j p p ≠ 0 p \ne0 p = 0 w i w_i w i tr ( X ∇ F ) = ρ F \operatorname{tr}(X\nabla F)=\rho F tr ( X ∇ F ) = ρF
Our objective has degree one. The lemma bounds its first derivatives using the spectral floor and objective bounds, independently of the magnitude of the power. The needed coefficient e k ( A i 1 / 2 X A i 1 / 2 ) = [ t k ] det ( I + t X A i ) e_k(A_i^{1/2}XA_i^{1/2}) = [t^k]\det(I+tXA_i) e k ( A i 1/2 X A i 1/2 ) = [ t k ] det ( I + tX A i ) [ t k ] [t^k] [ t k ] t k t^k t k n + 1 n+1 n + 1
d d h det ( I + t ( X + h H ) A i ) ∣ h = 0 = t tr ( adj ( I + t X A i ) H A i ) . \left.\frac{d}{dh}\det(I+t(X+hH)A_i)\right|_{h=0}
= t\operatorname{tr}\left(\operatorname{adj}(I+tXA_i)HA_i\right). d h d det ( I + t ( X + h H ) A i ) h = 0 = t tr ( adj ( I + tX A i ) H A i ) . Adjugates and interpolation compute these coefficients without assuming invertibility. The positive lower bounds determine the precision needed for roots, logarithms, and their derivatives.
The constraints defining T n θ T_n^\theta T n θ tr X = 1 \operatorname{tr} X=1 tr X = 1 I / n I/n I / n ( 1 − θ ) / ( 2 n ) (1-\theta)/(2n) ( 1 − θ ) / ( 2 n ) X ∈ T n θ X\in T_n^\theta X ∈ T n θ
F ( X ) ≥ max T n θ F − θ S 0 ≥ ( 1 − 2 θ ) max T n F . F(X)\geq\max_{T_n^\theta}F-\theta S_0\geq(1-2\theta)\max_{T_n}F. F ( X ) ≥ T n θ max F − θ S 0 ≥ ( 1 − 2 θ ) T n max F . Certified interval evaluation of S 0 S_0 S 0 log ( 1 / θ ) \log(1/\theta) log ( 1/ θ ) I / n I/n I / n 1 − p 1-p 1 − p
Evaluating rational powers
For positive relaxed scores put ℓ i : = log f i \ell_i:=\log f_i ℓ i := log f i
log Mean p , w [ f ] = a + 1 p log ( ∑ i w i e p ( ℓ i − a ) ) . (38) \log\operatorname{Mean}_{p,w}[f]
= a+\frac{1}{p}\log\left(\sum_i w_i e^{p(\ell_i-a)}\right). \tag*{(38)} log Mean p , w [ f ] = a + p 1 log ( i ∑ w i e p ( ℓ i − a ) ) . (38) At zero use ∑ i w i ℓ i \sum_i w_i\ell_i ∑ i w i ℓ i log ( 1 / ∣ p ∣ ) \log(1/|p|) log ( 1/∣ p ∣ ) p p p a : = min i ℓ i a:=\min_i\ell_i a := min i ℓ i w min w_{\min} w m i n ∣ p ∣ |p| ∣ p ∣ O ( log ∣ p ∣ ) O(\log|p|) O ( log ∣ p ∣ ) p ≤ 1 p\leq1 p ≤ 1
Success from an approximate optimum
Let S ⋆ : = max T n F S^\star:=\max_{T_n}F S ⋆ := max T n F q : = F ( X ) / S ⋆ ≥ 1 − 2 θ q:=F(X)/S^\star\geq1-2\theta q := F ( X ) / S ⋆ ≥ 1 − 2 θ
Y : = Mean p , w [ v A i ( P ) ] / S ⋆ Y:=\operatorname{Mean}_{p,w}[v_{A_i}(P)]/S^\star Y := Mean p , w [ v A i ( P )] / S ⋆ one still has 0 ≤ Y ≤ 1 0\leq Y\leq1 0 ≤ Y ≤ 1 b q bq b q b : = α n , k ( p ) b:=\alpha_{n,k}(p) b := α n , k ( p ) − log ( b q ) ≤ − log c δ , β − log ( 1 − 2 θ ) -\log(bq)\leq-\log c_{\delta,\beta}-\log(1-2\theta) − log ( b q ) ≤ − log c δ , β − log ( 1 − 2 θ ) ( α n , k ( p ) − ϵ / 2 ) S ⋆ (\alpha_{n,k}(p)-\epsilon/2)S^\star ( α n , k ( p ) − ϵ /2 ) S ⋆ 5 / 6 5/6 5/6 S ⋆ S^\star S ⋆
Small-determinant bounds and numerical precision
For square standard Gaussian H ∈ F k × k H \in\mathbb{F}^{k \times k} H ∈ F k × k ∣ det H ∣ 2 = β − k ∏ j = 1 k γ j |\det H|^2 = \beta^{-k} \prod_{j=1}^{k} \gamma_j ∣ det H ∣ 2 = β − k ∏ j = 1 k γ j γ j ∼ Gamma ( j β , rate 1 ) \gamma_j \sim\operatorname{Gamma}(j\beta,\text{ rate }1) γ j ∼ Gamma ( j β , rate 1 ) γ j \gamma_j γ j γ 1 \gamma_1 γ 1
Pr { ∣ det H ∣ 2 < t k } ≤ C β k t β , C β : = β β Γ ( β + 1 ) , 0 < t ≤ 1. (39) \Pr\{|\det H|^2 < t^k\} \le C_\beta k t^\beta,\qquad C_\beta:= \frac{\beta^\beta}{\Gamma(\beta+1)},\qquad0 < t \le1. \tag*{(39)} Pr { ∣ det H ∣ 2 < t k } ≤ C β k t β , C β := Γ ( β + 1 ) β β , 0 < t ≤ 1. (39) Indeed, a product below t k t^k t k γ j < β t \gamma_j < \beta t γ j < β t
For observation A i A_i A i Lemma A.1 has at most J : = ( n k ) ≤ 2 n J := \binom{n}{k} \le2^n J := ( k n ) ≤ 2 n C i : = e k ( A i 1 / 2 X A i 1 / 2 ) C_i := e_k(A_i^{1/2} X A_i^{1/2}) C i := e k ( A i 1/2 X A i 1/2 ) C i / J C_i/J C i / J ∣ det H ∣ 2 |\det H|^2 ∣ det H ∣ 2
Pr { det ( G ∗ A i G ) < ( C i / J ) t k } ≤ C β k t β . \Pr\{\det(G^* A_i G) < (C_i/J)t^k\} \le C_\beta k t^\beta. Pr { det ( G ∗ A i G ) < ( C i / J ) t k } ≤ C β k t β . No term needs to be found by the algorithm. The floor and (B.1) give a lower bound for C i C_i C i A i = I n A_i = I_n A i = I n
A union bound over all observations and all samples, together with Gaussian entry tails, gives an event of probability at least 1 − ζ 1-\zeta 1 − ζ 2 − B 2^{-B} 2 − B 2 B 2^B 2 B B B B log ( 1 / θ ) \log(1/\theta) log ( 1/ θ ) log ( 1 / ζ ) \log(1/\zeta) log ( 1/ ζ )
λ min ( G ∗ G ) ≥ det ( G ∗ G ) ∥ G ∗ G ∥ o p k − 1 . \lambda_{\min}(G^*G) \ge\frac{\det(G^*G)}{\lVert G^*G\rVert_{\mathrm{op}}^{k-1}}. λ m i n ( G ∗ G ) ≥ ∥ G ∗ G ∥ op k − 1 det ( G ∗ G ) . Determinant multilinearity and these conditioning bounds show that polynomial-bit approximations to X 1 / 2 X^{1/2} X 1/2 [ θ / n , 1 ] [\theta/n,1] [ θ / n , 1 ]
Lemma B.1 transfers the relative score accuracy to the objective uniformly in the power. A rational output basis R R R
ν A i ( range R ) k = det ( R ∗ A i R ) det ( R ∗ R ) . (40) \nu_{A_i}(\operatorname{range} R)^k = \frac{\det(R^* A_i R)}{\det(R^*R)}. \tag*{(40)} ν A i ( range R ) k = det ( R ∗ R ) det ( R ∗ A i R ) . (40) Both determinants are rational. Thus the algorithm needs no exact irrational orthonormalization. The same conditioning bounds give relative score evaluation. Selecting the largest approximate value loses at most twice the evaluation tolerance in logarithmic scale.
Finite-dimensional approximation
Proof (of Theorem 4.2 ). Cases with identically zero optimum were handled above. We may replace ε \varepsilon ε min ( ε , ε 5 , β / 4 ) \min(\varepsilon,\varepsilon_5,\beta/4) min ( ε , ε 5 , β /4 ) Theorem 4.1 supplies α n , k ( p ) \alpha_{n,k}(p) α n , k ( p ) F F F 1 / 6 1/6 1/6 1 / 6 1/6 1/6 2 / 3 2/3 2/3 log ( 1 / ε ) \log(1/\varepsilon) log ( 1/ ε ) max ( 1 , 1 / ε ) \max(1,1/\varepsilon) max ( 1 , 1/ ε ) S ⋆ ≥ OPT p , k S^\star\geq\operatorname{OPT}_{p,k} S ⋆ ≥ OPT p , k □ \square □
The strict finite-dimensional margin
For k ≥ 2 k \geq2 k ≥ 2 D : = det ( Z ∗ Z / n ) D := \det(Z^\ast Z/n) D := det ( Z ∗ Z / n ) Z ∈ F n × k Z \in\mathbb{F}^{n \times k} Z ∈ F n × k
g n , k : = ( ∏ j = 1 k n − j + 1 n ) 1 / k . g_{n,k} := \left(\prod_{j=1}^{k} \frac{n-j+1}{n}\right)^{1/k}. g n , k := ( j = 1 ∏ k n n − j + 1 ) 1/ k . The rectangular moment formula gives E D = g n , k k \mathbb{E}D = g_{n,k}^{k} E D = g n , k k
α n , k ( p ) α k ( p ) = 1 Mean p [ D 1 / k ] . (41) \frac{\alpha_{n,k}(p)}{\alpha_k(p)} = \frac{1}{\operatorname{Mean}_{p}[D^{1/k}]}. \tag*{(41)} α k ( p ) α n , k ( p ) = Mean p [ D 1/ k ] 1 . (41) Since p ≤ 1 ≤ k p \leq1 \leq k p ≤ 1 ≤ k Mean p [ D 1 / k ] ≤ ( E D ) 1 / k = g n , k \operatorname{Mean}_{p}[D^{1/k}] \leq(\mathbb{E}D)^{1/k} = g_{n,k} Mean p [ D 1/ k ] ≤ ( E D ) 1/ k = g n , k ( n − j + 1 ) / n (n-j+1)/n ( n − j + 1 ) / n
α n , k ( p ) α k ( p ) ≥ 1 g n , k ≥ 1 1 − ( k − 1 ) / ( 2 n ) ≥ exp ( k − 1 2 n ) . (42) \frac{\alpha_{n,k}(p)}{\alpha_k(p)} \geq\frac{1}{g_{n,k}} \geq\frac{1}{1-(k-1)/(2n)} \geq\exp\left(\frac{k-1}{2n}\right). \tag*{(42)} α k ( p ) α n , k ( p ) ≥ g n , k 1 ≥ 1 − ( k − 1 ) / ( 2 n ) 1 ≥ exp ( 2 n k − 1 ) . (42) For k = 1 k=1 k = 1
Lemma B.2 (Gamma log-convexity estimate) For x > 0 x>0 x > 0 t < 1 t<1 t < 1 x + t > 0 x+t>0 x + t > 0
log x − log Γ ( x + t ) − log Γ ( x ) t ≥ 1 − t 2 ( x + 1 ) , (43) \log x-\frac{\log\Gamma(x+t)-\log\Gamma(x)}{t}\geq\frac{1-t}{2(x+1)}, \tag*{(43)} log x − t log Γ ( x + t ) − log Γ ( x ) ≥ 2 ( x + 1 ) 1 − t , (43) with the continuous interpretation at t = 0 t=0 t = 0
Proof. Put g ( t ) : = log Γ ( x + t ) g(t):=\log\Gamma(x+t) g ( t ) := log Γ ( x + t ) ψ ′ ( y ) = ∑ j = 0 ∞ ( y + j ) − 2 > 1 / y \psi'(y)=\sum_{j=0}^{\infty}(y+j)^{-2}>1/y ψ ′ ( y ) = ∑ j = 0 ∞ ( y + j ) − 2 > 1/ y [ min ( t , 0 ) , 1 ] [\min(t,0),1] [ min ( t , 0 ) , 1 ] g ′ ′ > 1 / ( x + 1 ) g''>1/(x+1) g ′′ > 1/ ( x + 1 ) g ( t ) − t 2 / [ 2 ( x + 1 ) ] g(t)-t^2/[2(x+1)] g ( t ) − t 2 / [ 2 ( x + 1 )] 0 < t < 1 0<t<1 0 < t < 1 t < 0 t<0 t < 0 g ( 1 ) − g ( 0 ) = log x g(1)-g(0)=\log x g ( 1 ) − g ( 0 ) = log x t t t □ \square □
Taking x : = n β x:=n\beta x := n β t : = p t:=p t := p e u − 1 ≥ u e^u-1\geq u e u − 1 ≥ u
α n , 1 ( p ) − α 1 ( p ) ≥ α 1 ( p ) ( 1 − p ) n ( 2 β + 1 ) ( n ≥ 2 , − β < p < 1 ) . (44) \alpha_{n,1}(p)-\alpha_1(p)\geq\frac{\alpha_1(p)(1-p)}{n(2\beta+1)} \qquad(n\geq2,\ -\beta<p<1). \tag*{(44)} α n , 1 ( p ) − α 1 ( p ) ≥ n ( 2 β + 1 ) α 1 ( p ) ( 1 − p ) ( n ≥ 2 , − β < p < 1 ) . (44) Here 2 ( n β + 1 ) ≤ n ( 2 β + 1 ) 2(n\beta+1)\leq n(2\beta+1) 2 ( n β + 1 ) ≤ n ( 2 β + 1 )
Scalar attainment uniformly near power one
It remains to justify the last nontrivial case in Theorem 3.2: k = 1 k=1 k = 1 n ≥ 2 n\geq2 n ≥ 2 1 / 2 ≤ p < 1 1/2\leq p<1 1/2 ≤ p < 1
s : = 1 − p , b : = α 1 ( p ) , a : = b p , A : = α n , 1 ( p ) p . s:=1-p,\qquad b:=\alpha_1(p),\qquad a:=b^p,\qquad A:=\alpha_{n,1}(p)^p. s := 1 − p , b := α 1 ( p ) , a := b p , A := α n , 1 ( p ) p . For a mean-one Gamma variable Q Q Q β \beta β a = E Q p a = \mathbb{E}Q^{p} a = E Q p b ≥ α 1 ( 1 / 2 ) = 2 / π b \ge\alpha_1(1/2) = 2/\pi b ≥ α 1 ( 1/2 ) = 2/ π R \mathbb{R} R π / 4 \pi/4 π /4 C \mathbb{C} C a , b > 1 / 2 a,b > 1/2 a , b > 1/2 t ↦ E Q t t \mapsto\mathbb{E}Q^t t ↦ E Q t
1 − a ≤ s E ( Q log Q ) ≤ s E [ Q ( Q − 1 ) ] = s / β ≤ 2 s , (45) 1-a \le s\mathbb{E}(Q\log Q) \le s\mathbb{E}[Q(Q-1)] = s/\beta\le2s, \tag*{(45)} 1 − a ≤ s E ( Q log Q ) ≤ s E [ Q ( Q − 1 )] = s / β ≤ 2 s , (45) where log Q ≤ Q − 1 \log Q \le Q-1 log Q ≤ Q − 1 x : = n β x := n\beta x := n β r n ( p ) : = x − p Γ ( x + p ) / Γ ( x ) r_n(p) := x^{-p}\Gamma(x+p)/\Gamma(x) r n ( p ) := x − p Γ ( x + p ) /Γ ( x ) A = a / r n ( p ) A = a/r_n(p) A = a / r n ( p ) d : = s / ( 24 n ) d := s/(24n) d := s / ( 24 n ) Lemma B.2 gives
A − a ≥ a p ( 1 − p ) 2 ( n β + 1 ) ≥ s 24 n = d . (46) A-a \ge\frac{ap(1-p)}{2(n\beta+1)} \ge\frac{s}{24n} = d. \tag*{(46)} A − a ≥ 2 ( n β + 1 ) a p ( 1 − p ) ≥ 24 n s = d . (46) We used weaker bounds a ≥ 1 / 4 a \ge1/4 a ≥ 1/4 p ≥ 1 / 2 p \ge1/2 p ≥ 1/2 β ≤ 1 \beta\le1 β ≤ 1 A ≤ 1 A \le1 A ≤ 1 a + d ≤ 1 a+d \le1 a + d ≤ 1
Obtain positive definite rational X X X q : = F ( X ) / S ⋆ ≥ 1 − d / 4 q := F(X)/S^\star\ge1-d/4 q := F ( X ) / S ⋆ ≥ 1 − d /4 d / n d/n d / n log ( 1 / d ) = O ( log n + log ( 1 / ( 1 − p ) ) ) \log(1/d) = O(\log n + \log(1/(1-p))) log ( 1/ d ) = O ( log n + log ( 1/ ( 1 − p ))) Y : = Mean p , w [ v A i ( P ) ] / S ⋆ Y := \operatorname{Mean}_{p,w}[v_{A_i}(P)]/S^\star Y := Mean p , w [ v A i ( P )] / S ⋆
E ν Y p ≥ A q p ≥ A ( 1 − d / 4 ) ≥ a + 3 d / 4. \mathbb{E}_{\nu}Y^p \ge Aq^p \ge A(1-d/4) \ge a+3d/4. E ν Y p ≥ A q p ≥ A ( 1 − d /4 ) ≥ a + 3 d /4. Define T T T T : = ( a + d / 4 ) 1 / p T := (a+d/4)^{1/p} T := ( a + d /4 ) 1/ p E : = { Y ≥ T } E := \{Y \ge T\} E := { Y ≥ T } 0 ≤ Y ≤ 1 0 \le Y \le1 0 ≤ Y ≤ 1
ν ( E ) ≥ d / 2 1 − a − d / 4 ≥ d 2 ( 1 − a ) ≥ 1 96 n . (47) \nu(E) \ge\frac{d/2}{1-a-d/4} \ge\frac{d}{2(1-a)} \ge\frac{1}{96n}. \tag*{(47)} ν ( E ) ≥ 1 − a − d /4 d /2 ≥ 2 ( 1 − a ) d ≥ 96 n 1 . (47) The factor 1 − p 1-p 1 − p [ b , 1 ] [b,1] [ b , 1 ] x p x^p x p b − 1 / 2 ≤ 2 b^{-1/2} \le2 b − 1/2 ≤ 2
T − b ≥ d / 8. (48) T-b \ge d/8. \tag*{(48)} T − b ≥ d /8. (48) For the ordinary law, diagonalize X X X D : = ∑ j λ j Q ( j ) D := \sum_j \lambda_j Q^{(j)} D := ∑ j λ j Q ( j ) λ j ≥ 0 \lambda_j \ge0 λ j ≥ 0 Q ( j ) Q^{(j)} Q ( j ) Q Q Q E D p ≥ a ≥ 1 / 2 \mathbb{E}D^p \ge a \ge1/2 E D p ≥ a ≥ 1/2 1 ≤ 2 p ≤ 2 1 \le2p \le2 1 ≤ 2 p ≤ 2
E D 2 p ≤ E Q 2 p ≤ ( E Q 2 ) 2 p − 1 ≤ 1 + 1 / β ≤ 3. \mathbb{E}D^{2p} \le\mathbb{E}Q^{2p} \le(\mathbb{E}Q^2)^{2p-1} \le1+1/\beta\le3. E D 2 p ≤ E Q 2 p ≤ ( E Q 2 ) 2 p − 1 ≤ 1 + 1/ β ≤ 3. Thus the tilt W : = D p / E D p W := D^p/\mathbb{E}D^p W := D p / E D p E W 2 ≤ 12 \mathbb{E}W^2 \le12 E W 2 ≤ 12
Pr ( E ) ≥ ν ( E ) 2 12 ≥ 1 12 ( 96 n ) 2 . \Pr(E) \ge\frac{\nu(E)^2}{12} \ge\frac{1}{12(96n)^2}. Pr ( E ) ≥ 12 ν ( E ) 2 ≥ 12 ( 96 n ) 2 1 . At least 12 ( 96 n ) 2 log 6 12(96n)^2\log6 12 ( 96 n ) 2 log 6 1 / 6 1/6 1/6 1 / ( 1 − p ) 1/(1-p) 1/ ( 1 − p )
Use the discretization argument above with relative score, basis, and evaluation errors bounded by sufficiently small fixed multiples of d d d d / 128 d/128 d /128 log ( 1 / d ) \log(1/d) log ( 1/ d ) 1 / 6 1/6 1/6 2 / 3 2/3 2/3 b S ⋆ ≥ b O P T p , 1 bS^\star\ge b\,\mathrm{OPT}_{p,1} b S ⋆ ≥ b OPT p , 1 a , A , b , T a,A,b,T a , A , b , T
Attainment and assembly of the classification
Proof (of Theorem 3.2 ). Lemma A.3 gives a positive rational lower bound c δ , β c_{\delta,\beta} c δ , β α k ( p ) \alpha_k^{(p)} α k ( p ) k ≥ 2 k \ge2 k ≥ 2 c δ , β / ( 2 n ) c_{\delta,\beta}/(2n) c δ , β / ( 2 n ) Theorem 4.2 with slack c δ , β / ( 4 n ) c_{\delta,\beta}/(4n) c δ , β / ( 4 n ) α k ( p ) \alpha_k(p) α k ( p ) k = n k=n k = n k = 1 k=1 k = 1 p ≤ 1 / 2 p \le1/2 p ≤ 1/2 c δ , β / [ 4 n ( 2 β + 1 ) ] c_{\delta,\beta}/[4n(2\beta+1)] c δ , β / [ 4 n ( 2 β + 1 )] 1 / 2 ≤ p < 1 1/2 \le p < 1 1/2 ≤ p < 1 O ( n 2 ) O(n^2) O ( n 2 ) log n + log ( 1 / ( 1 − p ) ) \log n + \log(1/(1-p)) log n + log ( 1/ ( 1 − p )) k = p = 1 k = p = 1 k = p = 1 ∑ i w i A i \sum_i w_i A_i ∑ i w i A i ( 2 1 1 1 ) \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix} ( 2 1 1 1 ) ( 5 − 1 ) / 2 (\sqrt{5}-1)/2 ( 5 − 1 ) /2 □ \square □
Proof (of Theorem 3.1) For each fixed p > − k β p > -k\beta p > − k β 0 < δ < 1 0 < \delta< 1 0 < δ < 1 p ≥ − ( 1 − δ ) k β p \ge-(1-\delta)k\beta p ≥ − ( 1 − δ ) k β p < 1 p < 1 p < 1 p = 1 p = 1 p = 1 − k β -k\beta − k β ( k , p ) = ( 1 , 1 ) (k,p) = (1,1) ( k , p ) = ( 1 , 1 ) □ \square □
Matching computational hardness
This appendix proves Theorems 5.1, 5.2, and 5.4, together with the normalization identity in Lemma 5.3. We construct instances with optimum one in the YES case and with every feasible value at most the Gaussian threshold plus an arbitrarily small fixed slack in the NO case. Both constructions start from a block-subspace promise. In the NO case, it ensures that most coefficient blocks have no large individual coefficient, allowing comparison with Gaussian sums.
A small exceptional set of blocks may nevertheless carry all the coefficient energy. For p < 1 p < 1 p < 1 p = 1 p = 1 p = 1
Section C.1 supplies the common ingredients; Sections C.2 and C.3 prove the two PSD gaps. Section C.4 handles rational encoding, positive-definite perturbations, and the remaining powers. Section C.5 transfers the hardness to projection observations. Throughout, β : = 1 / 2 \beta:= 1/2 β := 1/2 R \mathbb{R} R β : = 1 \beta:= 1 β := 1 C \mathbb{C} C
The shared source and moment family
We use the following form of the block-subspace hardness theorem of Briët, Regev, and Saket [12 ] , stated explicitly as Theorem 4.3 in the full version of Ebrahimnejad, Nagda, and Oveis Gharan [18 ] . All norms in this statement are ordinary, unnormalized Euclidean norms. The YES witness selects one coordinate per block. The NO promise limits the number of blocks that have both bounded norm and a large coordinate.
Proposition C.1 (Block-subspace promise) For any fixed 0 < τ , δ 0 , η < 1 0 < \tau,\delta_0,\eta< 1 0 < τ , δ 0 , η < 1 b s r c b_{\mathrm{src}} b src W ⊆ R N b s r c W \subseteq\mathbb{R}^{N b_{\mathrm{src}}} W ⊆ R N b src
W W W v v v v i ∈ R b s r c v_i \in\mathbb{R}^{b_{\mathrm{src}}} v i ∈ R b src
For every v ∈ W v \in W v ∈ W ∥ v ∥ 2 = N \lVert v\rVert^2 = N ∥ v ∥ 2 = N τ N \tau N τ N ∥ v i ∥ ≤ η − 1 \lVert v_i\rVert\le\eta^{-1} ∥ v i ∥ ≤ η − 1 ∥ v i ∥ ∞ ≥ δ 0 \lVert v_i\rVert_\infty\ge\delta_0 ∥ v i ∥ ∞ ≥ δ 0
We use only this small-parameter regime. Its cases are disjoint: every block of the YES witness has norm and maximum coordinate one, so all N N N τ N < N \tau N < N τ N < N 1 / 2 1/2 1/2
The rational representation follows directly from the original construction. Its subspace is defined by homogeneous equalities between coordinate sums [12 Section 3.1, equation (3.1)] .
After selecting independent rows of the resulting integer constraint matrix D D D Π W = I − D T ( D D T ) − 1 D \Pi_W = I - D^{T}(DD^{T})^{-1}D Π W = I − D T ( D D T ) − 1 D § 15 .§ 4 . We use this real source over both fields. For F = C F = \mathbb{C} F = C W W W
A rational unitary family with independent row phases
Let C t C_t C t k k k ε 1 , … , ε k \varepsilon_1,\ldots,\varepsilon_k ε 1 , … , ε k R \mathbb{R} R C \mathbb{C} C π t \pi_t π t e r T C t = e π t ( r ) T e_r^{T}C_t=e_{\pi_t(r)}^{T} e r T C t = e π t ( r ) T U k \mathcal{U}_k U k
U : = diag ( ε 1 , … , ε k ) C t . U := \operatorname{diag}(\varepsilon_1,\ldots,\varepsilon_k)C_t. U := diag ( ε 1 , … , ε k ) C t . Every outcome is a rational orthogonal or unitary matrix, and
E U = 0 , E U a b U ‾ c d = δ a c δ b d k . (49) \mathbb{E}U=0,\qquad\mathbb{E}U_{ab}\overline{U}_{cd}=\frac{\delta_{ac}\delta_{bd}}{k}. \tag*{(49)} E U = 0 , E U ab U c d = k δ a c δ b d . (49) Different row phases have zero cross-moment; within one row the uniform shift visits each column with probability 1 / k 1/k 1/ k C \mathbb{C} C E U a b U c d = 0 \mathbb{E}U_{ab}U_{cd}=0 E U ab U c d = 0 k 2 k k2^k k 2 k k 4 k k4^k k 4 k k k k
A norm-exact source-coefficient bound
Let W F W_F W F N N N
Lemma C.2 (Few exceptional source blocks) Fix M ≥ 1 M \ge1 M ≥ 1 0 < d 0 < 1 0 < d_0 < 1 0 < d 0 < 1 τ 0 , δ 0 ≤ d 0 / 2 \tau_0,\delta_0 \le d_0/2 τ 0 , δ 0 ≤ d 0 /2 η 0 ≤ ( 4 M ) − 1 \eta_0 \le(4M)^{-1} η 0 ≤ ( 4 M ) − 1 V V V W F W_F W F ∥ V ∥ F 2 = N \lVert V\rVert_F^2=N ∥ V ∥ F 2 = N 8 τ 0 N 8\tau_0N 8 τ 0 N
∥ V i ∥ F ≤ M , max a ∥ V i , a ∥ 2 ≥ d 0 . \lVert V_i\rVert_F \le M,\qquad\max_a \lVert V_{i,a}\rVert_2 \ge d_0. ∥ V i ∥ F ≤ M , a max ∥ V i , a ∥ 2 ≥ d 0 . Here V i , a V_{i,a} V i , a ( i , a ) (i,a) ( i , a ) ( 8 τ 0 + M − 2 ) N (8\tau_0+M^{-2})N ( 8 τ 0 + M − 2 ) N ∥ V i ∥ F ≤ M \lVert V_i\rVert_F \le M ∥ V i ∥ F ≤ M max a ∥ V i , a ∥ 2 < d 0 \max_a\lVert V_{i,a}\rVert_2<d_0 max a ∥ V i , a ∥ 2 < d 0
Proof. First suppose V V V Q Q Q V T V V^T V V T V b j b_j b j B : = V Q B:=VQ B := V Q ε j \varepsilon_j ε j x : = ∑ j ε j b j x:=\sum_j\varepsilon_jb_j x := ∑ j ε j b j W W W
∥ x ∥ 2 = ∑ j ∥ b j ∥ 2 = N . \lVert x\rVert^2=\sum_j\lVert b_j\rVert^2=N. ∥ x ∥ 2 = j ∑ ∥ b j ∥ 2 = N . Fix a block in the asserted exceptional set and a row with squared norm σ 2 ≥ d 0 2 \sigma^2\ge d_0^2 σ 2 ≥ d 0 2 Z : = x i , a Z:=x_{i,a} Z := x i , a E Z 2 = σ 2 \mathbb{E}Z^2=\sigma^2 E Z 2 = σ 2
E Z 4 = 3 σ 4 − 2 ∑ j B i , a , j 4 ≤ 3 σ 4 . (50) \mathbb{E}Z^4=3\sigma^4-2\sum_j B_{i,a,j}^4\le3\sigma^4. \tag*{(50)} E Z 4 = 3 σ 4 − 2 j ∑ B i , a , j 4 ≤ 3 σ 4 . (50) If E : = { ∣ Z ∣ ≥ σ / 2 } E := \{|Z| \ge\sigma/2\} E := { ∣ Z ∣ ≥ σ /2 } σ 2 ≤ σ 2 / 4 + ( E Z 4 Pr ( E ) ) 1 / 2 \sigma^2 \le\sigma^2/4 + (\mathbb{E}Z^4\Pr(E))^{1/2} σ 2 ≤ σ 2 /4 + ( E Z 4 Pr ( E ) ) 1/2 Pr { ∣ Z ∣ ≥ d 0 / 2 } ≥ 3 / 16 \Pr\{|Z| \ge d_0/2\} \ge3/16 Pr { ∣ Z ∣ ≥ d 0 /2 } ≥ 3/16 E ∥ x i ∥ 2 ≤ M 2 \mathbb{E}\lVert x_i\rVert^2 \le M^2 E ∥ x i ∥ 2 ≤ M 2 Pr { ∥ x i ∥ > 4 M } ≤ 1 / 16 \Pr\{\lVert x_i\rVert> 4M\} \le1/16 Pr {∥ x i ∥ > 4 M } ≤ 1/16 1 / 8 1/8 1/8 τ 0 N \tau_0N τ 0 N N / M 2 N/M^2 N / M 2 ∥ V i ∥ F > M \lVert V_i\rVert_{\mathrm{F}} > M ∥ V i ∥ F > M V V V [ ℜ V ℑ V ] [\Re V\ \Im V] [ ℜ V ℑ V ] □ \square □
Gaussian comparison when every coefficient is small
For a square matrix T ∈ F k × k T \in\mathbb{F}^{k \times k} T ∈ F k × k
H ( T ) : = k ∣ det T ∣ 1 / k . \mathcal{H}(T) := \sqrt{k}\lvert\det T\rvert^{1/k}. H ( T ) := k ∣ det T ∣ 1/ k . Let U j U_j U j U k \mathcal{U}_k U k Z j Z_j Z j
H ( ∑ j U j Z j ) 2 ≤ ∥ ∑ j U j Z j ∥ F 2 , E ∥ ∑ j U j Z j ∥ F 2 = 1. (51) \mathcal{H}\left(\sum_j U_jZ_j\right)^2 \le\left\lVert\sum_j U_jZ_j\right\rVert_{\mathrm{F}}^2,\qquad\mathbb{E}\left\lVert\sum_j U_jZ_j\right\rVert_{\mathrm{F}}^2 = 1. \tag*{(51)} H ( j ∑ U j Z j ) 2 ≤ j ∑ U j Z j F 2 , E j ∑ U j Z j F 2 = 1. (51) The next lemma improves this second-moment bound to the Gaussian benchmark whenever every normalized coefficient is small. Its coefficient threshold is uniform in the number of summands.
Lemma C.3 (Uniform determinant moments) Fix k ≥ 1 k \ge1 k ≥ 1 − k β < p < 1 -k\beta< p < 1 − k β < p < 1 p ≠ 0 p \ne0 p = 0 q : = 2 p q := 2p q := 2 p κ > α k ( p ) \kappa> \sqrt{\alpha_k(p)} κ > α k ( p ) δ > 0 \delta> 0 δ > 0 ( Z j ) (Z_j) ( Z j )
∑ j ∥ Z j ∥ F 2 = 1 , max j ∥ Z j ∥ F ≤ δ , \sum_j \lVert Z_j\rVert_{\mathrm{F}}^2 = 1,\qquad\max_j \lVert Z_j\rVert_{\mathrm{F}} \le\delta, j ∑ ∥ Z j ∥ F 2 = 1 , j max ∥ Z j ∥ F ≤ δ , one has
( E H ( ∑ j U j Z j ) q ) 1 / q ≤ κ . (52) \left(\mathbb{E}\mathcal{H}\left(\sum_j U_jZ_j\right)^q\right)^{1/q} \le\kappa. \tag*{(52)} ( E H ( j ∑ U j Z j ) q ) 1/ q ≤ κ . (52) For q < 0 q < 0 q < 0 δ \delta δ
Proof We argue by contradiction. If the assertion failed, there would be a sequence of families violating (C.3) whose largest coefficient Frobenius norm tends to zero. The matrices Σ : = ∑ j Z j ∗ Z j \Sigma:= \sum_j Z_j^*Z_j Σ := ∑ j Z j ∗ Z j Σ ∞ ⪰ 0 \Sigma_\infty\succeq0 Σ ∞ ⪰ 0 max j ∥ Z j ∥ F \max_j\lVert Z_j\rVert_{\mathrm{F}} max j ∥ Z j ∥ F [9 ] and (C.1) give, along this subsequence,
∑ j U j Z j ⟹ T ∞ : = k − 1 / 2 G Σ ∞ 1 / 2 , (53) \sum_j U_jZ_j \mathrel{\Longrightarrow} T_\infty:= k^{-1/2}G\Sigma_\infty^{1/2}, \tag*{(53)} j ∑ U j Z j ⟹ T ∞ := k − 1/2 G Σ ∞ 1/2 , (53) where G G G E ∣ G a b ∣ 2 = 1 \mathbb{E}|G_{ab}|^2 = 1 E ∣ G ab ∣ 2 = 1 Σ ∞ / k \Sigma_\infty/k Σ ∞ / k Σ ∞ \Sigma_\infty Σ ∞
The covariance dependence factors:
H ( T ∞ ) 2 = ∣ det G ∣ 2 / k det ( Σ ∞ ) 1 / k ≤ k − 1 ∣ det G ∣ 2 / k . (54) \mathcal{H}(T_\infty)^2 = |\det G|^{2/k}\det(\Sigma_\infty)^{1/k} \le k^{-1}|\det G|^{2/k}. \tag*{(54)} H ( T ∞ ) 2 = ∣ det G ∣ 2/ k det ( Σ ∞ ) 1/ k ≤ k − 1 ∣ det G ∣ 2/ k . (54) The inequality follows from tr Σ ∞ = 1 \operatorname{tr}\Sigma_{\infty}=1 tr Σ ∞ = 1 [23 , 37 ] gives independent variables γ j ∼ Gamma ( j β , rate 1 ) \gamma_j \sim\operatorname{Gamma}(j\beta,\text{ rate }1) γ j ∼ Gamma ( j β , rate 1 ) ∣ det G ∣ 2 |\det G|^2 ∣ det G ∣ 2 β − k ∏ j = 1 k γ j \beta^{-k}\prod_{j=1}^{k}\gamma_j β − k ∏ j = 1 k γ j
E ∣ det G ∣ 2 u = β − k u ∏ j = 1 k Γ ( j β + u ) Γ ( j β ) ( u > − β ) . (55) \mathbb{E}|\det G|^{2u}=\beta^{-ku}\prod_{j=1}^{k}\frac{\Gamma(j\beta+u)}{\Gamma(j\beta)} \qquad(u>-\beta). \tag*{(55)} E ∣ det G ∣ 2 u = β − k u j = 1 ∏ k Γ ( j β ) Γ ( j β + u ) ( u > − β ) . (55) In the stated moment range,
[ E ( k − 1 / 2 ∣ det G ∣ 1 / k ) q ] 1 / q = α k ( p ) . \left[\mathbb{E}\left(k^{-1/2}|\det G|^{1/k}\right)^q\right]^{1/q}=\sqrt{\alpha_k(p)}. [ E ( k − 1/2 ∣ det G ∣ 1/ k ) q ] 1/ q = α k ( p ) . If 0 < q < 2 0<q<2 0 < q < 2
E [ H ( S ) q 1 { H ( S ) > R } ] ≤ R q − 2 . \mathbb{E}\left[\mathcal{H}(S)^q\mathbf{1}_{\{\mathcal{H}(S)>R\}}\right]\leq R^{q-2}. E [ H ( S ) q 1 { H ( S ) > R } ] ≤ R q − 2 . Thus (C.4 entails convergence of the q q q α k ( p ) q / 2 < κ q \alpha_k(p)^{q/2}<\kappa^q α k ( p ) q /2 < κ q
For q < 0 q<0 q < 0 min { H ( T ) q , M } \min\{\mathcal{H}(T)^q,M\} min { H ( T ) q , M } M M M det T = 0 \det T=0 det T = 0 M → ∞ M\to\infty M → ∞
lim inf E H ( S ) q ≥ E H ( T ∞ ) q . \liminf\mathbb{E}\mathcal{H}(S)^q\geq\mathbb{E}\mathcal{H}(T_\infty)^q. lim inf E H ( S ) q ≥ E H ( T ∞ ) q . If Σ ∞ \Sigma_\infty Σ ∞ α k ( p ) q / 2 > κ q \alpha_k(p)^{q/2}>\kappa^q α k ( p ) q /2 > κ q
Both cases contradict the strict limiting inequalities above. The contradiction also proves uniformity in the number of summands. □ \square □
Hardness for powers below one
We prove Theorem 5.1 . Fix its field, selected dimension, rational power − k β < p < 1 -k\beta<p<1 − k β < p < 1 p ≠ 0 p\ne0 p = 0 ε \varepsilon ε q : = 2 p q:=2p q := 2 p b s r c b_{\mathrm{src}} b src
Construction and completeness
Write Π : = Π W ⊗ I k \Pi:=\Pi_W\otimes I_k Π := Π W ⊗ I k x i , j ∈ F k x_{i,j}\in\mathbb{F}^k x i , j ∈ F k 1 ≤ i ≤ N 1\leq i\leq N 1 ≤ i ≤ N 1 ≤ j ≤ b s r c 1\leq j\leq b_{\mathrm{src}} 1 ≤ j ≤ b src i i i U : = ( U 1 , … , U b s r c ) ∈ U k b s r c U:=(U_1,\ldots,U_{b_{\mathrm{src}}})\in\mathcal{U}_k^{b_{\mathrm{src}}} U := ( U 1 , … , U b src ) ∈ U k b src
L i , U x : = ∑ j = 1 b s r c U j ( Π x ) i , j , A i , U : = N L i , U ∗ L i , U . (56) L_{i,U}x:=\sum_{j=1}^{b_{\mathrm{src}}}U_j(\Pi x)_{i,j},\qquad A_{i,U}:=N L_{i,U}^{*}L_{i,U}. \tag*{(56)} L i , U x := j = 1 ∑ b src U j ( Π x ) i , j , A i , U := N L i , U ∗ L i , U . (56) We call L i , U L_{i,U} L i , U A i , U A_{i,U} A i , U m : = N ∣ U k ∣ b s r c m:=N|\mathcal{U}_k|^{b_{\mathrm{src}}} m := N ∣ U k ∣ b src k k k F N b s r c k \mathbb{F}^{N b_{\mathrm{src}}k} F N b src k b s r c b_{\mathrm{src}} b src k k k U j U_j U j i i i
1 m ∑ i , U A i , U = Π . (57) \frac{1}{m}\sum_{i,U}A_{i,U}=\Pi. \tag*{(57)} m 1 i , U ∑ A i , U = Π. (57) Consequently, for every frame P P P
1 m ∑ i , U det ( P ∗ A i , U P ) 1 / k ≤ 1 k tr ( P ∗ Π P ) ≤ 1. (58) \frac{1}{m}\sum_{i,U}\det(P^*A_{i,U}P)^{1/k}\leq\frac{1}{k}\operatorname{tr}(P^*\Pi P)\leq1. \tag*{(58)} m 1 i , U ∑ det ( P ∗ A i , U P ) 1/ k ≤ k 1 tr ( P ∗ Π P ) ≤ 1. (58) The first inequality is determinant AM–GM. Every power mean with p ≤ 1 p \le1 p ≤ 1
For a YES witness v v v P : = ( v / N ) ⊗ I k P := (v/\sqrt{N}) \otimes I_k P := ( v / N ) ⊗ I k v i v_i v i L i , U P = U j / N L_{i,U}P = U_j/\sqrt{N} L i , U P = U j / N j j j I k I_k I k
Soundness and the order of parameters
Reduction to source-supported matrices. Fix a frame P P P Π P \Pi_P Π P Π P = 0 \Pi_P = 0 Π P = 0
Q : = k Π P ∥ Π P ∥ F . Q := \frac{\sqrt{k}\,\Pi_P}{\lVert\Pi_P\rVert_{\mathrm{F}}}. Q := ∥ Π P ∥ F k Π P . Since ∥ Π P ∥ F ≤ k \lVert\Pi_P\rVert_{\mathrm{F}} \le\sqrt{k} ∥ Π P ∥ F ≤ k Q Q Q W F ⊗ F k \mathcal{W}_{F} \otimes\mathbb{F}^{k} W F ⊗ F k k \sqrt{k} k
Set Z : = N / k Q Z := \sqrt{N/k}\,Q Z := N / k Q ∥ Z ∥ F 2 = N \lVert Z\rVert_{\mathrm{F}}^{2} = N ∥ Z ∥ F 2 = N k × k k \times k k × k Z i , j Z_{i,j} Z i , j Q Q Q A i , U A_{i,U} A i , U
det ( Q ∗ A i , U Q ) 1 / k = H ( ∑ j U j Z i , j ) 2 . (59) \det(Q^{*}A_{i,U}Q)^{1/k} = \mathcal{H}\left(\sum_{j} U_{j}Z_{i,j}\right)^{2}. \tag*{(59)} det ( Q ∗ A i , U Q ) 1/ k = H ( j ∑ U j Z i , j ) 2 . (59) Writing S i : = ∑ j U j Z i , j S_i := \sum_j U_j Z_{i,j} S i := ∑ j U j Z i , j q q q H \mathcal{H} H q = 2 p q = 2p q = 2 p ( i , U ) (i,U) ( i , U )
Mean p [ H ( S i ) ] 2 = ( Mean 2 p [ H ( S i ) ] ) 2 . \operatorname{Mean}_{p}[\mathcal{H}(S_i)]^{2}
=
\left(\operatorname{Mean}_{2p}[\mathcal{H}(S_i)]\right)^{2}. Mean p [ H ( S i ) ] 2 = ( Mean 2 p [ H ( S i )] ) 2 . A common good set. Arrange the entries of each Z i , j Z_{i,j} Z i , j ( i , j ) (i,j) ( i , j ) W F \mathcal{W}_{F} W F N N N G \mathcal{G} G
g : = ∣ G ∣ N ≥ 1 − f , f : = 8 τ 0 + M − 2 , max j ∥ Z i , j ∥ F < d 0 ( i ∈ G ) . (60) g := \frac{|\mathcal{G}|}{N} \ge1-f,
\qquad
f := 8\tau_{0}+M^{-2},
\qquad
\max_{j}\lVert Z_{i,j}\rVert_{\mathrm{F}} < d_{0}
\quad(i \in\mathcal{G}). \tag*{(60)} g := N ∣ G ∣ ≥ 1 − f , f := 8 τ 0 + M − 2 , j max ∥ Z i , j ∥ F < d 0 ( i ∈ G ) . (60) The set may depend on P P P
Moments within each block. Put s i 2 : = ∑ j ∥ Z i , j ∥ 2 s_i^{2} := \sum_j \lVert Z_{i,j}\rVert^{2} s i 2 := ∑ j ∥ Z i , j ∥ 2 ∑ i s i 2 = N \sum_i s_i^{2} = N ∑ i s i 2 = N s i s_i s i λ > 0 \lambda> 0 λ > 0 d 0 ≤ δ λ d_0 \le\delta\lambda d 0 ≤ δ λ δ \delta δ s i > λ s_i > \lambda s i > λ d 0 / s i ≤ δ d_0/s_i \le\delta d 0 / s i ≤ δ
Expectations below average the finite gadget within each block. On any block, homogeneity rescales (C.2) from unit coefficient energy to s i 2 s_i^{2} s i 2 q q q H ( S i ) \mathcal{H}(S_i) H ( S i ) s i s_i s i s i = 0 s_i = 0 s i = 0 s i > λ s_i > \lambda s i > λ s i s_i s i q q q κ s i \kappa s_i κ s i s i ≤ λ s_i \le\lambda s i ≤ λ q q q λ \lambda λ
Averaging at positive powers. For 0 < q < 2 0 < q < 2 0 < q < 2 κ q + λ q \kappa^{q}+\lambda^{q} κ q + λ q f f f
1 N ∑ i ∉ G E H ( S i ) q ≤ 1 N ∑ i ∉ G s i q ≤ f 1 − q / 2 . \frac{1}{N}\sum_{i\notin\mathcal{G}}\mathbb{E}\mathcal{H}(S_i)^{q}
\le
\frac{1}{N}\sum_{i\notin\mathcal{G}}s_i^{q}
\le f^{1-q/2}. N 1 i ∈ / G ∑ E H ( S i ) q ≤ N 1 i ∈ / G ∑ s i q ≤ f 1 − q /2 . Consequently
( 1 N ∑ i E H ( S i ) q ) 1 / q ≤ [ κ q + λ q + f 1 − q / 2 ] 1 / q . (61) \left(\frac{1}{N}\sum_i \mathbb{E}\mathcal{H}(S_i)^{q}\right)^{1/q}
\le
\left[\kappa^{q}+\lambda^{q}+f^{1-q/2}\right]^{1/q}. \tag*{(61)} ( N 1 i ∑ E H ( S i ) q ) 1/ q ≤ [ κ q + λ q + f 1 − q /2 ] 1/ q . (61) Averaging at negative powers. For q < 0 q < 0 q < 0 t i : = max { λ , κ s i } t_i := \max\{\lambda,\kappa s_i\} t i := max { λ , κ s i } G \mathcal{G} G E H ( S i ) q ≥ t i q \mathbb{E}\mathcal{H}(S_i)^q \ge t_i^q E H ( S i ) q ≥ t i q x ↦ x q / 2 x \mapsto x^{q/2} x ↦ x q /2
1 N ∑ i E H ( S i ) q ≥ 1 N ∑ i ∈ G t i q ≥ g ( ∑ i ∈ G t i 2 g N ) q / 2 ≥ g ( λ 2 + κ 2 g ) q / 2 . (62) \frac{1}{N}\sum_i \mathbb{E}\mathcal{H}(S_i)^q \ge\frac{1}{N}\sum_{i\in\mathcal{G}} t_i^q
\ge g\left(\frac{\sum_{i\in\mathcal{G}}t_i^2}{gN}\right)^{q/2}
\ge g\left(\frac{\lambda^2+\kappa^2}{g}\right)^{q/2}. \tag*{(62)} N 1 i ∑ E H ( S i ) q ≥ N 1 i ∈ G ∑ t i q ≥ g ( g N ∑ i ∈ G t i 2 ) q /2 ≥ g ( g λ 2 + κ 2 ) q /2 . (62) After taking the negative root,
( 1 N ∑ i E H ( S i ) q ) 1 / q ≤ λ 2 + κ 2 g 1 / q − 1 / 2 . (63) \left(\frac{1}{N}\sum_i \mathbb{E}\mathcal{H}(S_i)^q\right)^{1/q}
\le\sqrt{\lambda^2+\kappa^2}\,g^{1/q-1/2}. \tag*{(63)} ( N 1 i ∑ E H ( S i ) q ) 1/ q ≤ λ 2 + κ 2 g 1/ q − 1/2 . (63) Infinite moments only strengthen (C.13).
Choosing parameters. In view of (C.10), the target p p p q q q ε / 2 \varepsilon/2 ε /2
Choose κ > α k ( p ) \kappa> \sqrt{\alpha_k(p)} κ > α k ( p ) κ 2 < α k ( p ) + ε / 2 \kappa^2 < \alpha_k(p) + \varepsilon/2 κ 2 < α k ( p ) + ε /2 λ > 0 \lambda> 0 λ > 0 0 < f ∗ < 1 0 < f_* < 1 0 < f ∗ < 1 α k ( p ) + ε / 2 \alpha_k(p) + \varepsilon/2 α k ( p ) + ε /2 f ≤ f ∗ f \le f_* f ≤ f ∗ g ≥ 1 − f ∗ g \ge1-f_* g ≥ 1 − f ∗
Obtain δ \delta δ M ≥ 1 M \ge1 M ≥ 1 τ 0 > 0 \tau_0 > 0 τ 0 > 0 8 τ 0 + M − 2 ≤ f ∗ 8\tau_0 + M^{-2} \le f_* 8 τ 0 + M − 2 ≤ f ∗ 0 < d 0 < min { 1 , δ λ } 0 < d_0 < \min\{1,\delta\lambda\} 0 < d 0 < min { 1 , δ λ }
Invoke the source theorem with τ ≤ min { τ 0 , 1 / 2 } \tau\le\min\{\tau_0,1/2\} τ ≤ min { τ 0 , 1/2 } δ 0 ≤ d 0 / 2 \delta_0 \le d_0/2 δ 0 ≤ d 0 /2 η ≤ ( 4 M ) − 1 \eta\le(4M)^{-1} η ≤ ( 4 M ) − 1 1 / 2 1/2 1/2 b s r c b_{\mathrm{src}} b src N N N
The comparison threshold is independent of the number of coefficients, so choosing it before the source block length creates no circular dependence. This proves PSD hardness strictly above the negative boundary at nonzero power. Section C.4.3 supplies the positive-definite version, and Section C.4.4 treats the remaining powers.
Why the arithmetic endpoint needs a new argument. At q = 2 q = 2 q = 2 1 − q / 2 1-q/2 1 − q /2 f > 0 f > 0 f > 0 s i = f − 1 / 2 s_i = f^{-1/2} s i = f − 1/2 s i = 0 s_i = 0 s i = 0
1 N ∑ i s i 2 = 1 , 1 N ∑ i e x c e p t i o n a l s i q = f 1 − q / 2 . \frac{1}{N}\sum_i s_i^2 = 1,\qquad\frac{1}{N}\sum_{i\ \mathrm{exceptional}}s_i^q = f^{1-q/2}. N 1 i ∑ s i 2 = 1 , N 1 i exceptional ∑ s i q = f 1 − q /2 . For 0 < q < 2 0 < q < 2 0 < q < 2 f f f q = 2 q = 2 q = 2
Hardness at power one
We prove Theorem 5.2. Fix k ≥ 2 k \ge2 k ≥ 2
a k : = α k ( 1 ) = 1 k E ∣ det G ∣ 2 / k , (64) a_k := \alpha_k(1) = \frac{1}{k}\mathbb{E}|\det G|^{2/k}, \tag*{(64)} a k := α k ( 1 ) = k 1 E ∣ det G ∣ 2/ k , (64) where G G G d ≥ 2 d \ge2 d ≥ 2 max { a k , 1 / d } \max\{a_k,1/d\} max { a k , 1/ d } 1 / d ≤ a k 1/d \le a_k 1/ d ≤ a k
An orientation is the choice of a factor h h h G u G_u G u e ∅ e_{\varnothing} e ∅ e h e_h e h
F h ( T ) ≤ a k e ∅ + e h + E e r r , F ( T ) ≤ max { a k , 1 / d } + E e r r . F_h(T) \le a_k e_{\varnothing} + e_h + E_{\mathrm{err}}, \qquad F(T) \le\max\{a_k,1/d\} + E_{\mathrm{err}}. F h ( T ) ≤ a k e ∅ + e h + E err , F ( T ) ≤ max { a k , 1/ d } + E err . Here F h F_h F h h h h F F F E e r r E_{\mathrm{err}} E err 1 / d 1/d 1/ d
We use u u u h h h r r r u u u i u i_u i u a u a_u a u N N N b s r c b_{\mathrm{src}} b src
Scalar comparison on prescribed subsets
The first ingredient replaces one independently sampled factor by a Gaussian contraction, meaning a sum against Gaussian coefficients along that factor. The comparison must remain valid when a prescribed set of source blocks is retained.
Put θ : = 2 / k ∈ ( 0 , 2 ) \theta:= 2/k \in(0,2) θ := 2/ k ∈ ( 0 , 2 ) μ θ : = E ∣ g ∣ θ \mu_\theta:= \mathbb{E}|g|^\theta μ θ := E ∣ g ∣ θ g g g σ a \sigma_a σ a
Lemma C.4 For every ϵ S > 0 \epsilon_S > 0 ϵ S > 0 c ∈ W F c \in\mathcal{W}_{\mathrm{F}} c ∈ W F S ⊆ [ N ] S \subseteq[N] S ⊆ [ N ]
1 N ∑ i ∈ S E ∣ ∑ a σ a c i , a ∣ θ ≤ μ θ ( 1 N ∑ i ∈ S , a ∣ c i , a ∣ 2 ) θ / 2 + ϵ S ( 1 N ∑ i , a ∣ c i , a ∣ 2 ) θ / 2 . (65) \frac{1}{N}\sum_{i\in S}\mathbb{E}\left|\sum_a \sigma_a c_{i,a}\right|^\theta
\le
\mu_\theta\left(\frac{1}{N}\sum_{i\in S,a}|c_{i,a}|^2\right)^{\theta/2}
+
\epsilon_S\left(\frac{1}{N}\sum_{i,a}|c_{i,a}|^2\right)^{\theta/2}. \tag*{(65)} N 1 i ∈ S ∑ E a ∑ σ a c i , a θ ≤ μ θ N 1 i ∈ S , a ∑ ∣ c i , a ∣ 2 θ /2 + ϵ S ( N 1 i , a ∑ ∣ c i , a ∣ 2 ) θ /2 . (65) The parameter choice is independent of N N N c c c S S S c c c W F \mathcal{W}_{\mathrm{F}} W F S S S N N N S S S S S S
Proof. The zero vector is immediate. Otherwise normalize by homogeneity so that ∥ c ∥ 2 2 = N \lVert c\rVert_2^2=N ∥ c ∥ 2 2 = N u i 2 : = ∑ a ∣ c i , a ∣ 2 u_i^2 := \sum_a |c_{i,a}|^2 u i 2 := ∑ a ∣ c i , a ∣ 2 f S : = 8 τ S + M − 2 f_S := 8\tau_S + M^{-2} f S := 8 τ S + M − 2 d S d_S d S λ > 0 \lambda> 0 λ > 0 u i ≤ λ u_i \le\lambda u i ≤ λ λ θ \lambda^\theta λ θ E ∣ ∑ a σ a c i , a ∣ θ ≤ u i θ \mathbb{E}\left|\sum_a \sigma_a c_{i,a}\right|^\theta\le u_i^\theta E ∣ ∑ a σ a c i , a ∣ θ ≤ u i θ f S 1 − θ / 2 f_S^{1-\theta/2} f S 1 − θ /2
On each remaining block normalize the coefficient vector by u i u_i u i θ / 2 \theta/2 θ /2 ρ > 0 \rho> 0 ρ > 0
E ∣ ∑ a σ a c i , a ∣ θ ≤ ( μ θ + ρ ) u i θ \mathbb{E}\left|\sum_a \sigma_a c_{i,a}\right|^\theta
\le(\mu_\theta+\rho)u_i^\theta E a ∑ σ a c i , a θ ≤ ( μ θ + ρ ) u i θ if d S / λ d_S/\lambda d S / λ S S S
1 N ∑ i ∈ S u i θ ≤ ( 1 N ∑ i ∈ S u i 2 ) θ / 2 . \frac{1}{N}\sum_{i\in S}u_i^\theta\leq\left(\frac{1}{N}\sum_{i\in S}u_i^2\right)^{\theta/2}. N 1 i ∈ S ∑ u i θ ≤ ( N 1 i ∈ S ∑ u i 2 ) θ /2 . The error beyond the asserted restricted-energy term is at most ρ + λ θ + f S 1 − θ / 2 \rho+\lambda^\theta+f_S^{1-\theta/2} ρ + λ θ + f S 1 − θ /2 ρ \rho ρ λ \lambda λ f S f_S f S M S M_S M S τ S \tau_S τ S d S d_S d S □ \square □
The tensor instance
Set
Π : = Π W ⊗ d ⊗ I k , V : = W F ⊗ d ⊗ F k . \Pi:= \Pi_W^{\otimes d}\otimes I_k,\qquad\mathcal{V}:=\mathcal{W}_F^{\otimes d}\otimes F^k. Π := Π W ⊗ d ⊗ I k , V := W F ⊗ d ⊗ F k . The ambient dimension is k ( N b s r c ) d k(N_{\mathrm{bsrc}})^d k ( N bsrc ) d
( ( i 1 , a 1 ) , … , ( i d , a d ) , t ) , i u ∈ [ N ] , a u ∈ [ b s r c ] , t ∈ [ k ] . ((i_1,a_1),\ldots,(i_d,a_d),t),\qquad i_u\in[N],\quad a_u\in[b_{\mathrm{src}}],\quad t\in[k]. (( i 1 , a 1 ) , … , ( i d , a d ) , t ) , i u ∈ [ N ] , a u ∈ [ b src ] , t ∈ [ k ] . For a first example, take d = 2 d=2 d = 2 h = 1 h=1 h = 1
( L x ) r : = ∑ a , b σ b 2 , r e r T U a ( Π x ) j , a , i 2 , r , b . (Lx)_r:=\sum_{a,b}\sigma_b^{2,r}e_r^T U_a(\Pi x)_{j,a,i_{2,r},b}. ( Lx ) r := a , b ∑ σ b 2 , r e r T U a ( Π x ) j , a , i 2 , r , b . The first factor’s block index j j j U a U_a U a i 2 , r i_{2,r} i 2 , r σ b 2 , r \sigma_b^{2,r} σ b 2 , r h = 2 h=2 h = 2 1 / d ≤ a k 1/d\leq a_k 1/ d ≤ a k
In general, the instance has d d d h h h
Choose the shared block index j : = i h ∈ [ N ] j:=i_h\in[N] j := i h ∈ [ N ] U a ∈ U k U_a\in\mathcal{U}_k U a ∈ U k a ∈ [ b s r c ] a\in[b_{\mathrm{src}}] a ∈ [ b src ]
For each nonshared factor u ≠ h u\ne h u = h r ∈ [ k ] r\in[k] r ∈ [ k ] i u , r ∈ [ N ] i_{u,r}\in[N] i u , r ∈ [ N ] ( σ a u , r ) a (\sigma_a^{u,r})_a ( σ a u , r ) a
All finite choices are enumerated in the reduction; probability notation describes their uniform average. Define the r r r
( L x ) r : = e r T ∑ a 1 , … , a d ( ∏ u ≠ h σ a u u , r ) U a h ( Π x ) i 1 , r , a 1 , … , j , a h , … , i d , r , a d , A : = N d L ∗ L . (66) (Lx)_r:=e_r^T\sum_{a_1,\ldots,a_d}\left(\prod_{u\ne h}\sigma_{a_u}^{u,r}\right)U_{a_h}(\Pi x)_{i_{1,r},a_1,\ldots,j,a_h,\ldots,i_{d,r},a_d},\qquad A:=N^dL^*L. \tag*{(66)} ( Lx ) r := e r T a 1 , … , a d ∑ u = h ∏ σ a u u , r U a h ( Π x ) i 1 , r , a 1 , … , j , a h , … , i d , r , a d , A := N d L ∗ L . (66) The number of observations is a constant times d N 1 + k ( d − 1 ) dN^{1+k(d-1)} d N 1 + k ( d − 1 ) k k k d d d b s r c b_{\mathrm{src}} b src k k k
Averaging the scalar phases kills unequal labels in nonshared factors. Equation (C.1) kills unequal shared labels and internal coordinates and assigns 1 / k 1/k 1/ k
E A = Π . (67) \mathbb{E}A=\Pi. \tag*{(67)} E A = Π. (67) Thus determinant AM–GM bounds every feasible arithmetic objective by one. For a YES witness v v v P : = ( v ⊗ d / N d / 2 ) ⊗ I k P:=(v^{\otimes d}/N^{d/2})\otimes I_k P := ( v ⊗ d / N d /2 ) ⊗ I k N d / 2 L P N^{d/2}LP N d /2 L P v j v_j v j I k I_k I k
Common good sets and independent-index replacement
Good sets and coefficient energy. For soundness, project a candidate frame onto V V V T T T ∥ T ∥ F 2 = k \lVert T\rVert_{F}^{2}=k ∥ T ∥ F 2 = k u u u N / k T \sqrt{N/k}T N / k T ( i u , a u ) (i_u,a_u) ( i u , a u ) W F W_F W F N N N τ 0 : = τ H \tau_0 := \tau_H τ 0 := τ H τ H \tau_H τ H G u ⊆ [ N ] G_u \subseteq[N] G u ⊆ [ N ] f : = 8 τ H + M − 2 f := 8\tau_H+M^{-2} f := 8 τ H + M − 2
∑ a u , other indices ∣ T ∣ 2 ≤ k M 2 N , max a u ∑ other indices ∣ T ∣ 2 ≤ k d 0 2 N ( i u ∈ G u ) . (68) \sum_{a_u,\ \text{other indices}} |T|^2 \le\frac{kM^2}{N}, \qquad\max_{a_u}\sum_{\text{other indices}} |T|^2 \le\frac{kd_0^2}{N}\quad(i_u\in G_u). \tag*{(68)} a u , other indices ∑ ∣ T ∣ 2 ≤ N k M 2 , a u max other indices ∑ ∣ T ∣ 2 ≤ N k d 0 2 ( i u ∈ G u ) . (68) The sets are fixed by T T T
The good/bad choices in the d d d e ∅ e_{\varnothing} e ∅ 1 / k 1/k 1/ k i u i_u i u e h e_h e h i h i_h i h
e ∅ + ∑ h = 1 d e h ≤ 1. (69) e_{\varnothing}+\sum_{h=1}^{d}e_h\le1. \tag*{(69)} e ∅ + h = 1 ∑ d e h ≤ 1. (69) The missing energy lies in rectangles with at least two bad factors. These are disjoint portions of coefficient energy; the determinant itself is not decomposed additively across rectangles.
For d = 2 d=2 d = 2
Table 2.
Discarding exceptional independent indices. Fix orientation h h h R : = N d / 2 L T R := N^{d/2}LT R := N d /2 L T A = N d L ∗ L A=N^dL^*L A = N d L ∗ L T T T det ( T ∗ A T ) 1 / k = ∣ det R ∣ 2 / k \det(T^*AT)^{1/k}=|\det R|^{2/k} det ( T ∗ A T ) 1/ k = ∣ det R ∣ 2/ k ∣ det R ∣ 2 / k ≤ ∏ r ∥ R r ∥ 2 / k |\det R|^{2/k}\le\prod_r\lVert R_r\rVert^{2/k} ∣ det R ∣ 2/ k ≤ ∏ r ∥ R r ∥ 2/ k r r r
E [ 1 b a d ∥ R r ∥ 2 / k ∣ shared ] ≤ f 1 − 1 / k E [ ∥ R r ∥ 2 ∣ shared ] 1 / k . \mathbb{E}[1_{\mathrm{bad}}\lVert R_r\rVert^{2/k}\mid\text{shared}]\le f^{1-1/k}\mathbb{E}[\lVert R_r\rVert^2\mid\text{shared}]^{1/k}. E [ 1 bad ∥ R r ∥ 2/ k ∣ shared ] ≤ f 1 − 1/ k E [∥ R r ∥ 2 ∣ shared ] 1/ k . Apply the ordinary moment inequality in the other rows, then AM–GM to their second moments. Averaging the shared data and using E ∥ R ∥ F 2 = k \mathbb{E}\lVert R\rVert_F^2=k E ∥ R ∥ F 2 = k f 1 − 1 / k f^{1-1/k} f 1 − 1/ k m 0 : = k ( d − 1 ) m_0:=k(d-1) m 0 := k ( d − 1 ) ( u , r ) (u,r) ( u , r ) G u G_u G u
m 0 f 1 − 1 / k (70) m_0f^{1-1/k} \tag*{(70)} m 0 f 1 − 1/ k (70) No restriction on the energy carried by the discarded indices has been used.
Replacing retained factors by Gaussian contractions. Next replace each independently indexed factor in each row by a Gaussian contraction. Condition on all other variables. The determinant is a scalar linear form in the current factor, and its full coefficient vector belongs to W F W_F W F S S S S S S S S S G S G_S G S N − 1 / 2 g i , a i ∈ S N^{-1/2}g_{i,a_i\in S} N − 1/2 g i , a i ∈ S G a l l G_{\mathrm{all}} G all
E I , σ [ 1 I ∈ S ∣ det R ∣ 2 / k ] ≤ E G S ∣ det R ∣ 2 / k + ξ E G a l l ∣ det R ∣ 2 / k , ξ : = ϵ S / μ 2 / k . (71) \mathbb{E}_{I,\sigma}[1_{I\in S}|\det R|^{2/k}]\le\mathbb{E}_{G_S}|\det R|^{2/k}+\xi\mathbb{E}_{G_{\mathrm{all}}}|\det R|^{2/k},\qquad\xi:=\epsilon_S/\mu_{2/k}. \tag*{(71)} E I , σ [ 1 I ∈ S ∣ det R ∣ 2/ k ] ≤ E G S ∣ det R ∣ 2/ k + ξ E G all ∣ det R ∣ 2/ k , ξ := ϵ S / μ 2/ k . (71) We use this comparison conditionally for the determinant. Every subsequent replacement has the same scalar linear form.
Iterating (C.22) produces a positive sum of Gaussian branches. For example, two replacements give four terms with coefficients 1 1 1 ξ \xi ξ ξ \xi ξ ξ 2 \xi^2 ξ 2 m 0 m_0 m 0 ( 1 + ξ ) m 0 (1+\xi)^{m_0} ( 1 + ξ ) m 0 G u G_u G u ( 1 + ξ ) m 0 − 1 (1+\xi)^{m_0}-1 ( 1 + ξ ) m 0 − 1
R r = N e r T ∑ a U a Y r , a , (72) R_r=\sqrt{N}e_r^{\mathsf T}\sum_a U_aY_{r,a}, \tag*{(72)} R r = N e r T a ∑ U a Y r , a , (72) where Y r , a Y_{r,a} Y r , a T T T d − 1 d-1 d − 1 N \sqrt{N} N d − 1 d-1 d − 1 1 / N 1/N 1/ N N d N^d N d T r r e t T_r^{\mathrm{ret}} T r ret r r r
E ∥ R ∥ F 2 = 1 k ∑ r = 1 k ∥ T r r e t ∥ F 2 ≤ k . \mathbb{E}\lVert R\rVert_F^2=\frac{1}{k}\sum_{r=1}^{k}\lVert T_r^{\mathrm{ret}}\rVert_F^2\le k. E ∥ R ∥ F 2 = k 1 r = 1 ∑ k ∥ T r ret ∥ F 2 ≤ k . A restriction on the shared index only deletes nonnegative terms. This is an inequality because coordinates have now been removed; the earlier second-moment equality concerned the unrestricted tensor. Determinant AM–GM bounds each branch by one, proving the total replacement error
( 1 + ξ ) m 0 − 1. (73) (1+\xi)^{m_0}-1. \tag*{(73)} ( 1 + ξ ) m 0 − 1. (73) In the main branch every nonshared factor is restricted to its common good set. Therefore the collections ( Y r , a ) a (Y_{r,a})_a ( Y r , a ) a
The shared factor and the surviving rectangles
The independent-factor replacements have made each row a multilinear function of Gaussian vectors. Positive Gaussian degree allows us to compare the remaining shared factor by covariance averaging, without another central-limit argument.
Lemma C.5 (Shared-factor comparison). Fix k ≥ 2 k\ge2 k ≥ 2 M 1 ≥ 1 M_1\ge1 M 1 ≥ 1 ϵ s h > 0 \epsilon_{\mathrm{sh}}>0 ϵ sh > 0 δ 1 > 0 \delta_1>0 δ 1 > 0 k × k k\times k k × k X r , a X_{r,a} X r , a D ≥ 1 D\ge1 D ≥ 1 r r r D D D a a a ( X r , a ) a (X_{r,a})_a ( X r , a ) a
max a E ∥ X r , a ∥ F 2 ≤ δ 1 2 N , ∑ a E ∥ X r , a ∥ F 2 ≤ M 1 2 N . \max_a\mathbb{E}\lVert X_{r,a}\rVert_F^2\le\frac{\delta_1^2}{N},\qquad\sum_a\mathbb{E}\lVert X_{r,a}\rVert_F^2\le\frac{M_1^2}{N}. a max E ∥ X r , a ∥ F 2 ≤ N δ 1 2 , a ∑ E ∥ X r , a ∥ F 2 ≤ N M 1 2 . For independent U a ∼ U k U_a\sim U_k U a ∼ U k
Y r , : : = N ∑ a e r T U a X r , a , Σ : = ∑ a E ( X r , a ∗ X r , a ) . Y_{r,:}:=\sqrt{N}\sum_a e_r^{\mathsf T}U_aX_{r,a},\qquad\Sigma:=\sum_a\mathbb{E}(X_{r,a}^{*}X_{r,a}). Y r , : := N a ∑ e r T U a X r , a , Σ := a ∑ E ( X r , a ∗ X r , a ) . Then
E ∣ det Y ∣ 2 / k ≤ N a k det ( Σ ) 1 / k + ϵ s h ≤ N a k k tr Σ + ϵ s h . (74) \mathbb{E}\lvert\det Y\rvert^{2/k}\le N a_k\det(\Sigma)^{1/k}+\epsilon_{\mathrm{sh}}\le\frac{N a_k}{k}\operatorname{tr}\Sigma+\epsilon_{\mathrm{sh}}. \tag*{(74)} E ∣ det Y ∣ 2/ k ≤ N a k det ( Σ ) 1/ k + ϵ sh ≤ k N a k tr Σ + ϵ sh . (74) The choice of δ 1 \delta_1 δ 1 N N N D D D
Proof Step 1: average the covariances of independent Gaussian mixtures. For PSD row covariances define
Ψ ( S 1 , … , S k ) : = E ∣ det [ g 1 S 1 1 / 2 ⋮ g k S k 1 / 2 ] ∣ 2 / k , \Psi(S_1,\ldots,S_k):=\mathbb{E}\left|\det\begin{bmatrix}g_1S_1^{1/2}\\ \vdots\\ g_kS_k^{1/2}\end{bmatrix}\right|^{2/k}, Ψ ( S 1 , … , S k ) := E det g 1 S 1 1/2 ⋮ g k S k 1/2 2/ k , where the g r g_r g r R r R_r R r S r : = E ( R r ∗ R r ) S_r:=\mathbb{E}(R_r^*R_r) S r := E ( R r ∗ R r )
E ∣ det R ∣ 2 / k ≤ Ψ ( S 1 , … , S k ) . (75) \mathbb{E}|\det R|^{2/k}\leq\Psi(S_1,\ldots,S_k). \tag*{(75)} E ∣ det R ∣ 2/ k ≤ Ψ ( S 1 , … , S k ) . (75) Indeed, condition on all rows but one and expand the determinant as a linear form in that row. If its covariance in the mixture is K K K μ 2 / k ( z ∗ K z ) 1 / k \mu_{2/k}(z^*Kz)^{1/k} μ 2/ k ( z ∗ K z ) 1/ k z z z E K ( z ∗ K z ) 1 / k ≤ ( z ∗ S r z ) 1 / k \mathbb{E}_K(z^*Kz)^{1/k}\leq(z^*S_rz)^{1/k} E K ( z ∗ K z ) 1/ k ≤ ( z ∗ S r z ) 1/ k S r S_r S r Ψ \Psi Ψ Ψ \Psi Ψ
Step 2: condition on the cyclic shifts. Write U a = diag ( ε a , 1 , … , ε a , k ) C t a U_a=\operatorname{diag}(\varepsilon_{a,1},\ldots,\varepsilon_{a,k})C_{t_a} U a = diag ( ε a , 1 , … , ε a , k ) C t a t : = ( t a ) a t:=(t_a)_a t := ( t a ) a Y Y Y r r r D ≥ 1 D\geq1 D ≥ 1
Step 3: control covariance fluctuations. For deterministic PSD matrices
B a , j : = E ( X r , a ∗ e j e j ∗ X r , a ) , b a : = ∑ j tr B a , j = E ∥ X r , a ∥ F 2 , B_{a,j}:=\mathbb{E}(X_{r,a}^*e_je_j^*X_{r,a}),\qquad b_a:=\sum_j\operatorname{tr}B_{a,j}=\mathbb{E}\|X_{r,a}\|_F^2, B a , j := E ( X r , a ∗ e j e j ∗ X r , a ) , b a := j ∑ tr B a , j = E ∥ X r , a ∥ F 2 , which do not depend on r r r
S r ( t ) = N ∑ a B a , π t a ( r ) , S 0 : = E t S r ( t ) = N Σ / k . S_r(t)=N\sum_a B_{a,\pi_{t_a}(r)},\qquad S_0:=\mathbb{E}_tS_r(t)=N\Sigma/k. S r ( t ) = N a ∑ B a , π t a ( r ) , S 0 := E t S r ( t ) = N Σ/ k . By (C.26), E [ ∣ det Y ∣ 2 / k ∣ t ] ≤ Ψ ( S 1 ( t ) , … , S k ( t ) ) \mathbb{E}[|\det Y|^{2/k}\mid t]\leq\Psi(S_1(t),\ldots,S_k(t)) E [ ∣ det Y ∣ 2/ k ∣ t ] ≤ Ψ ( S 1 ( t ) , … , S k ( t )) ∥ B ∥ F ≤ tr B \|B\|_F\leq\operatorname{tr}B ∥ B ∥ F ≤ tr B B B B
E t ∥ S r ( t ) − S 0 ∥ F 2 ≤ N 2 k ∑ a , j ∥ B a , j ∥ F 2 ≤ N 2 k ∑ a b a 2 ≤ δ 1 2 M 1 2 k . (76) \begin{aligned}
\mathbb{E}_t\|S_r(t)-S_0\|_F^2\leq\frac{N^2}{k}\sum_{a,j}\|B_{a,j}\|_F^2 \\
&\leq\frac{N^2}{k}\sum_a b_a^2\leq\frac{\delta_1^2M_1^2}{k}. \tag*{(76)}
\end{aligned} E t ∥ S r ( t ) − S 0 ∥ F 2 ≤ k N 2 a , j ∑ ∥ B a , j ∥ F 2 ≤ k N 2 a ∑ b a 2 ≤ k δ 1 2 M 1 2 . (76) For every choice of shifts, ∑ r tr S r ( t ) = N tr Σ ≤ M 1 2 \sum_r\operatorname{tr}S_r(t)=N\operatorname{tr}\Sigma\leq M_1^2 ∑ r tr S r ( t ) = N tr Σ ≤ M 1 2
e ( t ) : = max r ∥ S r ( t ) − S 0 ∥ op . e(t):=\max_r\|S_r(t)-S_0\|_{\operatorname{op}}. e ( t ) := r max ∥ S r ( t ) − S 0 ∥ op . Consequently,
0 ≤ e ( t ) ≤ M 1 2 , E t e ( t ) 2 ≤ δ 1 2 M 1 2 . 0\leq e(t)\leq M_1^2,\qquad\mathbb{E}_te(t)^2\leq\delta_1^2M_1^2. 0 ≤ e ( t ) ≤ M 1 2 , E t e ( t ) 2 ≤ δ 1 2 M 1 2 . For the first bound, the norm of a difference of PSD matrices is at most the larger of their operator norms; for the second, use (C.27) and sum over r r r
Step 4: convert covariance error into determinant error. Since S r ( t ) ⪯ S 0 + e ( t ) I S_r(t)\preceq S_0+e(t)I S r ( t ) ⪯ S 0 + e ( t ) I
Ψ ( S 1 ( t ) , … , S k ( t ) ) ≤ k a k det ( S 0 + e ( t ) I ) 1 / k . \Psi(S_1(t),\ldots,S_k(t))\leq k a_k\det(S_0+e(t)I)^{1/k}. Ψ ( S 1 ( t ) , … , S k ( t )) ≤ k a k det ( S 0 + e ( t ) I ) 1/ k . All eigenvalues of S 0 S_0 S 0 M 1 2 / k M_1^2/k M 1 2 / k e ≤ M 1 2 e\leq M_1^2 e ≤ M 1 2
0 ≤ det ( S 0 + e I ) − det S 0 ≤ k e ( 2 M 1 2 ) k − 1 . 0\leq\det(S_0+eI)-\det S_0\leq ke(2M_1^2)^{k-1}. 0 ≤ det ( S 0 + e I ) − det S 0 ≤ k e ( 2 M 1 2 ) k − 1 . Apply ( x + y ) 1 / k − x 1 / k ≤ y 1 / k (x+y)^{1/k}-x^{1/k}\le y^{1/k} ( x + y ) 1/ k − x 1/ k ≤ y 1/ k E e 1 1 / k ≤ ( E e 2 ) 1 / ( 2 k ) \mathbb{E}e_1^{1/k}\le(\mathbb{E}e_2)^{1/(2k)} E e 1 1/ k ≤ ( E e 2 ) 1/ ( 2 k ) a k ≤ 1 a_k\le1 a k ≤ 1 δ 1 \delta_1 δ 1
E ∣ det Y ∣ 2 / k ≤ N a k det ( Σ ) 1 / k + C k M 1 2 − 1 / k δ 1 1 / k , C k : = k ( k 2 k − 1 ) 1 / k . (77) \mathbb{E}|\det Y|^{2/k}\le Na_k\det(\Sigma)^{1/k}+C_kM_1^{2-1/k}\delta_1^{1/k},\qquad C_k:=k(k2^{k-1})^{1/k}. \tag*{(77)} E ∣ det Y ∣ 2/ k ≤ N a k det ( Σ ) 1/ k + C k M 1 2 − 1/ k δ 1 1/ k , C k := k ( k 2 k − 1 ) 1/ k . (77) Choose δ 1 \delta_1 δ 1 ϵ s h \epsilon_{\mathrm{sh}} ϵ sh det ( Σ ) 1 / k ≤ tr Σ / k \det(\Sigma)^{1/k}\le\operatorname{tr}\Sigma/k det ( Σ ) 1/ k ≤ tr Σ/ k □ \square □
Application to the retained tensor. Apply the lemma to (C.23) at a good shared index j ∈ G h j\in\mathcal{G}_h j ∈ G h D = d − 1 D=d-1 D = d − 1 m j , a m_{j,a} m j , a E ∥ Y r , a ∥ F 2 = m j , a \mathbb{E}\|Y_{r,a}\|_{\mathrm{F}}^2=m_{j,a} E ∥ Y r , a ∥ F 2 = m j , a
∑ a m j , a ≤ k M 2 N , max a m j , a ≤ k d 0 2 N . \sum_a m_{j,a}\le\frac{kM^2}{N},\qquad\max_a m_{j,a}\le\frac{kd_0^2}{N}. a ∑ m j , a ≤ N k M 2 , a max m j , a ≤ N k d 0 2 . Thus take M 1 : = k M M_1:=\sqrt{k}M M 1 := k M k d 0 ≤ δ 1 \sqrt{k}d_0\le\delta_1 k d 0 ≤ δ 1 Σ j : = ∑ a E ( Y r , a ∗ Y r , a ) \Sigma_j:=\sum_a\mathbb{E}(Y_{r,a}^{*}Y_{r,a}) Σ j := ∑ a E ( Y r , a ∗ Y r , a ) Σ j \Sigma_j Σ j j j j
1 N ∑ j ∈ G h E ∣ det R ∣ 2 / k ≤ a k k ∑ j ∈ G h tr Σ j + ϵ s h = a k e ∅ + ϵ s h . (78) \frac{1}{N}\sum_{j\in\mathcal{G}_h}\mathbb{E}|\det R|^{2/k}\le\frac{a_k}{k}\sum_{j\in\mathcal{G}_h}\operatorname{tr}\Sigma_j+\epsilon_{\mathrm{sh}}=a_ke_{\varnothing}+\epsilon_{\mathrm{sh}}. \tag*{(78)} N 1 j ∈ G h ∑ E ∣ det R ∣ 2/ k ≤ k a k j ∈ G h ∑ tr Σ j + ϵ sh = a k e ∅ + ϵ sh . (78) For a bad shared index, no Gaussian approximation is needed. The second-moment identity gives E ∥ R ∥ F 2 = N tr Σ j \mathbb{E}\|R\|_{\mathrm{F}}^2=N\operatorname{tr}\Sigma_j E ∥ R ∥ F 2 = N tr Σ j j j j
1 N ∑ j ∉ G h E ∣ det R ∣ 2 / k ≤ 1 k ∑ j ∉ G h tr Σ j = e h . (79) \frac{1}{N}\sum_{j\notin\mathcal{G}_h}\mathbb{E}|\det R|^{2/k}\le\frac{1}{k}\sum_{j\notin\mathcal{G}_h}\operatorname{tr}\Sigma_j=e_h. \tag*{(79)} N 1 j ∈ / G h ∑ E ∣ det R ∣ 2/ k ≤ k 1 j ∈ / G h ∑ tr Σ j = e h . (79) The other factors have already been restricted to their good sets. Accordingly, the right side is the energy where only factor h h h F h ( T ) F_h(T) F h ( T ) h h h
F h ( T ) ≤ a k e ∅ + e h + E e r r , E e r r : = m 0 f 1 − 1 / k + ( 1 + ξ ) m 0 − 1 + ϵ s h . F_h(T)\le a_ke_{\varnothing}+e_h+E_{\mathrm{err}},\qquad E_{\mathrm{err}}:=m_0f^{1-1/k}+(1+\xi)m_0-1+\epsilon_{\mathrm{sh}}. F h ( T ) ≤ a k e ∅ + e h + E err , E err := m 0 f 1 − 1/ k + ( 1 + ξ ) m 0 − 1 + ϵ sh . Averaging orientations and applying (C.20) therefore yields
F ( T ) ≤ a k e ∅ + 1 d ∑ h e h + E e r r ≤ max { a k , 1 / d } + E e r r . (80) F(T)\le a_ke_{\varnothing}+\frac{1}{d}\sum_h e_h+E_{\mathrm{err}}\le\max\{a_k,1/d\}+E_{\mathrm{err}}. \tag*{(80)} F ( T ) ≤ a k e ∅ + d 1 h ∑ e h + E err ≤ max { a k , 1/ d } + E err . (80) Error budget and parameter order. The three terms in E e r r E_{\mathrm{err}} E err ϵ \epsilon ϵ ϵ / 6 \epsilon/6 ϵ /6 ϵ / 2 \epsilon/2 ϵ /2
Fix k k k d d d ϵ \epsilon ϵ M ≥ 1 M\ge1 M ≥ 1 τ H > 0 \tau_H>0 τ H > 0 m 0 ( 8 τ H + M − 2 ) 1 − 1 / k < ϵ / 6 m_0(8\tau_H+M^{-2})^{1-1/k}<\epsilon/6 m 0 ( 8 τ H + M − 2 ) 1 − 1/ k < ϵ /6
Choose 0 < ϵ s h < ϵ / 6 0<\epsilon_{\mathrm{sh}}<\epsilon/6 0 < ϵ sh < ϵ /6 δ 1 \delta_1 δ 1 Lemma C.5 at M 1 : = k M M_1:=\sqrt{k}M M 1 := k M 0 < d H < 1 0<d_H<1 0 < d H < 1 k d H ≤ δ 1 \sqrt{k}d_H\le\delta_1 k d H ≤ δ 1
Choose ϵ S > 0 \epsilon_S>0 ϵ S > 0 ( 1 + ϵ S / μ 2 / k ) m 0 − 1 < ϵ / 6 (1+\epsilon_S/\mu^{2/k})m_0-1<\epsilon/6 ( 1 + ϵ S / μ 2/ k ) m 0 − 1 < ϵ /6 Lemma C.4 then supplies M S , τ S , d S M_S,\tau_S,d_S M S , τ S , d S
Invoke the source theorem once, with parameters satisfying
τ ≤ min { τ H , τ S , 1 / 2 } , \tau\le\min\{\tau_H,\tau_S,1/2\}, τ ≤ min { τ H , τ S , 1/2 } , δ 0 ≤ min { d H / 2 , d S / 2 , 1 / 2 } , \delta_0\le\min\{d_H/2,d_S/2,1/2\}, δ 0 ≤ min { d H /2 , d S /2 , 1/2 } , η ≤ min { ( 4 M ) − 1 , ( 4 M S ) − 1 , 1 / 2 } . \eta\le\min\{(4M)^{-1},(4M_S)^{-1},1/2\}. η ≤ min {( 4 M ) − 1 , ( 4 M S ) − 1 , 1/2 } . These parameters give the common good sets with coefficient threshold d 0 = d H d_0 = d_H d 0 = d H b s r c b_{\mathrm{src}} b src E e r r < ε / 2 E_{\mathrm{err}} < \varepsilon/2 E err < ε /2
Encoding and positive-definite observations
The analytic gaps are now established. We next check that the instances can be encoded and feasible outputs evaluated in polynomial time, then extend the gaps to positive-definite observations and the remaining powers. All parameters other than the source input size are fixed in the following bounds.
Rational projections and feasible outputs
Encoding the reduction. The source subspace is the kernel of an integer matrix whose entries belong to { 0 , 1 , − 1 } \{0,1,-1\} { 0 , 1 , − 1 } D D D I I I
Π W = I − D T ( D D T ) − 1 D . (81) \Pi_W = I - D^{T}(DD^{T})^{-1}D. \tag*{(81)} Π W = I − D T ( D D T ) − 1 D . (81) The entries of D D T DD^{T} D D T k ( N b s r c ) d k(N_{\mathrm{bsrc}})^d k ( N bsrc ) d d N 1 + k ( d − 1 ) dN^{1+k(d-1)} d N 1 + k ( d − 1 ) Π W \Pi_W Π W k k k d d d
Representing a feasible output. A full-column-rank rational matrix R ∈ F n × k R \in\mathbb{F}^{n \times k} R ∈ F n × k P : = R ( R ∗ R ) − 1 / 2 P := R(R^{*}R)^{-1/2} P := R ( R ∗ R ) − 1/2
det ( P ∗ A i P ) 1 / k = ( det ( R ∗ A i R ) det ( R ∗ R ) ) 1 / k . (82) \det(P^{*}A_iP)^{1/k} =
\left(\frac{\det(R^{*}A_iR)}{\det(R^{*}R)}\right)^{1/k}. \tag*{(82)} det ( P ∗ A i P ) 1/ k = ( det ( R ∗ R ) det ( R ∗ A i R ) ) 1/ k . (82) Evaluating to promise-gap accuracy. The determinants in the ratio are rational and can be computed exactly; in particular, zero volumes are detected exactly. For fixed rational nonzero p p p p = 0 p=0 p = 0 k k k p ≤ 0 p \le0 p ≤ 0
Distinguishing the promise cases. A deterministic improvement on the hardness factor would therefore imply P = NP. A randomized polynomial-time algorithm returning a feasible rational subspace with an improved factor with probability at least 2 / 3 2/3 2/3 N P ⊆ R P \mathrm{NP} \subseteq\mathrm{RP} NP ⊆ RP
At p = 1 p=1 p = 1 k k k N P ⊈ B P P \mathrm{NP} \not\subseteq\mathrm{BPP} NP ⊆ BPP
Continuity at the nonzero powers used in the reductions
The perturbation below first bounds the change in each volume score. This elementary continuity estimate converts that bound into a change in the objective.
Lemma C.6 (Equal-weight continuity) Let p ≤ 1 p \le1 p ≤ 1 p ≠ 0 p \ne0 p = 0 x ∈ [ 0 , H ] m x \in[0,H]^m x ∈ [ 0 , H ] m y ≥ 0 y \ge0 y ≥ 0 ∥ x − y ∥ ∞ ≤ t ≤ 1 \lVert x-y\rVert_\infty\le t \le1 ∥ x − y ∥ ∞ ≤ t ≤ 1
∣ Mean p [ x ] − Mean p [ y ] ∣ ≤ { m − 1 / p t , p < 0 , ( H + 1 ) 1 − p t p / p , 0 < p < 1 , t , p = 1. (83) \left|\operatorname{Mean}_p[x]-\operatorname{Mean}_p[y]\right|
\le
\begin{cases}
m^{-1/p}t, & p<0,\\
(H+1)^{1-p}t^p/p, & 0<p<1,\\
t, & p=1.
\end{cases} \tag*{(83)} ∣ Mean p [ x ] − Mean p [ y ] ∣ ≤ ⎩ ⎨ ⎧ m − 1/ p t , ( H + 1 ) 1 − p t p / p , t , p < 0 , 0 < p < 1 , p = 1. (83) Proof For positive coordinates and p < 0 p<0 p < 0 z i : = x i p z_i:=x_i^p z i := x i p
∑ i ∂ Mean p ∂ x i = m − 1 / p ∑ i z i 1 − 1 / p ( ∑ i z i ) 1 − 1 / p ≤ m − 1 / p . \sum_i \frac{\partial\operatorname{Mean}_p}{\partial x_i}
=
m^{-1/p}\frac{\sum_i z_i^{1-1/p}}{\left(\sum_i z_i\right)^{1-1/p}}
\le m^{-1/p}. i ∑ ∂ x i ∂ Mean p = m − 1/ p ( ∑ i z i ) 1 − 1/ p ∑ i z i 1 − 1/ p ≤ m − 1/ p . Integrate along a segment and extend continuously to zero coordinates. For 0 < p < 1 0<p<1 0 < p < 1 ∣ a p − b p ∣ ≤ ∣ a − b ∣ p |a^p-b^p|\le|a-b|^p ∣ a p − b p ∣ ≤ ∣ a − b ∣ p 1 / p 1/p 1/ p [ 0 , ( H + 1 ) p ] [0,(H+1)^p] [ 0 , ( H + 1 ) p ] □ \square □
A polynomial-bit positive-definite perturbation
Fix − k β < p ≤ 1 -k\beta< p \le1 − k β < p ≤ 1 p ≠ 0 p \ne0 p = 0 A 1 , … , A m A_1,\ldots,A_m A 1 , … , A m A ^ i : = ( A i + t p d I ) / ( 1 + t p d ) \widehat{A}_i:=(A_i+t_{\mathrm{pd}}I)/(1+t_{\mathrm{pd}}) A i := ( A i + t pd I ) / ( 1 + t pd ) t p d I t_{\mathrm{pd}}I t pd I 1 + t p d 1+t_{\mathrm{pd}} 1 + t pd t p d t_{\mathrm{pd}} t pd
In the one-index construction, ∥ L i , U ∥ o p 2 ≤ b s r c \lVert L_{i,U}\rVert_{\mathrm{op}}^2 \le b_{\mathrm{src}} ∥ L i , U ∥ op 2 ≤ b src ∥ A i ∥ o p ≤ N b s r c \lVert A_i\rVert_{\mathrm{op}} \le Nb_{\mathrm{src}} ∥ A i ∥ op ≤ N b src b s r c d b_{\mathrm{src}}^d b src d Π \Pi Π
∥ L ∥ o p 2 ≤ k b s r c d , ∥ A i ∥ o p ≤ k ( N b s r c ) d . \lVert L\rVert_{\mathrm{op}}^2 \le kb_{\mathrm{src}}^d,\qquad
\lVert A_i\rVert_{\mathrm{op}} \le k(Nb_{\mathrm{src}})^d. ∥ L ∥ op 2 ≤ k b src d , ∥ A i ∥ op ≤ k ( N b src ) d . In either case choose the corresponding integer bound B B B 0 < t p d ≤ 1 0<t_{\mathrm{pd}}\le1 0 < t pd ≤ 1
A ^ i = A i + t p d I 1 + t p d . (84) \widehat{A}_i=\frac{A_i+t_{\mathrm{pd}}I}{1+t_{\mathrm{pd}}}. \tag*{(84)} A i = 1 + t pd A i + t pd I . (84) Every matrix is positive definite, every YES compression remains I k I_k I k ( Π + t p d I ) / ( 1 + t p d ) (\Pi+t_{\mathrm{pd}}I)/(1+t_{\mathrm{pd}}) ( Π + t pd I ) / ( 1 + t pd )
For an arbitrary frame, let a i : = det ( P ∗ A i P ) 1 / k ∈ [ 0 , B ] a_i:=\det(P^*A_iP)^{1/k}\in[0,B] a i := det ( P ∗ A i P ) 1/ k ∈ [ 0 , B ] [ 0 , B ] [0,B] [ 0 , B ]
0 ≤ det ( P ∗ A i P + t p d I ) − det ( P ∗ A i P ) ≤ k t p d ( B + 1 ) k − 1 . 0\le\det(P^*A_iP+t_{\mathrm{pd}}I)-\det(P^*A_iP)\le kt_{\mathrm{pd}}(B+1)^{k-1}. 0 ≤ det ( P ∗ A i P + t pd I ) − det ( P ∗ A i P ) ≤ k t pd ( B + 1 ) k − 1 . The inequality ( x + y ) 1 / k − x 1 / k ≤ y 1 / k (x+y)^{1/k}-x^{1/k}\le y^{1/k} ( x + y ) 1/ k − x 1/ k ≤ y 1/ k x , y ≥ 0 x,y\ge0 x , y ≥ 0
det ( P ∗ ( A i + t p d I ) P ) 1 / k ≤ a i + t , t : = [ k t p d ( B + 1 ) k − 1 ] 1 / k . (85) \det(P^{*}(A_i+t_{\mathrm{pd}}I)P)^{1/k}\le a_i+t,\qquad t:=\left[k t_{\mathrm{pd}}(B+1)^{k-1}\right]^{1/k}. \tag*{(85)} det ( P ∗ ( A i + t pd I ) P ) 1/ k ≤ a i + t , t := [ k t pd ( B + 1 ) k − 1 ] 1/ k . (85) Here t p d t_{\mathrm{pd}} t pd t t t 1 + t p d 1+t_{\mathrm{pd}} 1 + t pd Mean p [ a 1 + t , … , a m + t ] \operatorname{Mean}_p[a_1+t,\ldots,a_m+t] Mean p [ a 1 + t , … , a m + t ] Lemma C.6 , with H = B H=B H = B
To limit the objective increase to a prescribed fixed Δ > 0 \Delta>0 Δ > 0 t ≤ 1 t\le1 t ≤ 1
t ≤ { Δ m 1 / p , p < 0 , [ p Δ / ( B + 1 ) 1 − p ] 1 / p , 0 < p < 1 , Δ , p = 1 , 0 < t p d ≤ t k k ( B + 1 ) k − 1 . t\le
\begin{cases}
\Delta m^{1/p}, & p<0,\\
\left[p\Delta/(B+1)^{1-p}\right]^{1/p}, & 0<p<1,\\
\Delta, & p=1,
\end{cases}
\qquad
0<t_{\mathrm{pd}}\le\frac{t^k}{k(B+1)^{k-1}}. t ≤ ⎩ ⎨ ⎧ Δ m 1/ p , [ p Δ/ ( B + 1 ) 1 − p ] 1/ p , Δ , p < 0 , 0 < p < 1 , p = 1 , 0 < t pd ≤ k ( B + 1 ) k − 1 t k . A sufficiently small dyadic t p d t_{\mathrm{pd}} t pd p p p m m m B + 1 B+1 B + 1 Δ \Delta Δ
Zero power and the negative boundary
The remaining cases of Theorem 5.1 follow by power-mean monotonicity:
p ≤ p ′ ⟹ Mean p [ v i ] ≤ Mean p ′ [ v i ] . p\le p' \quad\Longrightarrow\quad\operatorname{Mean}_p[v_i]\le\operatorname{Mean}_{p'}[v_i]. p ≤ p ′ ⟹ Mean p [ v i ] ≤ Mean p ′ [ v i ] . We use an auxiliary power p ′ p' p ′
The geometric power. For p = 0 p=0 p = 0 0 < p ′ < 1 0<p'<1 0 < p ′ < 1 α k ( p ′ ) < α k ( 0 ) + ε / 2 \alpha_k(p')<\alpha_k(0)+\varepsilon/2 α k ( p ′ ) < α k ( 0 ) + ε /2 p ′ p' p ′ ε / 2 \varepsilon/2 ε /2 Mean 0 [ v i ] ≤ Mean p ′ [ v i ] ≤ α k ( 0 ) + ε \operatorname{Mean}_0[v_i]\le\operatorname{Mean}_{p'}[v_i]\le\alpha_k(0)+\varepsilon Mean 0 [ v i ] ≤ Mean p ′ [ v i ] ≤ α k ( 0 ) + ε
The negative boundary and lower powers. If the target power satisfies p ≤ − k β p\le-k\beta p ≤ − k β α k ( p ′ ) → 0 \alpha_k(p')\to0 α k ( p ′ ) → 0 p ′ ↓ − k β p'\downarrow-k\beta p ′ ↓ − k β 1 / p ′ 1/p' 1/ p ′ − k β < p ′ < 0 -k\beta<p'<0 − k β < p ′ < 0 α k ( p ′ ) < ε / 2 \alpha_k(p')<\varepsilon/2 α k ( p ′ ) < ε /2 ε / 2 \varepsilon/2 ε /2 Mean p [ v i ] ≤ Mean p ′ [ v i ] ≤ ε \operatorname{Mean}_p[v_i]\le\operatorname{Mean}_{p'}[v_i]\le\varepsilon Mean p [ v i ] ≤ Mean p ′ [ v i ] ≤ ε Theorem 5.1 ; Section C.4.3 also completes Theorem 5.2 .
Transfer to projection observations
Projective normalization separates a rank-k k k k k k k k k
Proof (of Lemma 5.3) Write A i = U i D i U i ∗ A_i=U_iD_iU_i^* A i = U i D i U i ∗ U i ∗ U i = I k U_i^*U_i=I_k U i ∗ U i = I k D i ≻ 0 D_i\succ0 D i ≻ 0
det ( P ∗ A i P ) = det ( D i ) ∣ det ( U i ∗ P ) ∣ 2 , \det(P^*A_iP)=\det(D_i)|\det(U_i^*P)|^2, det ( P ∗ A i P ) = det ( D i ) ∣ det ( U i ∗ P ) ∣ 2 , so v A i ( P ) = d i v Π i ( P ) v_{A_i}(P)=d_i v_{\Pi_i}(P) v A i ( P ) = d i v Π i ( P ) d i = det ( D i ) 1 / k d_i=\det(D_i)^{1/k} d i = det ( D i ) 1/ k p ≠ 0 p\ne0 p = 0
S : = ∑ i w i d i p , w ~ i : = w i d i p S S:=\sum_i w_i d_i^p,\qquad\widetilde{w}_i:=\frac{w_i d_i^p}{S} S := i ∑ w i d i p , w i := S w i d i p gives
Mean p , w [ ν A i ( P ) p ] = S 1 / p Mean p , w ~ [ ν Π i ( P ) p ] . \operatorname{Mean}_{p,w}\left[\sqrt[p]{\nu A_i(P)}\right] = S^{1/p}\operatorname{Mean}_{p,\widetilde{w}}\left[\sqrt[p]{\nu\Pi_i(P)}\right]. Mean p , w [ p ν A i ( P ) ] = S 1/ p Mean p , w [ p ν Π i ( P ) ] . For p = 0 p = 0 p = 0 ∏ i d i w i \prod_i d_i^{w_i} ∏ i d i w i P P P V i V_i V i Π i = V i ( V i ∗ V i ) − 1 V i ∗ \Pi_i = V_i(V_i^*V_i)^{-1}V_i^* Π i = V i ( V i ∗ V i ) − 1 V i ∗ e k ( A i ) e_k(A_i) e k ( A i )
For completeness, if each unnormalized weight is approximated within e ± σ e^{\pm\sigma} e ± σ e ± 2 σ e^{\pm2\sigma} e ± 2 σ e − 2 σ / ∣ p ∣ e^{-2\sigma/|p|} e − 2 σ /∣ p ∣ e 2 σ / ∣ p ∣ e^{2\sigma/|p|} e 2 σ /∣ p ∣ e − 4 σ / ∣ p ∣ e^{-4\sigma/|p|} e − 4 σ /∣ p ∣ □ \square □
Proof (of Theorem 5.4). Suppose a polynomial-time algorithm has approximation factor ρ > α k ( p ) \rho> \alpha_k(p) ρ > α k ( p ) k k k ε > 0 \varepsilon> 0 ε > 0 k k k k k k k k k k k k
For p ≠ 0 p \ne0 p = 0 ε \varepsilon ε σ > 0 \sigma> 0 σ > 0
ρ e − 4 σ / ∣ p ∣ > α k ( p ) + ε . \rho e^{-4\sigma/|p|} > \alpha_k(p) + \varepsilon. ρ e − 4 σ /∣ p ∣ > α k ( p ) + ε . Projective normalization, with the rational weights described above, loses at most the displayed exponential factor in an approximation ratio. Return the projection algorithm’s subspace in the unchanged original ambient space and evaluate its original objective. On a successful YES run this value exceeds the source NO bound, whereas no feasible output can do so on a NO instance. The certified gap evaluation in Section C.4 therefore distinguishes the source promise. At p = 0 p = 0 p = 0 □ \square □
This transfer preserves approximation-ratio hardness. It need not preserve identity YES compressions, equal weights away from zero, or a projection-valued average observation.
Two-view computation and Martin guarantees
The two-view purification proof is in § 6.1 . This appendix supplies the numerical details for Corollary 6.2 and the Martin consequences in § 7 .
Exactness for increasing aggregates
Proof (of Corollary 6.2). A frame projection Y : = P P ∗ Y := PP^* Y := P P ∗ Y Y Y G G G
For the stated power means the relaxed objective is concave: each determinant root is concave, and Mean p , w \operatorname{Mean}_{p,w} Mean p , w p ≤ 1 p \le1 p ≤ 1 p p p □ \square □
Precision for two-view purification
We prove the computational assertion of Corollary 6.2 using its concave PSD formulation. The case k = n k=n k = n 0 < ε < 1 / 2 0<\varepsilon<1/2 0 < ε < 1/2
A positive scale and a spectral floor. Let L L L k k k 2 − poly ( n , L ) 2^{-\operatorname{poly}(n,L)} 2 − poly ( n , L ) 2 poly ( n , L ) 2^{\operatorname{poly}(n,L)} 2 poly ( n , L ) d i : = e k ( A i ) 1 / k d_i:=e_k(A_i)^{1/k} d i := e k ( A i ) 1/ k
F ( Y ) : = Mean p , w [ d i det ( U i ∗ Y U i ) 1 / k ] , Y ⪰ 0 , tr Y = k . F(Y):=\operatorname{Mean}_{p,w}\left[d_i\det(U_i^*YU_i)^{1/k}\right],\qquad Y\succeq0,\quad\operatorname{tr}Y=k. F ( Y ) := Mean p , w [ d i det ( U i ∗ Y U i ) 1/ k ] , Y ⪰ 0 , tr Y = k . The central point Y 0 : = ( k / n ) I Y_0:=(k/n)I Y 0 := ( k / n ) I d i k / n d_i k/n d i k / n F ( Y 0 ) F(Y_0) F ( Y 0 ) p ≤ 1 p\le1 p ≤ 1
Put θ : = ε / 32 \theta:=\varepsilon/32 θ := ε /32 a : = θ k / n a:=\theta k/n a := θ k / n Y 0 Y_0 Y 0 θ \theta θ 1 − θ 1-\theta 1 − θ
Y ⪰ a I , tr Y = k . Y\succeq aI,\qquad\operatorname{tr}Y=k. Y ⪰ a I , tr Y = k . Every relaxed score there lies between d i a d_i a d i a d i d_i d i § 12 therefore finds a rational feasible Y Y Y
F ( Y ) ≥ ( 1 − 2 θ ) OPT p , k , F(Y)\ge(1-2\theta)\operatorname{OPT}_{p,k}, F ( Y ) ≥ ( 1 − 2 θ ) OPT p , k , using a number of bits and operations polynomial in n n n L L L log ( 1 / ε ) \log(1/\varepsilon) log ( 1/ ε ) Y 0 Y_0 Y 0
Stable evaluation for input powers. A rational full-rank basis R i R_i R i A i A_i A i
det ( U i ∗ Y U i ) = det ( R i ∗ Y R i ) det ( R i ∗ R i ) . \det(U_i^*YU_i)=\frac{\det(R_i^*YR_i)}{\det(R_i^*R_i)}. det ( U i ∗ Y U i ) = det ( R i ∗ R i ) det ( R i ∗ Y R i ) . Thus evaluating the objective and its derivatives requires no irrational input frame. The determinant in the denominator and e k ( A i ) e_k(A_i) e k ( A i )
For clarity, this cost remains polynomial for arbitrarily negative rational p p p e ℓ i e^{\ell_i} e ℓ i ℓ min : = min i ℓ i \ell_{\min}:=\min_i\ell_i ℓ m i n := min i ℓ i p < 0 p<0 p < 0
log F ( Y ) = ℓ min + 1 p log ( ∑ i w i e p ( ℓ i − ℓ min ) ) . \log F(Y)=\ell_{\min}+\frac{1}{p}\log\left(\sum_i w_i e^{p(\ell_i-\ell_{\min})}\right). log F ( Y ) = ℓ m i n + p 1 log ( i ∑ w i e p ( ℓ i − ℓ m i n ) ) . The exponentials are at most one and their weighted sum is at least w min > 0 w_{\min}>0 w m i n > 0 max ( 1 , ∣ p ∣ ) \max(1,|p|) max ( 1 , ∣ p ∣ ) O ( log ( 2 + ∣ p ∣ ) ) O(\log(2+|p|)) O ( log ( 2 + ∣ p ∣ )) w i e p ℓ i / ∑ j w j e p ℓ j w_i e^{p\ell_i}/\sum_jw_je^{p\ell_j} w i e p ℓ i / ∑ j w j e p ℓ j § 12 avoid cancellation; their additional precision is polynomial in the encoding length of p p p ∑ i w i ℓ i \sum_iw_i\ell_i ∑ i w i ℓ i
Principal vectors to certified precision. Principal vectors can be computed by standard singular-value methods [10 ] . Here is the bit-precision justification needed for rational input. The squared principal cosines are the eigenvalues of the generalized Hermitian problem
R 1 ∗ Π 2 R 1 z = λ R 1 ∗ R 1 z , Π 2 : = R 2 ( R 2 ∗ R 2 ) − 1 R 2 ∗ . R_1^{*}\Pi_2R_1z=\lambda R_1^{*}R_1z,\qquad\Pi_2:=R_2(R_2^{*}R_2)^{-1}R_2^{*}. R 1 ∗ Π 2 R 1 z = λ R 1 ∗ R 1 z , Π 2 := R 2 ( R 2 ∗ R 2 ) − 1 R 2 ∗ . Its characteristic polynomial has degree at most k k k 2 − poly ( n , L ) 2^{-\operatorname{poly}(n,L)} 2 − poly ( n , L )
For 0 < λ < 1 0<\lambda<1 0 < λ < 1 u u u
v : = Π 2 u / λ , f : = ( v − λ u ) / 1 − λ . v:=\Pi_2u/\sqrt{\lambda},\qquad f:=(v-\sqrt{\lambda}u)/\sqrt{1-\lambda}. v := Π 2 u / λ , f := ( v − λ u ) / 1 − λ . The divisors have polynomial-bit lower bounds. Eigenvalues zero and one use orthogonal and common subspaces directly. The same reasoning applies over C \mathbb{C} C
Purification and rational output. Apply the block construction from the main proof to the computed Y Y Y a a a a a a k k k W W W
det ( U i ∗ W W ∗ U i ) ≥ det ( U i ∗ Y U i ) ≥ a k , i = 1 , 2. \det(U_i^{*}WW^{*}U_i)\ge\det(U_i^{*}YU_i)\ge a^k,\qquad i=1,2. det ( U i ∗ W W ∗ U i ) ≥ det ( U i ∗ Y U i ) ≥ a k , i = 1 , 2. Each compression eigenvalue is at most one, so its smallest eigenvalue is also at least a k a^k a k log ( 1 / a k ) = k log ( 1 / a ) \log(1/a^k)=k\log(1/a) log ( 1/ a k ) = k log ( 1/ a ) log ( 1 / ε ) \log(1/\varepsilon) log ( 1/ ε )
Approximate W W W B o u t B_{\mathrm{out}} B out B o u t ( B o u t ∗ B o u t ) − 1 B o u t ∗ B_{\mathrm{out}}(B_{\mathrm{out}}^{*}B_{\mathrm{out}})^{-1}B_{\mathrm{out}}^{*} B out ( B out ∗ B out ) − 1 B out ∗ W W ∗ WW^{*} W W ∗ θ \theta θ a k a^k a k p p p
e − θ ( 1 − 2 θ ) OPT p , k ≥ ( 1 − 3 θ ) OPT p , k ≥ ( 1 − ε ) OPT p , k . e^{-\theta}(1-2\theta)\operatorname{OPT}_{p,k}\ge(1-3\theta)\operatorname{OPT}_{p,k}\ge(1-\varepsilon)\operatorname{OPT}_{p,k}. e − θ ( 1 − 2 θ ) OPT p , k ≥ ( 1 − 3 θ ) OPT p , k ≥ ( 1 − ε ) OPT p , k . This proves the stated deterministic running time and relative accuracy for a rational output basis.
The additive Martin guarantees
Use the projection identity (7.2) to pass to dimension s : = min ( k , n − k ) s:=\min(k,n-k) s := min ( k , n − k ) W i W_i W i k ≤ n / 2 k\le n/2 k ≤ n /2
The optimal loss is finite for every finite observation family: a standard Gaussian matrix has nonsingular compression to each observation space almost surely, and column normalization preserves this property. In the effective dimension, the relaxation has the logarithmic form
min Y ⪰ 0 − ∑ i w i log det ( W i ∗ Y W i ) . tr Y = s (86) \underset{Y \succeq0}{\operatorname{min}}\;-\sum_i w_i \log\det(W_i^*YW_i).
\quad\text{tr }Y=s \tag*{(86)} Y ⪰ 0 min − i ∑ w i log det ( W i ∗ Y W i ) . tr Y = s (86) It is the geometric-mean relaxation after the substitution Y : = s X Y := sX Y := s X
Proof (of Theorem 7.1) Apply Theorem 3.2 to the effective s s s α s ( 0 ) \alpha_s(0) α s ( 0 ) − s -s − s
For the finite-dimensional refinement, apply Theorem 4.2 to the same observations. Put b : = α n , s ( 0 ) b := \alpha_{n,s}(0) b := α n , s ( 0 ) c ≤ b c \le b c ≤ b
ζ : = c min { ε , 1 } 2 s . \zeta:= \frac{c\min\{\varepsilon,1\}}{2s}. ζ := 2 s c min { ε , 1 } . The returned geometric mean is at least b − ζ b-\zeta b − ζ ζ / b ≤ 1 / 2 \zeta/b \le1/2 ζ / b ≤ 1/2
− s log ( b − ζ ) = − s log b − s log ( 1 − ζ / b ) ≤ Δ s , n + ε . -s\log(b-\zeta)=-s\log b-s\log(1-\zeta/b)\le\Delta_{s,n}+\varepsilon. − s log ( b − ζ ) = − s log b − s log ( 1 − ζ / b ) ≤ Δ s , n + ε . Thus 1 / ζ 1/\zeta 1/ ζ s s s max ( 1 , 1 / ε ) \max(1,1/\varepsilon) max ( 1 , 1/ ε ) Δ s , n \Delta_{s,n} Δ s , n
Finally, an additive guarantee Δ k − ε \Delta_k-\varepsilon Δ k − ε
exp ( − ( Δ k − ε ) / k ) > α k ( 0 ) . \exp\left(-(\Delta_k-\varepsilon)/k\right)>\alpha_k(0). exp ( − ( Δ k − ε ) / k ) > α k ( 0 ) . Theorem 5.4 excludes this improvement even for equally weighted rational projection observations. At k = n k=n k = n
The explicit two-view Martin solution
Proof (of Proposition 7.2) Apply Theorem 6.1 to Y : = P P ∗ Y := PP^* Y := P P ∗ P P P [ 0 , ϕ j ] [0,\phi_j] [ 0 , ϕ j ]
w log cos θ + ( 1 − w ) log cos ( ϕ − θ ) . w\log\cos\theta+(1-w)\log\cos(\phi-\theta). w log cos θ + ( 1 − w ) log cos ( ϕ − θ ) . This function is strictly concave on its finite-loss interval. For 0 < ϕ < π / 2 0<\phi<\pi/2 0 < ϕ < π /2 w tan θ = ( 1 − w ) tan ( ϕ − θ ) w\tan\theta=(1-w)\tan(\phi-\theta) w tan θ = ( 1 − w ) tan ( ϕ − θ ) t : = tan θ t := \tan\theta t := tan θ T : = tan ϕ T := \tan\phi T := tan ϕ w T t 2 + t − ( 1 − w ) T = 0 wTt^2+t-(1-w)T=0 w T t 2 + t − ( 1 − w ) T = 0 ϕ = 0 \phi=0 ϕ = 0 ϕ = π / 2 \phi=\pi/2 ϕ = π /2 w log cos θ + ( 1 − w ) log sin θ w\log\cos\theta+(1-w)\log\sin\theta w log cos θ + ( 1 − w ) log sin θ cos 2 θ = w \cos^2\theta=w cos 2 θ = w θ = ϕ / 2 \theta=\phi/2 θ = ϕ /2
