Organizations: Tri-institutional Center for Translational Research in Neuroimaging and Data Science (TReNDS), Georgia State University, Georgia Institute of Technology, Emory University, Atlanta, GA, USA · Huazhong University of Science and Technology, Wuhan, China · University of Pennsylvania, Philadelphia, PA, USA · Lancaster University, Lancaster, UK · Georgia Institute of Technology, Atlanta, GA, USA
Can independent components be recovered when all of them are Gaussian? Yes, if their variances change across environments; but how many environments, and how many samples as the number of components d grows? We answer both for the joint diagonalization of K covariances. Each component has a signature, its variances across the environments. Separating component j costs the Riesz 2-energy Ej of this signature, a sum, over the other components, of inverse pairwise Fisher informations. For Gaussian sources no estimator in O(d) beats cEj/(n+Ej) at any n and d, and above an explicit sample size a spectral estimator attains Ej/n up to a constant, for every mixing and without the signatures (given a lower bound on the pairwise information). Since signatures live in K−1 dimensions, the rate obeys a dimension law: d2/n, dlogd/n and d/n for K=2, 3 and K≥4 well-spread environments. What counts is the dimension the signatures span, not their number, and logd well-designed environments make dlogd samples suffice. Projecting the covariances onto one linear combination pays d2/n at first order instead. In simulations up to d=1000 the predictions hold and joint diagonalization with K≥4 attains the rate once n/d is in the hundreds; on task fMRI the energy says which components are hard to separate.
Figures & tables
Figure 1: Separation is a Riesz energy. (a) Each source is a point pi in the (K−1) -dimensional space of signatures; separating source j costs the inverse-square energy of its interactions (blue), which a quadratic pencil centred at pj measures, while a linear pencil ∑kαkΣk projects the signatures onto a line (red), where gaps are ∼1/d . (b) The dimension law, simulated: mean row error of joint diagonalization for random signatures at n=400d ; dashed: Eˉw/n (Proposition 2 ). (c) Eˉ/d for lattice signatures grows like d ( K=2 ) and logd ( K=3 ) and saturates ( K≥4 ). (d) Projecting versus probing: on identical data ( K=8 , n=400d ) the eigenvectors of one random linear pencil degrade with d ; joint diagonalization and the quadratic pencil of Theorem 2 do not. Details: Appendix J .
K=2
K=3
K≥4
K≍logd , sep.
sources
whitening
signatures
energy Ej (T 4 ; Sec. 4 )
d2
dlogd
d
d
(geometry of the signatures only)
necessary: n≳ (T 1 , C 2 )
d2
dlogd
d
d
Gaussian
known †
may be used
sufficient: ≍Eˉ/n for n≳ (T 2 , C 1 )
d3
d2
dK−1K+1
dlogd
Gaussian
known or est.
known
without signatures (T 3 )
d3
d2
dK−1K+1
dlogd
Gaussian
known or est.
s0≤Smin
one linear pencil (T 5 )
≳d2/n for every K
4th mom.
known
not used
joint diagonalization (P 2 )
≍Eˉ/n
4th mom.
known or est.
not used
Table 1: What is known about ℓA2 and under which conditions (T: Theorem, C: Corollary, P: Proposition). Orders in d for well-spread signatures (row 2: every configuration); constants depend on K , B and the spreading constants. The upper bounds (rows 3–4) are for equal environment sizes. Row 2: no estimator in O(d) has risk below cmin(1,fK(d)/n) , fK(d) the listed order; † any mixing for labelled estimators and under the matched loss (Corollary 1 ). Rows 2–4 are non-asymptotic, 5–6 first order at fixed d , 7 simulation ( Eˉ : Section 2 ; Eˉw : Section 5 ).
Figure 2: The mechanism. (a) Dimension, not number: K=8 , signatures well-spread (Halton points, fixed scale) in an affine subspace of dimension 1 , 2 , 3 or 7 ; n=1600d ; dashed: Eˉw/n . (b) Energy beats the smallest gap: two configurations with the same Smin ( K=4 , d=27 , n=400d ), a lattice (A) and a coarser lattice plus one close pair (B): simulated ℓA2 with standard errors, Eˉw/n and (d/n)/Smin . (c) Sample complexity: n/d at which the median ℓA2 reaches 0.1 ( K=4,8 ) or 0.3 ( K=2 ; triangle: not reached by n=1600d ), from Figure 8 , with 90% bootstrap intervals; dotted: the growth d2/(K−1) of the proved threshold, K=4 . (d) First order explains the curves: error divided by Eˉw/n at n=400d , per draw (draws: Appendix J ).
Figure 3: Real data (HCP task fMRI, d=200 ). (a) Split-half discrepancy δj=1−corr2 of each component between two disjoint groups of m subjects, against its first-order prediction (colour: subjects per half; dashed: y=x ; dotted: δ^=0.3 and δ=1 ). (b) Eˉ/d against d for two environments (rest and working memory; noise-limited), the seven tasks and rest, and eight rest segments.
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
Result (main text)
Full statement; proof
Sources; whitening; sizes
Signatures
Regime
Not covered
Theorem 1 , lower bound
Theorem B.1 (a); App. B
Gaussian; known; any
may be used; estimators in O(d) or labelled; d directions under the matched loss, average bound only (Lemma 5 )
every n , d
the per-source and maximal losses ρj , ℓM for non-orthogonal estimators
Theorem 1 , attainment at fixed d
Theorem B.1 (b); App. B
Gaussian; known; any
Sij>0
n→∞ , fixed d
the d -dependence
Theorem 2 (a), pencil, known whitening
Theorem C.1 (a); App. C
Gaussian; known; equal
known
γj≤c
unequal sizes (App. A )
Theorem 2 (b), estimated whitening
Theorem C.1 (b); App. C , Lemma 2
Gaussian; estimated on a third; equal
known
γj≤c
unequal sizes
Lemmas 3 , 4 , perturbed probes
App. C , D
Gaussian; known / estimated; equal
a probe within η/B4 of the nearest-neighbour distance ( η≤1/8 ), independent of the halves
γj≤c
Theorem 3 (a), grid, known whitening
Theorem D.1 (a); App. D
Gaussian; known; equal
only B and s0≤Smin
γ0≤c
adaptivity in s0 ; the grid is exponential in K
Appendix
Table 5
Figure 4: Algorithms, attainment and the lag route. (a) K=8 , n=400d , identical data for all methods (medians over three to six draws), error divided by the Riesz rate Eˉ/n (solid line at 1 ); dashed: EˉPC/Eˉ , the Cramér–Rao coefficient with estimated whitening; dotted: Eˉw/Eˉ . (b) Separated signatures ( K=16 balanced codes, Smin≥0.33 ): the estimator of Theorem 2 with known whitening (red) and Jacobi with estimated whitening (blue, d≤256 ) against n/d for d=64 to 512 (light to dark); dashed: Eˉqp/n . (c) SOBI with L lags on MA(8) sources, n=200d (medians and quartiles); AMUSE is L=1 . (d) Runs below n=100d ( K∈{4,8} , d∈{32,64,128} ): Jacobi continued to 1000 sweeps (filled) and Pham’s algorithm (open) against Eˉw/n ; crosses: a random orthogonal matrix.
K
d
Jacobi
FFDIAG
+step
Pham
Thm 2
pencil
Eˉw/n
EˉPC/n
Eˉ/n
8
16
21.0
21.0
20.1
20.9
34.6
471
19.8
18.2
17.6
8
32
18.4
18.5
16.7
16.6
32.6
545
18.1
16.7
16.0
8
64
20.3
20.3
18.4
18.3
32.1
666
19.8
18.2
17.5
8
128
20.1
20.2
18.5
18.4
32.0
779
19.5
17.9
17.3
8
256
20.6
20.6
18.9
18.8
33.2
842
20.4
18.8
18.1
4
16
37.4
37.5
36.4
36.7
72.5
366
34.1
31.9
31.0
Appendix
Table 2: Baselines on identical data, n=400d (means over draws, ×103 ); the estimator of Theorem 2 uses the known signatures and whitening, and the column gives the loss of its labelled vectors (Table 5 gives their polar factor).
n=200d
n=800d
departure
error
error / pred.
Spearman
error
error / pred.
Spearman
AR(1), ϕ= 0
45.0
1.12
0.73
10.4
1.04
0.69
AR(1), ϕ= 0.5
76.9
1.17
0.65
16.5
1.02
0.70
AR(1), ϕ= 0.8
479.1
2.65
0.54
51.0
1.11
0.66
mixing, ϵ= 0
43.3
1.09
0.71
10.5
1.02
0.73
mixing, ϵ= 0.01
46.6
1.17
0.70
10.4
1.05
0.67
Appendix
Table 3: The first-order prediction under departures from the model ( K=8 , d=64 , eight draws per cell, means): mean ℓA2 ( ×103 ), its ratio to the prediction (multiplied by τ for AR(1) sources), and the Spearman correlation between the predicted and the observed per-source errors.
Figure 5: Verification. (a) Energy per source for random signatures (medians over eleven draws): the average Eˉ/d (solid) saturates from K=4 on, the worst source Emax/d (dashed) only from K=5 on (Proposition 1 ); K=2 is off scale. (b) Simulated mean row error against the first-order prediction for K∈{3,4,8} , d∈{16,32} and n∈{400d,1600d} , one signature draw and six mixings each: filled markers use estimated whitening and Eˉw/n , open markers known whitening and EˉF/n ; dashed: identity. Points off the line are draws with a pair outside the first-order regime. (c) Gaussian, Laplace and uniform sources ( d=32 , K=8 , one signature draw, eight mixings each) give the same error from n=200d on, on top of Eˉw/n (dashed; ratios 1.03 , 1.01 and 1.11 at n=400d ) and above the Riesz rate Eˉ/n (dotted). (d) Attaining the Riesz rate (known whitening, K∈{4,8} , d∈{16,…,128} , n∈{400d,1600d} ): Algorithm 3 (open) sits at EˉF/n , above the Riesz rate; one Fisher-weighted step (filled) lands on it.
Figure 6: (a) Lattice signatures (Definition 1 ), n=400d , eight draws: the dimension law with the assumptions of Theorems 1 and 4 . (b) The estimator of Theorem 2 (known whitening) approaches its prediction Eˉqp/n as γ=Kd/(nSmin) decreases ( d=64 , four draws per point; diamonds: K=4 lattice, with ratio 1.03 to Eˉqp/n at γ=0.028 ; triangles: K=8 random signatures); dotted: the shape (1+γ)2 of ( 10 ). (c) Strong contrast ( B=10 , red) and unequal sizes (squares): Jacobi against Eˉw/n (filled) and Pham against EˉPC/n (open).
K
n/(Kd)
mean ℓA2
s.e.
Eˉw(K)/n
median ratio
participation ratio
converged
2
400
371.1
22.2
–
0.01
1.0
8/8
4
200
24.6
3.0
22.0
1.07
2.7
8/8
8
100
6.7
0.4
6.5
0.99
4.8
8/8
16
50
5.8
0.3
5.7
1.00
5.0
8/8
32
25
5.7
0.3
5.5
1.01
5.1
8/8
64
12.5
5.9
0.3
5.5
1.04
5.1
8/8
Appendix
Table 4: Segments of one nonstationary recording as environments ( d=32 , n=800d , eight draws): mean ℓA2 ( ×103 ) with its standard error, the median first-order prediction Eˉw(K)/n ( ×103 ; off scale for K=2 ), the median per-draw ratio, the participation ratio of the centred signature matrix, and the runs that met the tolerance.
Figure 7: Mean risk on fixed configurations, larger d . Mean ℓA2 with 95% intervals against d at n/d∈{100,200,400,800} ; dashed: Eˉw/n . (a) K=4 lattices, d=27 to 1000 . (b) One fixed draw of K=4 random signatures per d . (c) K=16 balanced codes. (d) n/d at which the mean error of the lattices reaches 0.1 and 0.2 (and 0.05 , reached within n≤800d only at d=64 ); dashed: the growth of Eˉw/d ; dotted: the growth d2/3 of the proved threshold.
Figure 8: Collapse in n/d . Median error against n/d for random signatures, K∈{2,4,8} and d from 16 (light) to 512 (dark; K=2 up to 128 ), ten draws per point ( d≤128 ), six ( d=256 ) or three ( d=512 ); dashed: Eˉw/n for the largest d . For K=4 and K=8 the curves coincide; for K=2 they move up with d .
K
d
γ
labelled
polar
+step
Eˉqp/n
Eˉ/n
polar /(Eˉ/n)
8
64
1.4
35.7
20.7
18.7
22.2
18.3
1.13
8
128
2.7
32.7
19.5
18.1
21.5
17.5
1.11
8
256
3.0
33.1
19.7
18.4
21.7
17.8
1.11
4
64
18.1
143.5
71.8
46.2
43.0
40.0
1.79
4
128
27.0
173.3
78.0
41.9
42.3
39.3
1.98
4
256
55.1
186.3
85.0
48.9
42.9
39.9
2.13
Appendix
Table 5: The estimator of Theorem 2 on random signatures, n=400d , three draws per row (means, ×103 ; γ : median): labelled vectors, their polar factor, and one Fisher step from it, with the first-order coefficient of the labelled vectors, the Riesz rate, and the ratio of the polar factor’s loss to the Riesz rate.
d
n/d
draws
γ
known
Eˉqp/nB
estimated
(Eˉqp+2Eˉwh)/nB
estimated / known
27
6400
40
0.22
7.99
7.28
8.81
7.43
1.103
27
25600
40
0.060
1.87
1.82
1.95
1.86
1.042
27
102400
40
0.016
0.464
0.455
0.478
0.465
1.029
27
409600
40
0.0043
0.114
0.114
0.117
0.116
1.023
64
6400
16
0.25
9.41
8.39
10.8
8.57
1.146
64
25600
16
0.065
2.15
2.10
2.25
2.14
1.050
Appendix
Table 6: Theorem 2 (b) in simulation: K=4 lattices, known signatures, n/3 observations per part. The estimator of Theorem 2 on parts 1 and 2 with the true whitening (known; loss 1−⟨q^j,qj⟩2 ) and with the whitening estimated on part 0 (estimated; loss ρj of Theorem 2 (b)): means of ℓA2 over the stated number of draws ( ×103 ), their first-order predictions with nB=2n/3 , and the ratio of the two means; γ=maxjγj .
d
n/d
all probes
probe error
grid
all runs
oracle
Eˉqp/nB
Eˉ/nB
selection (s)
27
1600
1/3
0.40
36.13
70.37
30.51
29.12
27.82
4
27
6400
3/3
0.18
6.86
6.86
6.84
7.28
6.95
3
27
25600
3/3
0.10
1.81
1.81
1.81
1.82
1.74
4
64
1600
0/3
–
–
62.01
34.79
33.58
32.29
23
64
6400
3/3
0.18
8.37
8.37
8.29
8.39
8.07
22
64
25600
3/3
0.08
2.06
2.06
2.06
2.10
2.02
22
Appendix
Table 7: A practical variant of Algorithm 2 (not a test of Theorem 3 ): K=4 lattices, three draws per row (two for d=216 ). All probes: runs in which the selection returns one probe per source; probe error: largest distance of a probe from its signature over the signature’s nearest-neighbour distance (median over those runs); grid and all runs: ℓA2 with the selected probes over those runs and over every run, failures included; oracle: true signatures, on the same data; losses and predictions ×103 , with nB=2n/3 the size of parts 1 and 2 ; selection: time on one core.
Figure 9: Real data: components ( d=200 ). (a) The components with the smallest and the largest predicted error ( nδ^j=734 and 350907 ): parcel loadings on the inflated cortical surface and task-variance signatures. (b) The hardest pair (components 72 and 179, Sij=0.0000570 ) has nearly identical signatures; between halves of m=50 subjects the matched ∣corr∣ of their estimates is 0.091 and the crossed one 0.071 .
Estimating the number of components is a fundamental challenge in unsupervised learning, particularly when dealing with high-dimensional data with many components or severely imbalanced component sizes. This paper addresses this challenge for classical Gaussian mixture models. The proposed estimator is simple: center the data, compute the singular values of the centered matrix, and count those above a threshold. No iterative fitting, no likelihood calculation, and no prior knowledge of the number of components are required. We prove that, under a mild separation condition on the component centers, the estimator consistently recovers the true number of components. The result holds in high-dimensional settings where the dimension can be much larger than the sample size. It also holds when the number of components grows to the smaller of the dimension and the sample size, even under severe imbalance among component sizes. Computationally, the method is extremely fast: for example, it processes ten million samples in one hundred dimensions within one minute. Extensive experimental studies confirm its accuracy in challenging settings such as high dimensionality, many components, and severe class imbalance.
Huan Qing
School of Economics and Finance, Chongqing University of Technology, Chongqing, 400054, Chongqing, China.
We study model-order selection and component-mean estimation for multidimensional Gaussian mixture models with a known common covariance matrix. Using empirical characteristic-function measurements, we construct Fourier covariance matrices whose population counterparts have rank equal to the number of mixture components. We establish a minimax lower bound showing that distinguishing a separated k-component mixture from the class of (k−1)-component mixtures requires Ω(Δ−(4k−4)) samples. We then develop an oracle spectral-thresholding estimator with a sufficient sample size of order Δ−(8k−8) for fixed k, together with a practical singular-value-ratio estimator. Given the model order, we estimate the component means by score-initialized gradient descent on a MUSIC-type projection objective. Under an explicit sample-size condition, a qualifying sample initialization lies in a certified attraction region with high probability, after which the iterates converge linearly. For fixed positive component separation, the resulting mean estimates achieve the parametric rate Op(n−1/2). Numerical experiments demonstrate competitive accuracy and lower computational cost than expectation-maximization across a range of multidimensional settings.
Xinyu Liu, Hai Zhang
Department of Mathematics, Hong Kong University of Science and Technology (HKUST) · HKUST-Shenzhen-Hong Kong Collaborative Innovation Research Institute
Kurtosis-based Independent Component Analysis (ICA) weakens in wide, balanced mixtures. We prove a sharp redundancy law: for a standardized projection with effective width Reff (participation ratio), the population excess kurtosis obeys ∣κ(y)∣=O(κmax/Reff), yielding the order-tight O(cbκmax/R) under balance (typically cb=O(logR)). As an impossibility screen, under standard finite-moment conditions for sample kurtosis estimation, surpassing the O(1/T) estimation scale requires R≲κmaxT. We also show that purification -- selecting m≪R sign-consistent sources -- restores R-independent contrast Ω(1/m), with a simple data-driven heuristic. Synthetic experiments validate the predicted decay, the T crossover, and contrast recovery.
Yuda Bi, Wenjun Xiao, Linhao Bai +1
Tri-Institutional Center for Translational Research in Neuroimaging and Data Science (TReNDS), Georgia State University, Georgia Institute of Technology, and Emory University, Atlanta, GA 30303 USA · Department of Computer Science, The George Washington University, Washington, DC 20052 USA · School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA 30332 USA