Introduction
Understanding how anatomical wiring governs coordinated functional activity in the brain remains a fundamental problem in computational neuroscience. This objective naturally motivates the study of two complementary representations of the brain connectome. Specifically, structural connectivity (SC), inferred from diffusion imaging, charts the physical pathways along which regions communicate, whereas functional connectivity (FC), derived from correlated activity fluctuations, captures the statistical dependence between regional signals [16 , 40 ] . Characterizing the relationship between SC and FC has emerged as a salient analytical task: it provides a principled framework to investigate
40th Conference on Neural Information Processing Systems (NeurIPS 2026). how anatomy constrains function, how individual variability manifests across modalities, and which subnetworks offer the most robust structural support for observed functional coordination [22 , 15 ] .
Meanwhile, the SC-FC relationship is intrinsically indirect and spatially heterogeneous [41 , 15 ] . An extensive body of literature demonstrates that functional connectivity is only partially constrained by direct anatomical pathways, and the cross-modal agreement varies systematically across cortical hierarchies, individuals, and developmental stages [22 , 42 , 4 , 51 , 17 ] . Specifically, while certain functional communities are anchored by a dense set of anatomical connections, others rely on diffuse or polysynaptic interactions [49 , 19 , 38 , 51 ] . Consequently, the most pronounced cross-modal signals are concentrated within localized subnetworks rather than distributed uniformly across the connectome [42 , 51 , 17 ] . Existing analytical approaches often summarize SC–FC coupling using a single connectome-wide correlation or region-wise scalar scores [22 , 42 , 4 ] . Global correlations obscure spatial variation, whereas region-wise scores characterize such variation without directly identifying a compact node set whose induced structural subgraph maximizes cross-modal concordance. To move beyond global and region-wise scalar summaries, we therefore seek a framework that identifies structural subnetworks with maximal SC–FC concordance within functional communities.
Extensive prior research has sought to characterize the relationship between structural and functional connectivity (SC-FC). Global correlation approaches [22 , 41 , 15 ] reduce the connectome to a single summary statistic, thereby failing to identify localized subnetworks. Predictive SC-to-FC models [22 , 1 , 41 ] aim to explain functional connectivity from structural connectivity, while graph-theoretic summaries [5 , 36 ] characterize network topology. These formulations do not directly target the joint estimation of a cross-modal alignment transformation and a sparse node set defining an induced structural subgraph. Subnetwork inference [50 ] , functional parcellation [49 , 10 ] , and regional SC–FC analysis [51 ] provide complementary tools for characterizing localized network organization. Here, SC and FC share anatomical node labels, and alignment relates latent functional geometry to a selected structural subgraph while preserving the anatomical identities of its nodes. In practice, leading functional gradients are often rotated or otherwise transformed relative to the structural connectome [29 , 42 , 46 , 17 ] . Consequently, a localized search that ignores this mismatch tends to recover the structurally densest subset rather than the subnetwork genuinely aligned with functional organization.
Our primary objective in this paper is to address this fundamental challenge: given paired SC and FC matrices across subjects, we aim to identify a sparse, interpretable set of brain regions whose induced structural subgraph is maximally concordant with the dominant functional organization. Specifically, the proposed methodology is designed to overcome the two primary limitations of existing SC-FC analyses. First, the relevant signal manifests at the subnetwork level. Concordance is an intrinsic property of a node set rather than of individual nodes. Consequently, a valid estimation procedure must jointly model the connection patterns of node sets instead of evaluating individual regions sequentially. Second, as FC and SC are typically embedded in disparate coordinate systems, the two modalities may differ by a nontrivial transformation that a purely localized search cannot adequately capture. Therefore, a rigorous methodological solution must explicitly account for this cross-modal mismatch to localize the target subnetwork, while simultaneously ensuring the statistical interpretability of the identified brain regions.
To address this methodological gap, we introduce Orthogonal Sparse Subgraph Alignment (OSSA) , a novel framework that integrates these dual requirements into a unified variational problem. Specifically, Ossa couples an orthogonal transformation component with a sparse subgraph selection component (Figure 1). The method jointly estimates an orthogonal transformation of the functional connectivity and a sparse node-selection vector, thereby inducing a structural subgraph that maximizes cross-modal concordance. The transformation component serves as a structure-aware alignment mechanism, absorbing the global coordinate mismatch between modalities while preserving the intrinsic geometry of the functional data. Concurrently, the sparse selection component directly encodes the combinatorial subgraph structure within the continuous optimization space. Together, these components extend the classical orthogonal Procrustes problem [37 ] to a setting where the alignment target is itself an unknown, induced subgraph of the structural connectome. More generally, OSSA addresses the joint alignment and localization of paired similarity representations on a common index set when both the transformation and the informative subset are unknown. Related settings include comparing learned representations with localized shared information and aligning embedding spaces with only a subset of reliable anchors.
Figure 1. Overview of the OSSA. (a) SC and FC are restricted to functional communities obtained from a spectral clustering of population-averaged FC. (b) Within a community, OSSA jointly learns an orthogonal FC alignment W W W and K K K sparse node-support masks. (c) Rounding each mask gives an induced SC subgraph. An overlap penalty controls whether the K K K supports collapse or separate.
To the best of our knowledge, OSSA represents the first principled statistical formulation for the cross-modal subnetwork identification problem in SC-FC analysis. The problem can be solved by a computationally efficient algorithm that seamlessly integrates the orthogonal alignment and sparse selection components. Furthermore, we establish theoretical guarantees for canonical OSSA within a fixed population community. Under the required conditions, a local maximizer exists near the population target, and every local maximizer in the specified neighborhood achieves exact support recovery and the finite-sample aligned functional projector error bound with high probability. The empirical utility of the proposed methodology is evaluated through extensive simulation experiments, which highlight its superior accuracy and robustness compared to conventional baseline methods. Finally, we apply OSSA to analyze multi-modal brain connectome data from the Adolescent Brain Cognitive Development (ABCD) study. Our analysis successfully extracts highly interpretable structural modules that tightly couple with functional organization, yielding novel scientific insights into the anatomical constraints of the developing human brain. The identified supports also remain highly consistent across the baseline and Year-2 follow-up releases, indicating that the dominant aligned cores are stable under longitudinal neurodevelopmental variation.
Orthogonal sparse subgraph alignment
Consider a study comprising n n n subjects, indexed by i ∈ { 1 , … , n } i \in\{1,\ldots,n\} i ∈ { 1 , … , n } . For each subject i i i , we observe a paired set of P × P P \times P P × P symmetric matrices, A i A_i A i and B i B_i B i , representing the functional connectivity (FC) and structural connectivity (SC) networks, respectively, defined on a common atlas of P P P brain regions. We assume that A i A_i A i and B i B_i B i have been preprocessed according to standard pipelines in brain connectome studies.
Communities. Let { C q } q = 1 Q \{C_q\}_{q=1}^{Q} { C q } q = 1 Q denote a partition of the atlas nodes derived from the training FC data. Each set C q C_q C q represents a module of brain regions, hereafter referred to as a functional community, which is assumed to be shared across all subjects. Such community structures are commonly studied in the context of functional connectivity patterns [18 , 7 ] . Let p q = ∣ C q ∣ p_q = \lvert C_q \rvert p q = ∣ C q ∣ denote the size of community q q q . Under the assumption of a multiple degree-corrected block structure, the algorithm proposed by [3 ] exactly identifies the communities C q C_q C q with high probability. Consequently, we condition our subsequent analysis on the successful recovery of these communities, and we formulate the OSSA objective within each FC-derived community. In practice, the community detection algorithm of [3 ] is applied prior to OSSA. Define A i , q A_{i,q} A i , q and B i , q B_{i,q} B i , q as the principal submatrices of A i A_i A i and B i B_i B i , respectively, induced by the node set C q C_q C q . For notational conciseness, when the context restricts focus to a single community, we suppress the subscript q q q and overload the notation, denoting the submatrices as A i A_i A i and B i B_i B i , and the community size as p p p .
Algorithm 1 Canonical OSSA
Require: Symmetric matrices { A i , B i } i = 1 n \{A_i, B_i\}_{i=1}^{n} { A i , B i } i = 1 n in one community; budget κ \kappa κ ; initial steps η W \eta_W η W , η s \eta_s η s ; backtracking factor β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 )
Ensure: Alignment W W W , relaxed support s s s , and hard support V ^ \widehat{\mathcal{V}} V
Initialize W ← I p W \leftarrow I_p W ← I p or a random orthogonal matrix; initialize s ∈ S κ s \in\mathcal{S}_{\kappa} s ∈ S κ
repeat
S ← diag ( s ) S \leftarrow\operatorname{diag}(s) S ← diag ( s ) and M i ← S B i S M_i \leftarrow SB_iS M i ← S B i S for i = 1 , … , n i=1,\ldots,n i = 1 , … , n
G W ← 2 ∑ i = 1 n A i W M i G_W \leftarrow2\sum_{i=1}^{n} A_iWM_i G W ← 2 ∑ i = 1 n A i W M i and W + ( η ) ← Π O ( p ) ( W + η G W ) W^{+}(\eta) \leftarrow\Pi_{O(p)}(W+\eta G_W) W + ( η ) ← Π O ( p ) ( W + η G W )
Choose the largest η ∈ { η W β m : m ≥ 0 } \eta\in\{\eta_W\beta^m:m\geq0\} η ∈ { η W β m : m ≥ 0 } satisfying J ( W + ( η ) , s ) ≥ J ( W , s ) J(W^{+}(\eta),s)\geq J(W,s) J ( W + ( η ) , s ) ≥ J ( W , s ) , and set W ← W + ( η ) W \leftarrow W^{+}(\eta) W ← W + ( η )
D ← sym { ∑ i = 1 n ( W T A i W ) ∘ B i } D \leftarrow\operatorname{sym}\{\sum_{i=1}^{n}(W^{\mathsf{T}}A_iW)\circ B_i\} D ← sym { ∑ i = 1 n ( W T A i W ) ∘ B i }
g s ← 2 D s g_s \leftarrow2Ds g s ← 2 D s and s + ( η ) ← Π S κ ( s + η g s ) s^{+}(\eta)\leftarrow\Pi_{\mathcal{S}_{\kappa}}(s+\eta g_s) s + ( η ) ← Π S κ ( s + η g s )
Choose the largest η ∈ { η s β m : m ≥ 0 } \eta\in\{\eta_s\beta^m:m\geq0\} η ∈ { η s β m : m ≥ 0 } satisfying J ( W , s + ( η ) ) ≥ J ( W , s ) J(W,s^{+}(\eta))\geq J(W,s) J ( W , s + ( η )) ≥ J ( W , s ) , and set s ← s + ( η ) s\leftarrow s^{+}(\eta) s ← s + ( η )
until the objective and iterate changes satisfy the stopping tolerances
V ^ ← Top κ ( s ) \widehat{\mathcal{V}}\leftarrow\operatorname{Top}_{\kappa}(s) V ← Top κ ( s )
return W W W , s s s , V ^ \widehat{\mathcal{V}} V
Fixing each community, our target is to recover a shared subset of brain regions V ⊆ { 1 , … , p } \mathcal{V}\subseteq\{1,\ldots,p\} V ⊆ { 1 , … , p } , where ∣ V ∣ ≤ κ |\mathcal{V}|\leq\kappa ∣ V ∣ ≤ κ , such that the V \mathcal{V} V -induced SC subgraph has maximal agreement with the FC geometry across subjects. This V \mathcal{V} V -induced SC subgraph thus serves as a structural backbone for the FC patterns.
The canonical Ossa
Let O ( p ) O(p) O ( p ) be the set of all p × p p\times p p × p orthogonal matrices, and write S = diag ( s ) S=\operatorname{diag}(s) S = diag ( s ) . Fixing one community, the OSSA problem is defined as the following optimization problem
max W , s J ( W , s ) = ∑ i = 1 n Tr [ ( W T A i W ) ( S B i S ) ] (1) \max_{W,s}\quad J(W,s)=\sum_{i=1}^{n}\operatorname{Tr}\left[(W^{\mathsf{T}}A_iW)(SB_iS)\right] \tag*{(1)} W , s max J ( W , s ) = i = 1 ∑ n Tr [ ( W T A i W ) ( S B i S ) ] (1)
s.t. W T W = I p , s ∈ { 0 , 1 } p , 1 T s = κ . \text{s.t.}\quad W^{\mathsf{T}}W=I_p,\qquad s\in\{0,1\}^{p},\qquad\mathbf{1}^{\mathsf{T}}s=\kappa. s.t. W T W = I p , s ∈ { 0 , 1 } p , 1 T s = κ .
where Tr is the trace operator. Two parameters are introduced in the OSSA problem. The selection vector s s s identifies a subset of nodes from the SC, such that S B i S SB_iS S B i S represents the induced structural subgraph of B i B_i B i . Concurrently, the rotation matrix W W W captures a shared cross-modal transformation mapping. The objective function J ( W , s ) J(W,s) J ( W , s ) explicitly evaluates the alignment between the transformed FC matrix and the corresponding induced SC subgraph. Because the induced matrix S B i S SB_iS S B i S is generally expected to form a locally dense structural module within the selected node set, it can be conceptualized as a structural clique of the SC network, a topological connectivity pattern widely documented in empirical connectome studies [34 , 39 , 33 ] . Both components are indispensable to this formulation: without the orthogonal transformation W W W , the model would impose an exact coordinate-level comparability between FC and SC, a restrictive assumption rarely supported by empirical connectome data. Conversely, without the sparse selection vector s s s , the objective degenerates into a global alignment metric, failing to achieve precise anatomical localization. As OSSA is formulated within individual functional communities, its integration with functional community detection establishes a hierarchical refinement of the cross-modal SC-FC relationship.
Directly optimizing the objective in (1) is NP-hard due to the combinatorial nature of the binary constraints. To circumvent these difficulties, we employ a continuous relaxation of the domain for s s s , formulating the following surrogate optimization problem.
max W ∈ O ( p ) , s ∈ S κ J ( W , s ) , S κ = { s ∈ [ 0 , 1 ] p : 1 T s ≤ κ } . (2) \max_{W\in O(p),\,s\in\mathcal{S}_{\kappa}} J(W,s),\qquad\mathcal{S}_{\kappa}=\{s\in[0,1]^{p}:\mathbf{1}^{\mathsf{T}}s\leq\kappa\}. \tag*{(2)} W ∈ O ( p ) , s ∈ S κ max J ( W , s ) , S κ = { s ∈ [ 0 , 1 ] p : 1 T s ≤ κ } . (2)
Upon solving the relaxed formulation in (2) , the final induced subnetwork is recovered via a hard thresholding procedure, V ^ = Top κ ( s ^ ) \widehat{\mathcal{V}}=\operatorname{Top}_{\kappa}(\widehat{s}) V = Top κ ( s ) , where Top κ \operatorname{Top}_{\kappa} Top κ extracts the indices corresponding to the κ \kappa κ largest entries. This continuous relaxation preserves the natural interpretation of s s s as a soft subgraph-membership indicator while simultaneously rendering the optimization computationally tractable. We solve (2) by a projected block-coordinate ascent procedure, outlined in Algorithm 1.
Theoretical properties. We study (2) within a fixed population community. The matrices restricted to that community satisfy the sampling conditions in Assumptions A1–A2. Define
J ˉ n ( W , s ) = J ( W , s ) n , J ( W , s ) = E J ˉ n ( W , s ) . (3) \bar{J}_n(W,s)=\frac{J(W,s)}{n},\qquad\mathcal{J}(W,s)=\mathbb{E}\bar{J}_n(W,s). \tag*{(3)} J ˉ n ( W , s ) = n J ( W , s ) , J ( W , s ) = E J ˉ n ( W , s ) . (3)
For V ⊆ { 1 , … , p } V\subseteq\{1,\ldots,p\} V ⊆ { 1 , … , p } , let 1 V \mathbf{1}_V 1 V be its indicator vector and P V = diag ( 1 V ) P_V=\operatorname{diag}(\mathbf{1}_V) P V = diag ( 1 V ) . Fix V ⋆ V^\star V ⋆ with ∣ V ⋆ ∣ = κ \lvert V^\star\rvert=\kappa ∣ V ⋆ ∣ = κ and write u ⋆ = 1 V ⋆ u^\star=\mathbf{1}_{V^\star} u ⋆ = 1 V ⋆ . Assumption A3 specifies a compact smooth embedded submanifold W ⋆ ⊂ O ( p ) \mathcal{W}^\star\subset O(p) W ⋆ ⊂ O ( p ) and a rank-κ \kappa κ orthogonal projector Π ⋆ \Pi^\star Π ⋆ such that J ( U , u ⋆ ) = J ⋆ \mathcal{J}(U,u^\star)=J^\star J ( U , u ⋆ ) = J ⋆ , grad W J ( U , u ⋆ ) = 0 \operatorname{grad}_{\mathcal{W}}\mathcal{J}(U,u^\star)=0 grad W J ( U , u ⋆ ) = 0 , and U P V ⋆ U T = Π ⋆ UP_{V^\star}U^\mathsf{T}=\Pi^\star U P V ⋆ U T = Π ⋆ for every U ∈ W ⋆ U\in\mathcal{W}^\star U ∈ W ⋆ , where grad W \operatorname{grad}_{\mathcal{W}} grad W denotes the gradient for the Frobenius metric on O ( p ) O(p) O ( p ) . We let J ⋆ J^\star J ⋆ denote the common value of the population alignment objective J ( U , u ⋆ ) \mathcal{J}(U,u^\star) J ( U , u ⋆ ) for U ∈ W ⋆ U\in\mathcal{W}^\star U ∈ W ⋆ . Under the curvature condition in Assumption A4, each such alignment is a local maximizer of J ( ⋅ , u ⋆ ) \mathcal{J}(\cdot,u^\star) J ( ⋅ , u ⋆ ) . The matrices in W ⋆ \mathcal{W}^\star W ⋆ are therefore stationary alignments whose columns indexed by V ⋆ V^\star V ⋆ span the same subspace.
Theorem 1 establishes the existence of local maximizers satisfying (133) and proves s ^ = u ⋆ \widehat{s}=u^\star s = u ⋆ and the bound on ∥ W ^ P V ⋆ W ^ T − Π ⋆ ∥ F \lVert\widehat{W}P_{V^\star}\widehat{W}^{\mathsf{T}}-\Pi^\star\rVert_F ∥ W P V ⋆ W T − Π ⋆ ∥ F in (4) for every such maximizer.
Theorem 1. Suppose Assumptions A1–A5 hold. In addition, let x > 0 x>0 x > 0 and 0 < r < r 0 0<r<r_0 0 < r < r 0 satisfy Assumption A6. With probability at least 1 − 2 e − x 1-2e^{-x} 1 − 2 e − x , (2) has a local maximizer ( W ^ , s ^ ) (\widehat{W},\widehat{s}) ( W , s ) in a neighborhood of ( W ⋆ , u ⋆ ) (\mathcal{W}^\star,u^\star) ( W ⋆ , u ⋆ ) satisfying
s ^ = u ⋆ , ∥ W ^ P V ⋆ W ^ T − Π ⋆ ∥ F ≤ 8 ( κ − 1 ) κ η n ( x ) α n . (4) \widehat{s}=u^\star,\qquad\left\lVert\widehat{W}P_{V^\star}\widehat{W}^{\mathsf{T}}-\Pi^\star\right\rVert_F\leq\frac{8(\kappa-1)\sqrt{\kappa}\,\eta_n(x)}{\alpha_n}. \tag*{(4)} s = u ⋆ , W P V ⋆ W T − Π ⋆ F ≤ α n 8 ( κ − 1 ) κ η n ( x ) . (4)
Here η n ( x ) \eta_n(x) η n ( x ) , and α n \alpha_n α n are specified in Section B.
Proof is given in Section B. In Theorem 1, η n ( x ) \eta_n(x) η n ( x ) denote a high-probability bound on the operator-norm differences between sample and population averages of FC matrices weighted by SC edge values, uniformly over all edges. The constant α n \alpha_n α n characterizes the lower bound of the magnitude of the negative curvature of the population objective in directions normal to the target alignment set W ⋆ \mathcal{W}^\star W ⋆ . The radius r 0 r_0 r 0 limits the size of the neighborhood in which the local recovery analysis applies. For every local maximizer covered by Theorem 1, the first conclusion of the support recovery yields V ^ = Top κ ( s ^ ) = V ⋆ \widehat{V}=\operatorname{Top}_{\kappa}(\widehat{s})=V^\star V = Top κ ( s ) = V ⋆ . Consequently, W ^ P V ^ W ^ T = W ^ P V ⋆ W ^ T \widehat{W}P_{\widehat{V}}\widehat{W}^{\mathsf{T}}=\widehat{W}P_{V^\star}\widehat{W}^{\mathsf{T}} W P V W T = W P V ⋆ W T is the orthogonal projector onto the functional subspace spanned by the columns of W ^ \widehat{W} W indexed by the recovered SC support. The two conclusions therefore address both components of OSSA: identifying the structural node set and recovering its aligned functional subspace. Along any sequence satisfying the assumptions of Theorem 1 with x = x n → ∞ x=x_n\to\infty x = x n → ∞ , these estimated projectors are consistent in probability for Π ⋆ \Pi^\star Π ⋆ if the right-hand side of (4) tends to zero. These guarantees concern local maximizers in the specified neighborhood. We do not claim that Algorithm 1, including its multi-restart selection rule below, reaches this neighborhood or returns one of these maximizers. The monotonicity of the objective values alone does not ensure this; see Appendix A.5 and Appendix G.
Extension to multiple cliques
The canonical OSSA framework identifies a single dominant clique within each functional community. This configuration is practically well-justified, as communities in functional connectivity networks are typically already restricted in scale (comprising approximately 10–30 nodes). Further partitioning these modules into multiple cliques is rarely necessary from a dimensionality reduction perspective. Indeed, as demonstrated in our analysis of the ABCD dataset (Section 4), empirical evidence strongly corroborates the prevalence of a single-clique structural topology within these localized functional modules. Nevertheless, for broader applicability, the OSSA formulation can be naturally extended to extract multiple cliques per community. Specifically, we generalize the method by introducing K K K to denote the predefined number of target cliques to be identified within a given community, as OSSA-K K K . Define
s ( ℓ ) ∈ S κ , S ( ℓ ) = diag ( s ( ℓ ) ) , S κ = { s ∈ [ 0 , 1 ] p : 1 T s ≤ κ } , 1 ≤ ℓ ≤ K . s^{(\ell)}\in\mathcal{S}_{\kappa},\qquad\mathcal{S}^{(\ell)}=\operatorname{diag}(s^{(\ell)}),\qquad\mathcal{S}_{\kappa}=\{s\in[0,1]^p:\mathbf{1}^{\mathsf{T}}s\leq\kappa\},\qquad1\leq\ell\leq K. s ( ℓ ) ∈ S κ , S ( ℓ ) = diag ( s ( ℓ ) ) , S κ = { s ∈ [ 0 , 1 ] p : 1 T s ≤ κ } , 1 ≤ ℓ ≤ K .
The K K K -clique OSSA problem solves
max W ∈ O ( p ) , s ( 1 ) , … , s ( K ) ∈ S κ ∑ ℓ = 1 K ∑ i = 1 n Tr [ ( W T A i W ) ( S ( ℓ ) B i S ( ℓ ) ) ] − λ ∑ ℓ < ℓ ′ ⟨ s ( ℓ ) , s ( ℓ ′ ) ⟩ . (5) \max_{\substack{W\in O(p),\ s^{(1)},\ldots,s^{(K)}\in\mathcal{S}_{\kappa}}}
\sum_{\ell=1}^{K}\sum_{i=1}^{n}\operatorname{Tr}\left[(W^{\mathsf{T}}A_iW)\left(\mathcal{S}^{(\ell)}B_i\mathcal{S}^{(\ell)}\right)\right]
-\lambda\sum_{\ell<\ell'}\left\langle s^{(\ell)},s^{(\ell')}\right\rangle. \tag*{(5)} W ∈ O ( p ) , s ( 1 ) , … , s ( K ) ∈ S κ max ℓ = 1 ∑ K i = 1 ∑ n Tr [ ( W T A i W ) ( S ( ℓ ) B i S ( ℓ ) ) ] − λ ℓ < ℓ ′ ∑ ⟨ s ( ℓ ) , s ( ℓ ′ ) ⟩ . (5)
This objective is a direct generalization of the canonical formulation, incorporating an explicit regularization term to penalize redundant or highly overlapping node memberships. Crucially, the orthogonal transformation matrix W W W is shared across all structural subgraphs. This shared rotation ensures that all candidate subnetworks are evaluated within a unified functional coordinate system, thereby preventing clique-specific transformations from artificially absorbing the underlying separation structure. We employ a similar projected block-coordinate ascent procedure. The complete optimization routine is detailed as Algorithm 2 in Appendix § 9 .
Remark. We employ the K K K -clique extension primarily as a diagnostic tool. If multiple distinct cliques adequately explain the functional connectivity, the estimated supports should diverge at moderate values of the regularization parameter λ \lambda λ , while maintaining robust cross-modal alignment on held-out data. Conversely, if a given FC community contains only a single aligned clique, the supports would collapse into a unified structure at small values of λ \lambda λ . When artificially forced apart by increased penalization, the extraneous supports may capture generic correlation structures but will cease to remain competitive under the primary alignment objective.
Simulation experiments
We first evaluate OSSA in simulations with known target supports. These experiments isolate support recovery, the role of the orthogonal block, and whether the K K K -support extension separates repeated recovery from distinct cores. All simulation experiments use fixed train/validation/test splits. We use the W = I p W = I_p W = I p ablation, OSSA-NOW, to isolate the learned rotation. Uncertainty is reported as standard error over simulation replicates.
Evaluation of the canonical OSSA
Experiment setup. We first test recovery of one planted clique under FC-SC coordinate mismatch. Each replicate contains n = 30 n = 30 n = 30 subjects in one community of size p = 40 p = 40 p = 40 , with a planted support V ⋆ V^\star V ⋆ of size κ ⋆ = 10 \kappa^\star= 10 κ ⋆ = 10 . For each subject i i i ,
B i = C i + ζ i B + σ B E i B , A i = W ⋆ C i W ⋆ ⊤ + ζ i A + σ A E i A , B_i = C_i + \zeta_i^B + \sigma_B E_i^B,\qquad A_i = W^\star C_i W^{\star\top} + \zeta_i^A + \sigma_A E_i^A, B i = C i + ζ i B + σ B E i B , A i = W ⋆ C i W ⋆ ⊤ + ζ i A + σ A E i A ,
with all matrices symmetrized and diagonal entries set to zero. The shared signal is C i = LR 3 ( V ⋆ , 1.5 ) C_i = \operatorname{LR}_3(V^\star, 1.5) C i = LR 3 ( V ⋆ , 1.5 ) , where LR r ( D , c ) \operatorname{LR}_r(D,c) LR r ( D , c ) denotes a symmetric mixed-sign block supported on D × D D \times D D × D , generated as U U ⊤ ∘ Σ UU^\top\circ\Sigma U U ⊤ ∘ Σ with entries U a b ∼ i . i . d . N ( 0 , c 2 / r ) U_{ab} \mathrel{\overset{\mathrm{i.i.d.}}{\sim}} \mathcal{N}(0,c^2/r) U ab ∼ i.i.d. N ( 0 , c 2 / r ) and a symmetric random sign matrix Σ \Sigma Σ . The additional terms ζ i A , ζ i B \zeta_i^A,\zeta_i^B ζ i A , ζ i B collect subject-level background and modality-specific nuisance variation, their exact construction is given in Appendix § 10 .§ 1 . These terms are included to stress-test recovery under extra single-modality variation, not as part of the OSSA model itself. The control mismatch by W ⋆ = polar ( ( 1 − α ) I p + α Q ) W^\star= \operatorname{polar}((1-\alpha)I_p+\alpha Q) W ⋆ = polar (( 1 − α ) I p + α Q ) , where Q ∼ Haar ( O ( p ) ) Q \sim\operatorname{Haar}(O(p)) Q ∼ Haar ( O ( p )) and polar ( X ) = U V ⊤ \operatorname{polar}(X)=UV^\top polar ( X ) = U V ⊤ for X = U Σ V ⊤ X=U\Sigma V^\top X = U Σ V ⊤ is the orthogonal factor in the polar decomposition. Thus α = 0 \alpha=0 α = 0 gives matched coordinates, and α = 1 \alpha=1 α = 1 gives a random rotation.
We compare OSSA with size-matched baselines that select κ \kappa κ nodes by simple marginal or graph summaries: (1) Marginal degree: SC-DEGREE and FC-DEGREE take the top-κ \kappa κ nodes by row-sum of ∣ B ‾ ∣ |\overline{B}| ∣ B ∣ and ∣ A ‾ ∣ |\overline{A}| ∣ A ∣ , respectively, where the average is over subjects. (2) Edgewise modality fusion: JOINT-SCxFC takes the top-κ \kappa κ nodes by row-sum of ∣ A ‾ ∘ B ‾ ∣ |\overline{A}\circ\overline{B}| ∣ A ∘ B ∣ . (3) SC graph summary: COMMUNICABILITY [14 ] takes the top-κ \kappa κ nodes by column-sum of exp ( B ‾ ) \exp(\overline{B}) exp ( B ) . (4) RANDOM samples a uniform κ \kappa κ -node subset as a control floor. We also include two OSSA controls: OSSA-NOW fixes W = I p W=I_p W = I p , and OSSA-ORACLE fixes W = W ⋆ W=W^\star W = W ⋆ as an upper bound. All OSSA variants use eight restarts, and we keep the largest training objective. We report Jaccard similarity with the planted support and exact recovery rate, averaged over 10 independent replicates for each ( α , σ , n ) (\alpha,\sigma,n) ( α , σ , n ) setting. Detailed setup is defined in Appendix § 10 .§ 1 .
Results. Among the tested methods, OSSA remains accurate under latent FC-SC rotation (Table 1 ; full rotation and noise sweeps are reported in Appendix § 10 .§ 2 ). In the full sweep, fixed-coordinate methods work at α = 0 \alpha=0 α = 0 but fail as rotation increases. At full rotation, OSSA reaches Jaccard 0.861 ± 0.042 0.861\pm0.042 0.861 ± 0.042 and exactly recovers V ⋆ V^\star V ⋆ in 40% of replicates, compared with 0.205 ± 0.045 0.205\pm0.045 0.205 ± 0.045 for OSSA-NOW. The oracle run with W = W ⋆ W=W^\star W = W ⋆ is nearly perfect, suggesting that the remaining gap comes from estimating W W W . OSSA also remains stable at σ = 0.5 \sigma=0.5 σ = 0.5 (0.827 ± \pm ± 0.043) and reaches 0.85-0.89 for n ≥ 30 n \ge30 n ≥ 30 , where baselines show little gain with larger n n n .
Table 1. Canonical OSSA clique support recovery on three diagnostic slices (mean ± \pm ± s.e.). EXACT reports Pr ( V ^ = V ⋆ ) \Pr(\hat{V}=V^\star) Pr ( V ^ = V ⋆ ) at α = 1 \alpha=1 α = 1 . OSSA-ORACLE is reported separately as an upper bound.
Multi-clique simulation
We further evaluate OSSA-K K K in a multi-clique setting. We use one community (p = 50 p=50 p = 50 , n = 30 n=30 n = 30 ), a shared latent rotation α = 0.6 \alpha=0.6 α = 0.6 , and noise σ = 0.4 \sigma=0.4 σ = 0.4 , with either two disjoint supports, two supports sharing four nodes, or three disjoint supports. We compare against random, SC-spectral, communicability, and SEQUENTIAL-OSSA K K K -support baselines. SEQUENTIAL-OSSA is a greedy baseline that fits canonical OSSA, masks the selected nodes, and refits. Details of the generator, baselines, λ \lambda λ grid, and full results are in Appendices § 10 .6-§ 10 .7.
Table 2 summarizes the diagnostic outcome. OSSA-K K K recovers all three regimes. In the overlap case, it estimates 3.75 ± \pm ± 0.56 shared nodes for a planted overlap of four. The strongest baseline, SEQUENTIAL-OSSA, works mainly in disjoint regimes and degrades under planted overlap because its masking step enforces disjoint supports. Thus the shared-W W W objective in (5) recovers multi-clique structure while allowing controlled overlap.
Robustness
We run three robustness checks for choices that are usually unknown in practice, full results are in Appendix D. (i) Sparsity-budget misspecification (Appendix D.4): When κ \kappa κ is swept from 4 to 16 around κ ⋆ = 10 \kappa^\star=10 κ ⋆ = 10 at α = 0.6 \alpha=0.6 α = 0.6 and σ = 0.4 \sigma=0.4 σ = 0.4 , OSSA stays above all non-OSSA baselines. Smaller budgets favor precision and larger budgets favor recall. (ii) Selection stability (Appendix D.5): Bootstrap selection frequency is higher on planted than non-planted nodes (0.46 vs. 0.18), and per-restart pairwise Jaccard has median 0.43. The observed variation in selected supports across initializations indicates sensitivity to initialization in the joint nonconvex optimization problem. We therefore use multiple restarts in the main experiments and keep the run with the largest training objective. (iii) Continuous λ \lambda λ -trajectory (Appendix D.7): the dense λ \lambda λ grid spans four decades, and fitted overlap decreases from collapse, through the planted value, to full disjointness. These checks motivate the fixed-budget, multi-restart, and λ \lambda λ -diagnostic choices used for ABCD.
Cross-modal analysis of adolescent brain connectome
We next evaluate OSSA on Adolescent Brain Cognitive Development (ABCD) study [6 , 20 ] , a large multi-site longitudinal neuroimaging study of adolescent brain development. We use ABCD structural and functional connectomes on the 68-region Desikan-Killiany atlas [11 ] . The main evaluation uses the baseline release: FC is signed Pearson correlation and SC is normalized streamline density. We symmetrize both modalities, ignore diagonals, Fisher-z z z transform FC, clip negative FC values, and apply log ( 1 + ⋅ ) \log(1 + \cdot) log ( 1 + ⋅ ) to SC. A cohort-median 5 σ 5\sigma 5 σ QC rule on off-diagonal means removes 10 subjects, leaving n A B C D = 2,350 n_{\mathrm{ABCD}} = 2{,}350 n ABCD = 2 , 350 . We use deterministic 60/20/20 train/validation/test splits over 10 seeds. Community count, sparsity budget, and baseline-side rotations are selected using only training/validation data. The test set is evaluated once after these choices are fixed.
Community partition and budget. Network cross-validation offers an alternative framework for selecting the number of communities under network models [8 , 27 ] . Across all 10 split seeds, we select Q = 3 Q = 3 Q = 3 communities by jointly considering eigengap [45 ] , Newman-Girvan modularity [30 ] , and silhouette [35 ] , with partitions stable up to label permutation. This stability is assessed under the same community-construction procedure; the identities of the regions selected by OSSA remain conditional on that procedure (see Appendix § 10 .14). The training-only diagnostic curves are reported in Appendix § 10 .§ 3 . The pooled community sizes are ( 30 , 23 , 15 ) (30, 23, 15) ( 30 , 23 , 15 ) . We set κ = 3 \kappa= 3 κ = 3 in each community, the smallest nontrivial induced SC subgraph after zeroing SC diagonals: κ = 1 \kappa= 1 κ = 1 gives zero objective, and κ = 2 \kappa= 2 κ = 2 selects one edge. This choice is also supported by the baseline validation curves: averaged across split seeds, alignment per selected node, J v a l ( κ ) / κ J_{\mathrm{val}}(\kappa)/\kappa J val ( κ ) / κ , is highest at κ = 3 \kappa= 3 κ = 3 among the tested budgets κ ≥ 3 \kappa\ge3 κ ≥ 3 in each community. We also check κ ∈ { 3 , 5 , 8 , 10 } \kappa\in\{3, 5, 8, 10\} κ ∈ { 3 , 5 , 8 , 10 } to test sensitivity to this scale (Appendix § 10 .8).
Baselines and metrics. We compare OSSA with fourteen size-matched support-selection baselines and the OSSA-NoW ablation. (1) Marginal degree (SC-DEGREE, FC-DEGREE) rank nodes by row sums of the training means of ∣ B i ∣ |B_i| ∣ B i ∣ and ∣ A i ∣ |A_i| ∣ A i ∣ , respectively. (2) Cross-modal fusion (JOINT-SCxFC) ranks row sums of the averaged ∣ A i ∘ B i ∣ |A_i \circ B_i| ∣ A i ∘ B i ∣ . (3) SC graph summary (COMMUNICABILITY [14 ] ) uses column sums of exp ( B ˉ ) \exp(\bar{B}) exp ( B ˉ ) . (4) SDI [32 ] ranks nodes by the high/low-frequency FC energy ratio on the normalized SC Laplacian. (5) Deep learning (BRAINGNN [28 ] , BRAINNETCNN [23 ] ) both provide learned node saliencies, with hyperparameters selected by validation loss under the same compute budget as one OSSA run. (6) Random samples a uniform κ \kappa κ -node support. The ablation OSSA-NoW runs Algorithm 1 with W = I p W = I_p W = I p fixed. We additionally evaluate nonnegative matrix factorization (NMF) [24 ] , sparse partial least squares (PLS) [9 ] , path efficiency, mean first passage time, FAQ graph matching [44 ] , and SC-to-FC ridge prediction as size-matched node-selection baselines. For fairness, each baseline support is refit with its own rotation. For a selected support V ^ m , q \widehat{V}_{m,q} V m , q from method m m m in community q q q , we hold s = 1 V ^ m , q s = \mathbf{1}_{\widehat{V}_{m,q}} s = 1 V m , q fixed (protocol detail in Appendix § 10 .9) and fit a method-specific W ^ m , q \widehat{W}_{m,q} W m , q by running the OSSA W W W -block on training subjects. Thus the evaluator is the same across methods and only the support changes. Our primary metric is the out-of-sample OSSA objective evaluated on held-out test data, given by,
M 1 , a l n ( V ^ , W ) = 1 n t e ∑ i = 1 n t e Tr [ ( W T A i t e W ) ( S B i t e S ) ] , S = diag ( 1 V ^ ) . M_{1,\mathrm{aln}}(\widehat{V},W)=\frac{1}{n_{\mathrm{te}}}\sum_{i=1}^{n_{\mathrm{te}}}\operatorname{Tr}\left[(W^{\mathsf{T}}A_i^{\mathrm{te}}W)(S B_i^{\mathrm{te}}S)\right],\qquad S=\operatorname{diag}(\mathbf{1}_{\widehat{V}}). M 1 , aln ( V , W ) = n te 1 i = 1 ∑ n te Tr [ ( W T A i te W ) ( S B i te S ) ] , S = diag ( 1 V ) .
Let vec > ( ⋅ ) \operatorname{vec}_{>}(\cdot) vec > ( ⋅ ) extract strictly upper-triangular entries and let ρ ( ⋅ , ⋅ ) \rho(\cdot,\cdot) ρ ( ⋅ , ⋅ ) denote Pearson correlation. The scale-free, rotation-aware concordance is
M 2 , a l n ( V ^ , W ) = 1 n t e ∑ i ρ ( vec > ( ( W T A i t e W ) [ V ^ , V ^ ] ) , vec > ( B i t e [ V ^ , V ^ ] ) ) . M_{2,\mathrm{aln}}(\widehat{V},W)=\frac{1}{n_{\mathrm{te}}}\sum_i\rho\left(\operatorname{vec}_{>}\left((W^{\mathsf{T}}A_i^{\mathrm{te}}W)[\widehat{V},\widehat{V}]\right),\operatorname{vec}_{>}\left(B_i^{\mathrm{te}}[\widehat{V},\widehat{V}]\right)\right). M 2 , aln ( V , W ) = n te 1 i ∑ ρ ( vec > ( ( W T A i te W ) [ V , V ] ) , vec > ( B i te [ V , V ] ) ) .
with M 2 , r a w = M 2 , a l n ( V ^ , I p ) M_{2,\mathrm{raw}}=M_{2,\mathrm{aln}}(\widehat{V},I_p) M 2 , raw = M 2 , aln ( V , I p ) as a rotation-unaware control. To test whether a support merely selects structurally dense nodes, we use an SC-degree-quartile-matched null:
M 3 , a l n ( V ^ , W ) = M 2 , a l n ( V ^ , W ) − 1 N ∑ r = 1 N M 2 , a l n ( V ^ r , W ^ r ) . M_{3,\mathrm{aln}}(\widehat{V},W)=M_{2,\mathrm{aln}}(\widehat{V},W)-\frac{1}{N}\sum_{r=1}^{N}M_{2,\mathrm{aln}}(\widehat{V}_r,\widehat{W}_r). M 3 , aln ( V , W ) = M 2 , aln ( V , W ) − N 1 r = 1 ∑ N M 2 , aln ( V r , W r ) .
where each V ^ ( r ) \widehat{V}^{(r)} V ( r ) matches the SC-degree-quartile profile of V ^ \widehat{V} V within the same community and W ^ ( r ) \widehat{W}^{(r)} W ( r ) is refit by the same training-side W W W -block. We use N = 1000 N=1000 N = 1000 null supports and report the one-sided permutation p p p -value as the fraction whose M 2 , a l n M_{2,\mathrm{aln}} M 2 , aln exceeds the observed value.
Canonical OSSA evaluation. At κ = 3 \kappa=3 κ = 3 , OSSA outperforms all size-matched baselines on held-out alignment (Table 3 ; Figure 2 b). Across 30 seed-community units, OSSA attains M 1 , a l n = 10.55 ± 0.85 M_{1,\mathrm{aln}}=10.55\pm0.85 M 1 , aln = 10.55 ± 0.85 ; the closest competitors are NMF (9.96 ± 0.82 9.96\pm0.82 9.96 ± 0.82 ) and sparse PLS (9.22 ± 1.10 9.22\pm1.10 9.22 ± 1.10 ) (Table 3 and Table 8 ). OSSA’s improvement over OSSA-NOW (3.82 ± 0.42 3.82\pm0.42 3.82 ± 0.42 ), which fixes W = I p W=I_p W = I p , points to the contribution of the learned orthogonal block. OSSA achieves higher held-out alignment in all 30 paired seed-community comparisons against each baseline in Table 3 . These comparisons are descriptive, because the repeated splits reuse subjects from the same cohort. For held-out subjects from one split, OSSA’s mean M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln exceeds NMF’s by 0.468 (paired subject-bootstrap 95% CI: [0.400, 0.534]; Appendix § 10 .9). The recovered supports are compact and stable across split seeds. After aligning community labels to the pooled Q = 3 Q=3 Q = 3 partition, the consensus supports localize to right occipital, fronto-orbitofrontal/frontal-pole, and right temporal regions, respectively (Figure 2 a; see Table 4 for SC edge weights). Scale-free metrics suggest that the gain is not just a structural-density effect. In raw coordinates, SC-DEGREE slightly exceeds OSSA on M 2 , r a w M_{2,\mathrm{raw}} M 2 , raw (+0.674 vs. +0.635), consistent with its preference for dense SC nodes. After each support is evaluated with its own fitted rotation, OSSA leads on M 2 , a l n M_{2,\mathrm{aln}} M 2 , aln (+0.821 vs. +0.695) and on the SC-degree-quartile-matched gain M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln (+0.81 vs. next-best +0.69). These aligned metrics quantify the concordance of the selected structural subgraph with the latent functional geometry represented by the fitted transformation (see Appendix § 10 .13 for full empirical diagnostics); the selected SC nodes retain their anatomical identities. The κ \kappa κ sweep in Figure 2 c keeps positive null-corrected gain for κ ∈ { 3 , 5 , 8 , 10 } \kappa\in\{3,5,8,10\} κ ∈ { 3 , 5 , 8 , 10 } , full values are in Appendix § 10 .8.
Figure 2. ABCD localization and diagnostics. (A) OSSA selection frequency for the three FC communities at κ = 3 \kappa= 3 κ = 3 . Labels denote consensus supports. (B) Mean ± \pm ± s.e. of held-out rotation-aware alignment M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln for the five methods shown (Table 3). (C) Budget robustness: OSSA maintains positive SC-degree-quartile-matched gain M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln . (D) K K K -support λ \lambda λ diagnostic: supports collapse at small λ \lambda λ and separate only under large penalties.
Table 3 : ABCD canonical OSSA evaluation, mean ± \pm ± s.e. across 30 (seed, community) units, κ = 3 \kappa= 3 κ = 3 . M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln gain is the difference between the method’s M 2 , a l n M_{2,\mathrm{aln}} M 2 , aln and the mean of N = 1000 N = 1000 N = 1000 SC-degree-quartile-matched random nulls. M 3 p M_{3}\ p M 3 p is mean (median) over the 30 units.
Table 3.
Table 4 : SC connectivity of the consensus supports. Ratios use SC-degree-matched null means.
Table 4.
Table 8. Additional size-matched baseline comparisons on ABCD. Held-out M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln is reported as mean ± \pm ± s.e. across 30 seed-community units. W/T/L denotes OSSA wins, ties, and losses against each baseline. These counts are descriptive because repeated splits reuse subjects.
Structural and alignment interpretation. The occipital and temporal supports include primary visual and auditory regions, consistent with stronger SC–FC correspondence in unimodal cortex [42 ] . Table 4 reports subject-averaged log ( 1 + x ) \log(1+x) log ( 1 + x ) SC edge weights and mean-weight ratios to SC-degree-matched nulls.
For Π ^ = W ^ P V ^ W ^ T \widehat{\Pi}=\widehat{W}P_{\widehat{V}}\widehat{W}^{\mathsf{T}} Π = W P V W T , the community-mean normalized squared distance from P V ^ P_{\widehat{V}} P V is 0.54–0.67, versus 0.80–0.90 for dimension-matched Haar references. Loading participation ratios indicate 5–10 effective FC regions versus 10–19 under Haar. These characterize latent functional geometry; SC node identities remain unchanged. The diagnostics alone do not establish biological specificity (Appendix § 10 .13).
Multi-clique sensitivity (λ \lambda λ -diagnostic). At κ = 3 \kappa= 3 κ = 3 , the ABCD path shows collapse for λ ≤ 10 2 \lambda\le10^{2} λ ≤ 1 0 2 (pairwise Jaccard 0.98, ∣ U ∣ / κ ≈ 1 |U|/\kappa\approx1 ∣ U ∣/ κ ≈ 1 ) and separation only under large penalties. Forced separation at λ = 10 4 \lambda= 10^{4} λ = 1 0 4 reduces the primary held-out objective from 10.42 to 6.42 (K = 2 K = 2 K = 2 ) and 4.60 (K = 3 K = 3 K = 3 ). Although M 2 , a l n M_{2,\mathrm{aln}} M 2 , aln and M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln gain increase at high λ \lambda λ , these appear to reflect secondary correlation motifs rather than additional high-M 1 M_{1} M 1 cores. These results support using K > 1 K > 1 K > 1 as a diagnostic rather than the default estimator. Full trajectories and baseline-extension checks are reported in Appendices D.10-D.11.
Second-visit replication. We apply the unchanged baseline protocol and QC to the ABCD Year-2 release, yielding n A B C D 2 = 1,897 n_{\mathrm{ABCD2}} = 1{,}897 n ABCD2 = 1 , 897 subjects (Appendix E). The three-community structure is preserved, with cross-seed ARI 0.99 ± 0.01 0.99 \pm0.01 0.99 ± 0.01 and pooled sizes (31, 23, 14), close to baseline (30, 23, 15). The canonical ranking is also preserved: OSSA attains M 1 , a l n = 10.16 ± 0.87 M_{1,\mathrm{aln}} = 10.16 \pm0.87 M 1 , aln = 10.16 ± 0.87 , compared with 3.23 ± \pm ± 0.30 for OSSA-NOW and at most 3.19 for classical baselines. OSSA leads each Table 11 baseline in held-out alignment across all 30 paired seed-community comparisons; these are descriptive because splits reuse follow-up subjects. The λ \lambda λ diagnostic gives the same single-core pattern: collapse at small λ \lambda λ and forced separation only at large λ \lambda λ . OSSA’s cross-visit support replication score (CVSR), measured by support-set Jaccard, is 0.928 ± \pm ± 0.033, with mean overlap 2.86/3 nodes. Graph-summary baselines also replicate well, whereas deep-learning baselines replicate less well. CVSR supports longitudinal stability, which alone does not establish biological specificity. Appendix E gives per-method results and the follow-up λ \lambda λ sweep.
Table 11. ABCD second-visit canonical OSSA evaluation, mean ± \pm ± s.e. across 30 (seed, community) units, κ = 3 \kappa= 3 κ = 3 , on n A B C D 2 = 1,897 n_{\mathrm{ABCD2}} = 1{,}897 n ABCD2 = 1 , 897 subjects. Conventions match Table 3 : M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln gain is the difference between the method’s M 2 , a l n M_{2,\mathrm{aln}} M 2 , aln and the mean of N = 1000 N = 1000 N = 1000 SC-degree-quartile-matched random nulls; M 3 p M_3\,p M 3 p is mean (median) over the 30 units. The headline summary appears in § 4 (“Second-visit replication”), with this appendix providing per-method detail.
Conclusion and discussion
OSSA jointly localizes structural subnetworks and aligns them with latent functional geometry. In ABCD, the selected supports are compact, stable, and longitudinally reproducible; the λ \lambda λ path suggests a dominant aligned core within each FC community. Our theoretical guarantees cover canonical OSSA within a fixed population community. Future work includes establishing that the current algorithm reaches the required neighborhood with sufficiently small stationarity residuals, or developing an algorithm with these guarantees, as well as extending the statistical guarantees to the multi-clique setting. Empirically, the analyses are restricted to the Desikan–Killiany parcellation and the ABCD cohort; the identities of the selected regions are conditional on the functional-community construction and the sparsity budget. Rigorous replication across parcellations, acquisition pipelines, and clinical cohorts is needed before assigning definitive biological significance to these supports.
Acknowledgments and Disclosure of Funding
This work was supported by the National Institutes of Health (NIH) under grants R01AG081413, R01EB034720, and R01AG068191 (to Y. Zhao). T. Li was also supported in part by the National Science Foundation (NSF) under grant DMS-2515367. We thank the anonymous reviewers for their constructive feedback, which substantially improved the paper.
Optimization details and derivations
This appendix gives the first-order quantities used in Algorithms 1 and 2. All derivations assume the matrices have been symmetrized. In implementation we use X ← ( X + X T ) / 2 X \leftarrow(X + X^{\mathsf{T}})/2 X ← ( X + X T ) /2 for numerical stability and ignore diagonal entries when evaluating inter-regional connectivity.
Gradient for the canonical Ossa clique W-block
Fix s s s and define M i = S B i S M_i = SB_iS M i = S B i S . For one subject,
f i ( W ) = Tr ( W T A i W M i ) . f_i(W) = \operatorname{Tr}(W^{\mathsf{T}}A_iWM_i). f i ( W ) = Tr ( W T A i W M i ) .
Taking differentials,
d f i = Tr ( d W T A i W M i ) + Tr ( W T A i d W M i ) = Tr ( ( A i W M i ) T d W ) + Tr ( ( A i T W M i T ) T d W ) . \begin{aligned}
df_i &= \operatorname{Tr}(dW^{\mathsf{T}}A_iWM_i) + \operatorname{Tr}(W^{\mathsf{T}}A_idWM_i) \\
&= \operatorname{Tr}((A_iWM_i)^{\mathsf{T}}dW) + \operatorname{Tr}((A_i^{\mathsf{T}}WM_i^{\mathsf{T}})^{\mathsf{T}}dW).
\end{aligned} d f i = Tr ( d W T A i W M i ) + Tr ( W T A i d W M i ) = Tr (( A i W M i ) T d W ) + Tr (( A i T W M i T ) T d W ) .
Therefore
∇ W f i ( W ) = A i W M i + A i T W M i T . \nabla_W f_i(W) = A_iWM_i + A_i^{\mathsf{T}}WM_i^{\mathsf{T}}. ∇ W f i ( W ) = A i W M i + A i T W M i T .
When A i A_i A i and M i M_i M i are symmetric, this simplifies to
∇ W J ( W , s ) = 2 ∑ i = 1 n A i W ( S B i S ) . (6) \nabla_W J(W,s) = 2\sum_{i=1}^{n} A_iW(SB_iS). \tag*{(6)} ∇ W J ( W , s ) = 2 i = 1 ∑ n A i W ( S B i S ) . (6)
A Euclidean ascent proposal W ~ = W + η ∇ W J \widetilde{W} = W + \eta\nabla_WJ W = W + η ∇ W J is mapped back to the orthogonal group by the polar projection [21 ]
Π O ( p ) ( W ~ ) = U V T , W ~ = U Σ V T , (7) \Pi_{O(p)}(\widetilde{W}) = UV^{\mathsf{T}}, \qquad\widetilde{W} = U\Sigma V^{\mathsf{T}}, \tag*{(7)} Π O ( p ) ( W ) = U V T , W = U Σ V T , (7)
which is the closest orthogonal matrix to W ~ \widetilde{W} W in Frobenius norm.
Reduction and gradient for the canonical Ossa clique s-block
Fix W W W and set Q i = W T A i W Q_i = W^{\mathsf{T}}A_iW Q i = W T A i W . Since S = diag ( s ) S = \operatorname{diag}(s) S = diag ( s ) ,
( S B i S ) a b = s a ( B i ) a b s b , S B i S = ( s s T ) ∘ B i . (SB_iS)_{ab} = s_a(B_i)_{ab}s_b, \qquad SB_iS = (ss^{\mathsf{T}}) \circ B_i. ( S B i S ) ab = s a ( B i ) ab s b , S B i S = ( s s T ) ∘ B i .
Using symmetry of Q i Q_i Q i and B i B_i B i ,
Tr ( Q i S B i S ) = ∑ a , b ( Q i ) a b ( B i ) a b s a s b = s T ( Q i ∘ B i ) s . \operatorname{Tr}(Q_iSB_iS) = \sum_{a,b}(Q_i)_{ab}(B_i)_{ab}s_as_b = s^{\mathsf{T}}(Q_i \circ B_i)s. Tr ( Q i S B i S ) = a , b ∑ ( Q i ) ab ( B i ) ab s a s b = s T ( Q i ∘ B i ) s .
Thus, with
D ( W ) = ∑ i = 1 n ( Q i ∘ B i ) , D(W) = \sum_{i=1}^{n}(Q_i \circ B_i), D ( W ) = i = 1 ∑ n ( Q i ∘ B i ) ,
the fixed-W W W objective is s T D ( W ) s s^{\mathsf{T}}D(W)s s T D ( W ) s , and
∇ s J ( W , s ) = 2 D ( W ) s . (8) \nabla_sJ(W,s) = 2D(W)s. \tag*{(8)} ∇ s J ( W , s ) = 2 D ( W ) s . (8)
Projection onto the capped simplex
The support update requires Euclidean projection [48 , 12 ] onto
S κ = { s ∈ R p : 0 ≤ s ≤ 1 , 1 T s ≤ κ } . \mathcal{S}_{\kappa} = \{s \in\mathbb{R}^{p} : 0 \le s \le1,\ \mathbf{1}^{\mathsf{T}}s \le\kappa\}. S κ = { s ∈ R p : 0 ≤ s ≤ 1 , 1 T s ≤ κ } .
For y ∈ R p y \in\mathbb{R}^{p} y ∈ R p , define z j ( τ ) = min { 1 , max { 0 , y j − τ } } z_j(\tau) = \min\{1,\max\{0,y_j-\tau\}\} z j ( τ ) = min { 1 , max { 0 , y j − τ }} for j = 1 , … , p j = 1,\ldots,p j = 1 , … , p . If ∑ j z j ( 0 ) ≤ κ \sum_j z_j(0) \le\kappa ∑ j z j ( 0 ) ≤ κ , then Π S κ ( y ) = z ( 0 ) \Pi_{\mathcal{S}_{\kappa}}(y) = z(0) Π S κ ( y ) = z ( 0 ) . Otherwise, Π S κ ( y ) = z ( τ ) \Pi_{\mathcal{S}_{\kappa}}(y) = z(\tau) Π S κ ( y ) = z ( τ ) , where τ > 0 \tau> 0 τ > 0 is chosen so that ∑ j z j ( τ ) = κ \sum_j z_j(\tau) = \kappa ∑ j z j ( τ ) = κ . This scalar equation is monotone in τ \tau τ and can be solved by bisection or a sorting-based capped-simplex projection method.
Multi-clique gradients
For the multi-clique objective (5), fix { s ( ℓ ) } ℓ = 1 K \{s^{(\ell)}\}_{\ell=1}^{K} { s ( ℓ ) } ℓ = 1 K and define
M i = ∑ ℓ = 1 K s ( ℓ ) B i s ( ℓ ) . M_i=\sum_{\ell=1}^{K}s^{(\ell)}B_i s^{(\ell)}. M i = ℓ = 1 ∑ K s ( ℓ ) B i s ( ℓ ) .
The overlap penalty is constant in W W W , so the same calculation as Appendix A.1 gives
∇ W J K ( W , { s ( ℓ ) } ) = 2 ∑ i = 1 n A i W M i . (9) \nabla_W J_K\left(W,\{s^{(\ell)}\}\right)=2\sum_{i=1}^{n}A_iWM_i. \tag*{(9)} ∇ W J K ( W , { s ( ℓ ) } ) = 2 i = 1 ∑ n A i W M i . (9)
For fixed W W W , the objective is
J K ( { s ( ℓ ) } ∣ W ) = ∑ ℓ = 1 K s ( ℓ ) ⊤ D ( W ) s ( ℓ ) − λ ∑ ℓ < ℓ ′ ⟨ s ( ℓ ) , s ( ℓ ′ ) ⟩ . J_K\left(\{s^{(\ell)}\}\mid W\right)=\sum_{\ell=1}^{K}s^{(\ell)\top}D(W)s^{(\ell)}-\lambda\sum_{\ell<\ell'}\left\langle s^{(\ell)},s^{(\ell')}\right\rangle. J K ( { s ( ℓ ) } ∣ W ) = ℓ = 1 ∑ K s ( ℓ ) ⊤ D ( W ) s ( ℓ ) − λ ℓ < ℓ ′ ∑ ⟨ s ( ℓ ) , s ( ℓ ′ ) ⟩ .
Holding all other supports fixed, the gradient with respect to s ( ℓ ) s^{(\ell)} s ( ℓ ) is
∇ s ( ℓ ) J K = 2 D ( W ) s ( ℓ ) − λ ∑ r ≠ ℓ s ( r ) . (10) \nabla_{s^{(\ell)}}J_K=2D(W)s^{(\ell)}-\lambda\sum_{r\ne\ell}s^{(r)}. \tag*{(10)} ∇ s ( ℓ ) J K = 2 D ( W ) s ( ℓ ) − λ r = ℓ ∑ s ( r ) . (10)
Each support is projected onto its own capped simplex S κ S_\kappa S κ .
Monotonicity and nonconvexity
Algorithms 1 and 2 use backtracking steps that accept only updates that do not decrease the objective. Since O ( p ) × S κ O(p)\times S_\kappa O ( p ) × S κ and O ( p ) × S κ K O(p)\times S_\kappa^K O ( p ) × S κ K are compact, the corresponding objective sequences are bounded and therefore converge in value. The optimization problems remain nonconvex because of the orthogonality constraint and the quadratic support variables. We therefore treat the algorithms as first-order local solvers. In all experiments, we use multiple random restarts and retain the run with the largest training objective. This monotonicity and boundedness imply convergence of the objective values, but do not by themselves establish convergence of the iterates, vanishing stationarity residuals, or convergence to a global maximizer. The objective and iterate change tolerances are numerical stopping criteria and do not by themselves imply the residual bounds required in theory below.
Technical details
For W ∈ O ( p ) W\in O(p) W ∈ O ( p ) , define
D n ( W ) = 1 n ∑ i = 1 n { ( W ⊤ A i W ) ∘ B i } , D 0 ( W ) = E D n ( W ) . (11) D_n(W)=\frac{1}{n}\sum_{i=1}^{n}\left\{(W^\top A_iW)\circ B_i\right\},\qquad D_0(W)=\mathbb{E}D_n(W). \tag*{(11)} D n ( W ) = n 1 i = 1 ∑ n { ( W ⊤ A i W ) ∘ B i } , D 0 ( W ) = E D n ( W ) . (11)
Then
J ‾ n ( W , s ) = s ⊤ D n ( W ) s , J ( W , s ) = s ⊤ D 0 ( W ) s . (12) \overline{J}_n(W,s)=s^\top D_n(W)s,\qquad\mathcal{J}(W,s)=s^\top D_0(W)s. \tag*{(12)} J n ( W , s ) = s ⊤ D n ( W ) s , J ( W , s ) = s ⊤ D 0 ( W ) s . (12)
For a vector v v v , write ∥ v ∥ 1 = ∑ j ∣ v j ∣ \lVert v\rVert_1=\sum_j|v_j| ∥ v ∥ 1 = ∑ j ∣ v j ∣ , ∥ v ∥ 2 = ( ∑ j v j 2 ) 1 / 2 \lVert v\rVert_2=(\sum_jv_j^2)^{1/2} ∥ v ∥ 2 = ( ∑ j v j 2 ) 1/2 , and ∥ v ∥ ∞ = max j ∣ v j ∣ \lVert v\rVert_\infty=\max_j|v_j| ∥ v ∥ ∞ = max j ∣ v j ∣ . For a matrix M M M , let ∥ M ∥ F = { Tr ( M ⊤ M ) } 1 / 2 \lVert M\rVert_F=\{\operatorname{Tr}(M^\top M)\}^{1/2} ∥ M ∥ F = { Tr ( M ⊤ M ) } 1/2 and ∥ M ∥ o p = sup ∥ v ∥ 2 = 1 ∥ M v ∥ 2 \lVert M\rVert_{\mathrm{op}}=\sup_{\lVert v\rVert_2=1}\lVert Mv\rVert_2 ∥ M ∥ op = sup ∥ v ∥ 2 = 1 ∥ M v ∥ 2 . For a real random variable Z Z Z and r ∈ { 1 , 2 } r\in\{1,2\} r ∈ { 1 , 2 } , define
∥ Z ∥ ψ r = inf { t > 0 : E exp ( ∣ Z ∣ r t r ) ≤ 2 } . (13) \lVert Z\rVert_{\psi_r}=\inf\left\{t>0:\mathbb{E}\exp\left(\frac{|Z|^r}{t^r}\right)\le2\right\}. \tag*{(13)} ∥ Z ∥ ψ r = inf { t > 0 : E exp ( t r ∣ Z ∣ r ) ≤ 2 } . (13)
The cases r = 1 r=1 r = 1 and r = 2 r=2 r = 2 are the sub-exponential and sub-Gaussian norms, respectively [47 ] .
For matrices X , Y X,Y X , Y of the same size, write ⟨ X , Y ⟩ = Tr ( X ⊤ Y ) \langle X,Y\rangle=\operatorname{Tr}(X^\top Y) ⟨ X , Y ⟩ = Tr ( X ⊤ Y ) . We equip O ( p ) O(p) O ( p ) with the Riemannian metric induced by this Frobenius inner product. For W , U W,U W , U in the same connected component, define
d O ( W , U ) = inf γ : [ 0 , 1 ] → O ( p ) γ ( 0 ) = U , γ ( 1 ) = W piecewise C 1 ∫ 0 1 ∥ γ ˙ ( t ) ∥ F d t . (14) d_O(W,U)=\inf_{\substack{\gamma:[0,1]\to O(p)\\ \gamma(0)=U,\ \gamma(1)=W\\ \text{piecewise }C^1}}\int_0^1\lVert\dot{\gamma}(t)\rVert_F\,dt. \tag*{(14)} d O ( W , U ) = γ : [ 0 , 1 ] → O ( p ) γ ( 0 ) = U , γ ( 1 ) = W piecewise C 1 inf ∫ 0 1 ∥ γ ˙ ( t ) ∥ F d t . (14)
Set d O ( W , U ) = + ∞ d_O(W,U)=+\infty d O ( W , U ) = + ∞ for points in different components. For every nonempty W ⊂ O ( p ) \mathcal{W}\subset O(p) W ⊂ O ( p ) , define
d O ( W , W ) = inf U ∈ W d O ( W , U ) , d V ( W , W ) = inf U ∈ W ∥ ( W − U ) P V ∥ F . (15) d_O(W,\mathcal{W})=\inf_{U\in\mathcal{W}}d_O(W,U),\qquad d_V(W,\mathcal{W})=\inf_{U\in\mathcal{W}}\lVert(W-U)P_V\rVert_F. \tag*{(15)} d O ( W , W ) = U ∈ W inf d O ( W , U ) , d V ( W , W ) = U ∈ W inf ∥( W − U ) P V ∥ F . (15)
Differentiating W T W = I p W^{\mathsf{T}}W=I_p W T W = I p along a differentiable curve gives
T W O ( p ) = { ξ ∈ R p × p : W T ξ + ξ T W = 0 } = { W Ω : Ω T = − Ω } . (16) T_WO(p)=\{\xi\in\mathbb{R}^{p\times p}:W^{\mathsf{T}}\xi+\xi^{\mathsf{T}}W=0\}=\{W\Omega:\Omega^{\mathsf{T}}=-\Omega\}. \tag*{(16)} T W O ( p ) = { ξ ∈ R p × p : W T ξ + ξ T W = 0 } = { W Ω : Ω T = − Ω } . (16)
For U ∈ O ( p ) U\in O(p) U ∈ O ( p ) and ξ ∈ T U O ( p ) \xi\in T_UO(p) ξ ∈ T U O ( p ) , the Riemannian exponential for this metric is
Exp U ( ξ ) = U exp ( U T ξ ) , exp ( M ) = ∑ k = 0 ∞ M k k ! . (17) \operatorname{Exp}_U(\xi)=U\exp(U^{\mathsf{T}}\xi),\qquad\exp(M)=\sum_{k=0}^{\infty}\frac{M^k}{k!}. \tag*{(17)} Exp U ( ξ ) = U exp ( U T ξ ) , exp ( M ) = k = 0 ∑ ∞ k ! M k . (17)
The curve t ↦ Exp U ( t ξ ) t\mapsto\operatorname{Exp}_U(t\xi) t ↦ Exp U ( t ξ ) is the geodesic with initial position U U U and initial velocity ξ \xi ξ ; see Edelman et al. [13 Section 2.2.2, Eq. (2.14)] . For Z ∈ R p × p Z\in\mathbb{R}^{p\times p} Z ∈ R p × p , note that
Z = { Z − W sym ( W T Z ) } + W sym ( W T Z ) , (18) Z=\{Z-W\operatorname{sym}(W^{\mathsf{T}}Z)\}+W\operatorname{sym}(W^{\mathsf{T}}Z), \tag*{(18)} Z = { Z − W sym ( W T Z )} + W sym ( W T Z ) , (18)
where sym ( M ) = ( M + M T ) / 2 \operatorname{sym}(M)=(M+M^{\mathsf{T}})/2 sym ( M ) = ( M + M T ) /2 . The first term in (18) belongs to T W O ( p ) T_WO(p) T W O ( p ) , the second belongs to its orthogonal complement, and the two terms are orthogonal. Hence
P W ( Z ) = Z − W sym ( W T Z ) (19) P_W(Z)=Z-W\operatorname{sym}(W^{\mathsf{T}}Z) \tag*{(19)} P W ( Z ) = Z − W sym ( W T Z ) (19)
is the orthogonal projection onto T W O ( p ) T_WO(p) T W O ( p ) (under the stated inner product) and satisfies
∥ P W ( Z ) ∥ F ≤ ∥ Z ∥ F . (20) \lVert P_W(Z)\rVert_F\leq\lVert Z\rVert_F. \tag*{(20)} ∥ P W ( Z ) ∥ F ≤ ∥ Z ∥ F . (20)
We remark that the displays (16) and (19) are the orthogonal-group specializations of Absil et al. [2 Examples 3.5.3 and 3.6.2] ; see also Edelman et al. [13 Section 2.2.1] .
For a differentiable function F F F on O ( p ) O(p) O ( p ) , grad W F \operatorname{grad}_W F grad W F is the unique tangent vector satisfying
⟨ grad W F , ξ ⟩ = D F ( W ) [ ξ ] , ξ ∈ T W O ( p ) . (21) \langle\operatorname{grad}_W F,\xi\rangle=DF(W)[\xi],\qquad\xi\in T_WO(p). \tag*{(21)} ⟨ grad W F , ξ ⟩ = D F ( W ) [ ξ ] , ξ ∈ T W O ( p ) . (21)
If ∇ W F \nabla_W F ∇ W F is the Euclidean gradient of any differentiable ambient extension of F F F , then
grad W F = P W ( ∇ W F ) = ∇ W F − W sym ( W T ∇ W F ) . (22) \operatorname{grad}_W F=P_W(\nabla_W F)=\nabla_W F-W\operatorname{sym}(W^{\mathsf{T}}\nabla_W F). \tag*{(22)} grad W F = P W ( ∇ W F ) = ∇ W F − W sym ( W T ∇ W F ) . (22)
The projected expression is independent of the chosen extension. For twice continuously differentiable F F F , the Riemannian Hessian is given by
Hess W F ( W ) [ ξ ] = P W { d d t grad W F ( γ ( t ) ) ∣ t = 0 } , (23) \operatorname{Hess}_W F(W)[\xi]=P_W\left\{\left.\frac{d}{dt}\operatorname{grad}_W F(\gamma(t))\right|_{t=0}\right\}, \tag*{(23)} Hess W F ( W ) [ ξ ] = P W { d t d grad W F ( γ ( t )) t = 0 } , (23)
where γ \gamma γ is any smooth curve in O ( p ) O(p) O ( p ) with γ ( 0 ) = W \gamma(0)=W γ ( 0 ) = W and γ ˙ ( 0 ) = ξ \dot{\gamma}(0)=\xi γ ˙ ( 0 ) = ξ . This is the Riemannian covariant derivative of the gradient, which is further illustrated in Section 5 of Absil et al. [2 ] .
We use the following conditions at the target u ⋆ u^\star u ⋆ .
Assumption A1. The pairs ( A i , B i ) (A_i,B_i) ( A i , B i ) , i = 1 , … , n i=1,\ldots,n i = 1 , … , n , are independent and identically distributed, A i = A i T A_i=A_i^{\mathsf{T}} A i = A i T , B i = B i T B_i=B_i^{\mathsf{T}} B i = B i T , and diag ( B i ) = 0 \operatorname{diag}(B_i)=0 diag ( B i ) = 0 almost surely. Moreover, 2 ≤ κ < p 2\leq\kappa<p 2 ≤ κ < p .
Assumption A2. There exists ν n > 0 \nu_n>0 ν n > 0 such that, for every a , b ∈ { 1 , … , p } a,b\in\{1,\ldots,p\} a , b ∈ { 1 , … , p } and every pair of unit vectors x , y ∈ R p x,y\in\mathbb{R}^p x , y ∈ R p ,
∥ B i , a b x T A i y ∥ ψ 1 ≤ ν n . (24) \lVert B_{i,ab}x^{\mathsf{T}}A_i y\rVert_{\psi_1}\leq\nu_n. \tag*{(24)} ∥ B i , ab x T A i y ∥ ψ 1 ≤ ν n . (24)
Assumption A3. There are a nonempty compact smooth embedded submanifold W ⋆ ⊂ O ( p ) \mathcal{W}^\star\subset O(p) W ⋆ ⊂ O ( p ) and J ⋆ ∈ R J^\star\in\mathbb{R} J ⋆ ∈ R such that
J ( U , u ⋆ ) = J ⋆ , grad W J ( U , u ⋆ ) = 0 , U ∈ W ⋆ . (25) \mathcal{J}(U,u^\star)=J^\star,\qquad\operatorname{grad}_W\mathcal{J}(U,u^\star)=0,\qquad U\in\mathcal{W}^\star. \tag*{(25)} J ( U , u ⋆ ) = J ⋆ , grad W J ( U , u ⋆ ) = 0 , U ∈ W ⋆ . (25) There is also a rank-κ \kappa κ projector Π ⋆ \Pi^\star Π ⋆ satisfying
U P V ⋆ U T = Π ⋆ , U ∈ W ⋆ . (26) UP_{V^\star}U^{\mathsf{T}}=\Pi^\star,\qquad U\in\mathcal{W}^\star. \tag*{(26)} U P V ⋆ U T = Π ⋆ , U ∈ W ⋆ . (26)
The set contains every unselected-column completion: if U ∈ W ⋆ U \in\mathcal{W}^{\star} U ∈ W ⋆ , R ∈ O ( p ) R \in O(p) R ∈ O ( p ) , and R P V ⋆ = P V ⋆ RP_{V^{\star}} = P_{V^{\star}} R P V ⋆ = P V ⋆ , then U R ∈ W ⋆ UR \in\mathcal{W}^{\star} U R ∈ W ⋆ .
Assumption A4. There exists α n > 0 \alpha_n > 0 α n > 0 such that, for every U ∈ W ⋆ U \in\mathcal{W}^{\star} U ∈ W ⋆ and every ξ ∈ T U O ( p ) \xi\in T_UO(p) ξ ∈ T U O ( p ) orthogonal to T U W ⋆ T_U\mathcal{W}^{\star} T U W ⋆ ,
− ⟨ ξ , Hess W W J ( U , u ⋆ ) [ ξ ] ⟩ ≥ α n ∥ ξ ∥ F 2 . (27) -\langle\xi, \operatorname{Hess}_{WW}\mathcal{J}(U,u^{\star})[\xi]\rangle\ge\alpha_n\lVert\xi\rVert_F^2. \tag*{(27)} − ⟨ ξ , Hess W W J ( U , u ⋆ ) [ ξ ]⟩ ≥ α n ∥ ξ ∥ F 2 . (27)
Assumption A5. There exists m n > 0 m_n > 0 m n > 0 such that
inf U ∈ W ⋆ [ min a ∈ V ⋆ { 2 D 0 ( U ) u ⋆ } a − max { 0 , max b ∉ V ⋆ { 2 D 0 ( U ) u ⋆ } b } ] ≥ m n . (28) \inf_{U\in\mathcal{W}^{\star}}\left[\min_{a\in V^{\star}}\{2D_0(U)u^{\star}\}_a-\max\left\{0,\max_{b\notin V^{\star}}\{2D_0(U)u^{\star}\}_b\right\}\right]\ge m_n. \tag*{(28)} U ∈ W ⋆ inf [ a ∈ V ⋆ min { 2 D 0 ( U ) u ⋆ } a − max { 0 , b ∈ / V ⋆ max { 2 D 0 ( U ) u ⋆ } b } ] ≥ m n . (28)
The diagonal restriction in A1 applies only to B i B_i B i . In particular,
{ D n ( W ) } a a = { D 0 ( W ) } a a = 0 , a = 1 , … , p , (29) \{D_n(W)\}_{aa}=\{D_0(W)\}_{aa}=0,\qquad a=1,\ldots,p, \tag*{(29)} { D n ( W ) } aa = { D 0 ( W ) } aa = 0 , a = 1 , … , p , (29)
whereas a zero diagonal of A i A_i A i would not generally be preserved by the transformation W T A i W W^{\mathsf{T}}A_iW W T A i W .
The completion requirement in A3 ensures that the distance to W ⋆ \mathcal{W}^{\star} W ⋆ is finite in both connected components of O ( p ) O(p) O ( p ) . Write e j e_j e j for the j j j th standard basis vector of R p \mathbb{R}^p R p . Choose j ∉ V ⋆ j\notin V^{\star} j ∈ / V ⋆ and set
R j = I p − 2 e j e j T . (30) R_j=I_p-2e_je_j^{\mathsf{T}}. \tag*{(30)} R j = I p − 2 e j e j T . (30)
Then R j P V ⋆ = P V ⋆ R j = P V ⋆ R_jP_{V^{\star}}=P_{V^{\star}}R_j=P_{V^{\star}} R j P V ⋆ = P V ⋆ R j = P V ⋆ and det ( R j ) = − 1 \det(R_j)=-1 det ( R j ) = − 1 . Hence, for every U ∈ W ⋆ U\in\mathcal{W}^{\star} U ∈ W ⋆ ,
( U R j ) P V ⋆ = U P V ⋆ , ( U R j ) P V ⋆ ( U R j ) T = Π ⋆ , (31) (UR_j)P_{V^{\star}}=UP_{V^{\star}},\qquad(UR_j)P_{V^{\star}}(UR_j)^{\mathsf{T}}=\Pi^{\star}, \tag*{(31)} ( U R j ) P V ⋆ = U P V ⋆ , ( U R j ) P V ⋆ ( U R j ) T = Π ⋆ , (31)
but det ( U R j ) = − det ( U ) \det(UR_j)=-\det(U) det ( U R j ) = − det ( U ) . Thus W ⋆ \mathcal{W}^{\star} W ⋆ intersects both components. For every W ∈ O ( p ) W\in O(p) W ∈ O ( p ) ,
d O ( W , W ⋆ ) = inf U ∈ W ⋆ det ( U ) = det ( W ) d O ( W , U ) , (32) d_O(W,\mathcal{W}^{\star})=
\inf_{\substack{U\in\mathcal{W}^{\star}\\ \det(U)=\det(W)}}d_O(W,U), \tag*{(32)} d O ( W , W ⋆ ) = U ∈ W ⋆ d e t ( U ) = d e t ( W ) inf d O ( W , U ) , (32)
and the infimum is finite and attained. If W 1 W_1 W 1 and W 2 W_2 W 2 lie in the same component, the triangle inequality gives
∣ d O ( W 1 , W ⋆ ) − d O ( W 2 , W ⋆ ) ∣ ≤ d O ( W 1 , W 2 ) . (33) \left|d_O(W_1,\mathcal{W}^{\star})-d_O(W_2,\mathcal{W}^{\star})\right|\le d_O(W_1,W_2). \tag*{(33)} ∣ d O ( W 1 , W ⋆ ) − d O ( W 2 , W ⋆ ) ∣ ≤ d O ( W 1 , W 2 ) . (33)
Consequently, W ↦ d O ( W , W ⋆ ) W\mapsto d_O(W,\mathcal{W}^{\star}) W ↦ d O ( W , W ⋆ ) is continuous on each component and hence on O ( p ) O(p) O ( p ) , because the two components are both open and closed.
Condition A4 permits directions tangent to W ⋆ \mathcal{W}^{\star} W ⋆ to remain unidentified and requires curvature only in directions normal to the stationary manifold W ⋆ \mathcal{W}^{\star} W ⋆ . Condition A5 is the corresponding strict first-order requirement for the support block. To make the support requirement explicit, fix U ∈ W ⋆ U\in\mathcal{W}^{\star} U ∈ W ⋆ and write
g ( U ) = ∇ s J ( U , u ⋆ ) = 2 D 0 ( U ) u ⋆ . (34) g(U)=\nabla_s\mathcal{J}(U,u^{\star})=2D_0(U)u^{\star}. \tag*{(34)} g ( U ) = ∇ s J ( U , u ⋆ ) = 2 D 0 ( U ) u ⋆ . (34)
Equations (29) and (34) imply
g a ( U ) = 2 ∑ ℓ ∈ V ⋆ ∖ { a } { D 0 ( U ) } a ℓ , a ∈ V ⋆ , (35) g_a(U)=2\sum_{\ell\in V^{\star}\setminus\{a\}}\{D_0(U)\}_{a\ell},\qquad a\in V^{\star}, \tag*{(35)} g a ( U ) = 2 ℓ ∈ V ⋆ ∖ { a } ∑ { D 0 ( U ) } a ℓ , a ∈ V ⋆ , (35)
g b ( U ) = 2 ∑ ℓ ∈ V ⋆ { D 0 ( U ) } b ℓ , b ∉ V ⋆ , (36) g_b(U)=2\sum_{\ell\in V^{\star}}\{D_0(U)\}_{b\ell},\qquad b\notin V^{\star}, \tag*{(36)} g b ( U ) = 2 ℓ ∈ V ⋆ ∑ { D 0 ( U ) } b ℓ , b ∈ / V ⋆ , (36)
where
{ D 0 ( U ) } a ℓ = E [ B i , a ℓ ( U e a ) T A i ( U e ℓ ) ] . (37) \{D_0(U)\}_{a\ell}=\mathbb{E}\left[B_{i,a\ell}(Ue_a)^{\mathsf{T}}A_i(Ue_\ell)\right]. \tag*{(37)} { D 0 ( U ) } a ℓ = E [ B i , a ℓ ( U e a ) T A i ( U e ℓ ) ] . (37)
Thus (28) compares every selected (active) coordinate’s aggregate within-support SC–FC alignment with both zero and every outside (inactive) coordinate’s aggregate alignment.
A vector d d d is a feasible first-order direction from u ⋆ u^{\star} u ⋆ if and only if
d a ≤ 0 ( a ∈ V ⋆ ) , d b ≥ 0 ( b ∉ V ⋆ ) , 1 T d ≤ 0. (38) d_a\le0\quad(a\in V^{\star}),\qquad d_b\ge0\quad(b\notin V^{\star}),\qquad\mathbf{1}^{\mathsf{T}}d\le0. \tag*{(38)} d a ≤ 0 ( a ∈ V ⋆ ) , d b ≥ 0 ( b ∈ / V ⋆ ) , 1 T d ≤ 0. (38)
The directions − e a -e_a − e a and e b − e a e_b-e_a e b − e a remove active mass and replace active mass by inactive mass, respectively; their directional derivatives are − g a ( U ) -g_a(U) − g a ( U ) and g b ( U ) − g a ( U ) g_b(U)-g_a(U) g b ( U ) − g a ( U ) . The comparison with zero in (28) is therefore essential since (2) permits active mass to be removed without being reallocated.
More generally, for d d d satisfying (38) , set
A d = − ∑ a ∈ V ⋆ d a , B d = ∑ b ∉ V ⋆ d b , c ( U ) = max { 0 , max b ∉ V ⋆ g b ( U ) } . (39) A_d=-\sum_{a\in V^\star}d_a,\qquad B_d=\sum_{b\notin V^\star}d_b,\qquad c(U)=\max\left\{0,\max_{b\notin V^\star}g_b(U)\right\}. \tag*{(39)} A d = − a ∈ V ⋆ ∑ d a , B d = b ∈ / V ⋆ ∑ d b , c ( U ) = max { 0 , b ∈ / V ⋆ max g b ( U ) } . (39)
Then 0 ≤ B d ≤ A d 0\le B_d\le A_d 0 ≤ B d ≤ A d , and (28) implies
⟨ g ( U ) , d ⟩ = − ∑ a ∈ V ⋆ g a ( U ) ( − d a ) + ∑ b ∉ V ⋆ g b ( U ) d b ≤ − { c ( U ) + m n } A d + c ( U ) B d ≤ − m n A d ≤ − m n 2 ∥ d ∥ 1 . (40) \begin{aligned}
\langle g(U),d\rangle=-\sum_{a\in V^\star}g_a(U)(-d_a)+\sum_{b\notin V^\star}g_b(U)d_b \\
&\le-\{c(U)+m_n\}A_d+c(U)B_d\le-m_nA_d\le-\frac{m_n}{2}\lVert d\rVert_1. \tag*{(40)}
\end{aligned} ⟨ g ( U ) , d ⟩ = − a ∈ V ⋆ ∑ g a ( U ) ( − d a ) + b ∈ / V ⋆ ∑ g b ( U ) d b ≤ − { c ( U ) + m n } A d + c ( U ) B d ≤ − m n A d ≤ − 2 m n ∥ d ∥ 1 . (40)
Hence the directional derivative is uniformly negative along every nonzero feasible direction.
For x > 0 x>0 x > 0 , define
R n ( x ) = 2 log p + p log 9 + x , η n ( x ) = C ν n { R n ( x ) n + R n ( x ) n } . (41) R_n(x)=2\log p+p\log9+x,\qquad\eta_n(x)=C\nu_n\left\{\sqrt{\frac{R_n(x)}{n}}+\frac{R_n(x)}{n}\right\}. \tag*{(41)} R n ( x ) = 2 log p + p log 9 + x , η n ( x ) = C ν n { n R n ( x ) + n R n ( x ) } . (41)
where C > 0 C>0 C > 0 is a universal constant. For a , b ∈ { 1 , … , p } a,b\in\{1,\ldots,p\} a , b ∈ { 1 , … , p } , let
H a b = 1 n ∑ i = 1 n B i , a b A i − E ( B i , a b A i ) , (42) H_{ab}=\frac{1}{n}\sum_{i=1}^{n}B_{i,ab}A_i-\mathbb{E}(B_{i,ab}A_i), \tag*{(42)} H ab = n 1 i = 1 ∑ n B i , ab A i − E ( B i , ab A i ) , (42)
and define
G x = { max a , b ∥ H a b ∥ o p ≤ η n ( x ) } . (43) \mathcal{G}_x=\left\{\max_{a,b}\lVert H_{ab}\rVert_{\mathrm{op}}\le\eta_n(x)\right\}. \tag*{(43)} G x = { a , b max ∥ H ab ∥ op ≤ η n ( x ) } . (43)
Lemma 1 bounds max a , b ∥ H a b ∥ o p \max_{a,b}\lVert H_{ab}\rVert_{\mathrm{op}} max a , b ∥ H ab ∥ op and gives the probability of G x \mathcal{G}_x G x .
Lemma 1. Under A1–A2, the universal constant in (41) can be chosen so that
P ( G x ) ≥ 1 − 2 e − x . (44) \mathbb{P}(\mathcal{G}_x)\ge1-2e^{-x}. \tag*{(44)} P ( G x ) ≥ 1 − 2 e − x . (44)
Proof. Fix a , b a,b a , b and a unit vector z ∈ R p z\in\mathbb{R}^p z ∈ R p . The variables
Y i = B i , a b z T A i z − E ( B i , a b z T A i z ) (45) Y_i=B_{i,ab}z^\mathsf{T}A_i z-\mathbb{E}(B_{i,ab}z^\mathsf{T}A_i z) \tag*{(45)} Y i = B i , ab z T A i z − E ( B i , ab z T A i z ) (45)
are independent and centered. By (24), Jensen’s inequality, and the triangle inequality for the ψ 1 \psi_1 ψ 1 norm, ∥ Y i ∥ ψ 1 ≤ C 0 ν n \lVert Y_i\rVert_{\psi_1}\le C_0\nu_n ∥ Y i ∥ ψ 1 ≤ C 0 ν n for a universal constant C 0 C_0 C 0 . The sub-exponential Bernstein inequality [43 ] therefore yields
P ( ∣ z T H a b z ∣ > t ) ≤ 2 exp [ − c n min { t 2 ν n 2 , t ν n } ] , t > 0 , (46) \mathbb{P}\left(\left|z^\mathsf{T}H_{ab}z\right|>t\right)\le2\exp\left[-cn\min\left\{\frac{t^2}{\nu_n^2},\frac{t}{\nu_n}\right\}\right],\qquad t>0, \tag*{(46)} P ( z T H ab z > t ) ≤ 2 exp [ − c n min { ν n 2 t 2 , ν n t } ] , t > 0 , (46)
for a universal constant c > 0 c>0 c > 0 .
Let N \mathcal{N} N be a 1 / 4 1/4 1/4 -net of the unit sphere in R p \mathbb{R}^p R p with ∣ N ∣ ≤ 9 p |\mathcal{N}|\le9^p ∣ N ∣ ≤ 9 p . Because H a b H_{ab} H ab is symmetric,
∥ H a b ∥ o p ≤ 2 max z ∈ N ∣ z T H a b z ∣ . (47) \lVert H_{ab}\rVert_{\mathrm{op}}\le2\max_{z\in\mathcal{N}}\left|z^\mathsf{T}H_{ab}z\right|. \tag*{(47)} ∥ H ab ∥ op ≤ 2 z ∈ N max z T H ab z . (47)
Indeed, for every unit vector v v v , choose z ∈ N z\in\mathcal{N} z ∈ N such that ∥ v − z ∥ 2 ≤ 1 / 4 \lVert v-z\rVert_2\le1/4 ∥ v − z ∥ 2 ≤ 1/4 . Then
∣ v T H a b v ∣ ≤ ∣ z T H a b z ∣ + 1 2 ∥ H a b ∥ o p . (48) \left|v^\mathsf{T}H_{ab}v\right|\le\left|z^\mathsf{T}H_{ab}z\right|+\frac{1}{2}\lVert H_{ab}\rVert_{\mathrm{op}}. \tag*{(48)} v T H ab v ≤ z T H ab z + 2 1 ∥ H ab ∥ op . (48)
A union bound over at most p 2 9 p p^2 9^p p 2 9 p pairs and net points yields
P ( max a , b ∥ H a b ∥ o p > 2 t ) ≤ 2 exp [ 2 log p + p log 9 − c n min { t 2 ν n 2 , t ν n } ] . (49) \mathbb{P}\left(\max_{a,b}\lVert H_{ab}\rVert_{\mathrm{op}}>2t\right)\le2\exp\left[2\log p+p\log9-cn\min\left\{\frac{t^2}{\nu_n^2},\frac{t}{\nu_n}\right\}\right]. \tag*{(49)} P ( a , b max ∥ H ab ∥ op > 2 t ) ≤ 2 exp [ 2 log p + p log 9 − c n min { ν n 2 t 2 , ν n t } ] . (49)
Taking t = C 1 ν n { R n ( x ) / n + R n ( x ) / n } t=C_1\nu_n\{\sqrt{R_n(x)/n}+R_n(x)/n\} t = C 1 ν n { R n ( x ) / n + R n ( x ) / n } with C 1 C_1 C 1 sufficiently large makes the exponent in (49) at most − x -x − x . Absorbing the fixed constants into C C C in (41) proves (44) .
Define
M 0 = max a , b ∥ E ( B i , a b A i ) ∥ o p . (50) M_0=\max_{a,b}\left\|\mathbb{E}(B_{i,ab}A_i)\right\|_{\mathrm{op}}. \tag*{(50)} M 0 = a , b max ∥ E ( B i , ab A i ) ∥ op . (50)
This quantity is finite under A2. Indeed, symmetry and (24) imply
∥ E ( B i , a b A i ) ∥ o p = sup ∥ z ∥ 2 = 1 ∣ E ( B i , a b z ⊤ A i z ) ∣ ≤ C 0 ν n . (51) \left\|\mathbb{E}(B_{i,ab}A_i)\right\|_{\mathrm{op}}=\sup_{\|z\|_2=1}\left|\mathbb{E}(B_{i,ab}z^{\top}A_i z)\right|\le C_0\nu_n. \tag*{(51)} ∥ E ( B i , ab A i ) ∥ op = ∥ z ∥ 2 = 1 sup E ( B i , ab z ⊤ A i z ) ≤ C 0 ν n . (51)
The possible dependence of M 0 M_0 M 0 on n n n and p p p is suppressed.
Lemma 2 bounds ( J ˉ n − J ) ( W , s ) (\bar{J}_n-\mathcal{J})(W,s) ( J ˉ n − J ) ( W , s ) and ∇ s ( J ˉ n − J ) ( W , s ) \nabla_s(\bar{J}_n-\mathcal{J})(W,s) ∇ s ( J ˉ n − J ) ( W , s ) uniformly on O ( p ) × S κ O(p)\times\mathcal{S}_{\kappa} O ( p ) × S κ using G x \mathcal{G}_x G x .
Lemma 2. Under A1–A2, on G x \mathcal{G}_x G x , uniformly over W ∈ O ( p ) W\in O(p) W ∈ O ( p ) and s ∈ S κ s\in\mathcal{S}_{\kappa} s ∈ S κ ,
(i) ∣ ( J ˉ n − J ) ( W , s ) ∣ ≤ κ 2 η n ( x ) \left|(\bar{J}_n-\mathcal{J})(W,s)\right|\le\kappa^2\eta_n(x) ( J ˉ n − J ) ( W , s ) ≤ κ 2 η n ( x ) ,
(ii) ∥ ∇ s ( J ˉ n − J ) ( W , s ) ∥ ∞ ≤ 2 κ η n ( x ) \left\|\nabla_s(\bar{J}_n-\mathcal{J})(W,s)\right\|_\infty\le2\kappa\eta_n(x) ∇ s ( J ˉ n − J ) ( W , s ) ∞ ≤ 2 κ η n ( x ) .
Proof. Write w a w_a w a for column a a a of W W W . The symmetry in A1 gives H a b = H b a = H a b ⊤ H_{ab}=H_{ba}=H_{ab}^{\top} H ab = H ba = H ab ⊤ . Expanding J ˉ n \bar{J}_n J ˉ n and (11) yields
( J ˉ n − J ) ( W , s ) = ∑ a , b = 1 p s a s b w a ⊤ H a b w b . (52) (\bar{J}_n-\mathcal{J})(W,s)=\sum_{a,b=1}^{p}s_as_bw_a^{\top}H_{ab}w_b. \tag*{(52)} ( J ˉ n − J ) ( W , s ) = a , b = 1 ∑ p s a s b w a ⊤ H ab w b . (52)
Since s ≥ 0 s\ge0 s ≥ 0 , 1 ⊤ s ≤ κ 1^{\top}s\le\kappa 1 ⊤ s ≤ κ , and ∥ w a ∥ 2 = 1 \|w_a\|_2=1 ∥ w a ∥ 2 = 1 , the event (43) implies
∣ ( J ˉ n − J ) ( W , s ) ∣ ≤ η n ( x ) ∑ a , b = 1 p s a s b = η n ( x ) ( 1 ⊤ s ) 2 ≤ κ 2 η n ( x ) , (53) \left|(\bar{J}_n-\mathcal{J})(W,s)\right|\le\eta_n(x)\sum_{a,b=1}^{p}s_as_b=\eta_n(x)(1^{\top}s)^2\le\kappa^2\eta_n(x), \tag*{(53)} ( J ˉ n − J ) ( W , s ) ≤ η n ( x ) a , b = 1 ∑ p s a s b = η n ( x ) ( 1 ⊤ s ) 2 ≤ κ 2 η n ( x ) , (53)
which is (52). The a a a th coordinate of the support-gradient difference is
2 ∑ b = 1 p s b w a ⊤ H a b w b . (54) 2\sum_{b=1}^{p}s_bw_a^{\top}H_{ab}w_b. \tag*{(54)} 2 b = 1 ∑ p s b w a ⊤ H ab w b . (54)
Equation (43) bounds the absolute value of (54) by 2 η n ( x ) 1 ⊤ s ≤ 2 κ η n ( x ) 2\eta_n(x)1^{\top}s\le2\kappa\eta_n(x) 2 η n ( x ) 1 ⊤ s ≤ 2 κ η n ( x ) , proving (53). □
Lemma 3 bounds grad W ( J ˉ n − J ) ( W , u ⋆ ) \operatorname{grad}_W(\bar{J}_n-\mathcal{J})(W,u^\star) grad W ( J ˉ n − J ) ( W , u ⋆ ) and the change in grad W J ˉ n ( W , s ) \operatorname{grad}_W\bar{J}_n(W,s) grad W J ˉ n ( W , s ) when s s s is replaced by u ⋆ u^\star u ⋆ .
Lemma 3. Under A1–A2, on G x \mathcal{G}_x G x , uniformly over W ∈ O ( p ) W\in O(p) W ∈ O ( p ) and s ∈ S κ s\in\mathcal{S}_{\kappa} s ∈ S κ ,
(i) ∥ grad W ( J ˉ n − J ) ( W , u ⋆ ) ∥ F ≤ 2 ( κ − 1 ) κ η n ( x ) \left\|\operatorname{grad}_W(\bar{J}_n-\mathcal{J})(W,u^\star)\right\|_F\le2(\kappa-1)\sqrt{\kappa}\,\eta_n(x) grad W ( J ˉ n − J ) ( W , u ⋆ ) F ≤ 2 ( κ − 1 ) κ η n ( x ) ,
(ii) ∥ grad W J ˉ n ( W , s ) − grad W J ˉ n ( W , u ⋆ ) ∥ F ≤ 2 ( κ + κ ) { M 0 + η n ( x ) } ∥ s − u ⋆ ∥ 1 \left\|\operatorname{grad}_W\bar{J}_n(W,s)-\operatorname{grad}_W\bar{J}_n(W,u^\star)\right\|_F\le2(\kappa+\sqrt{\kappa})\{M_0+\eta_n(x)\}\|s-u^\star\|_1 grad W J ˉ n ( W , s ) − grad W J ˉ n ( W , u ⋆ ) F ≤ 2 ( κ + κ ) { M 0 + η n ( x )} ∥ s − u ⋆ ∥ 1 .
Proof. Write w a w_a w a for column a a a of W W W . The Euclidean W W W -gradient of the stochastic difference at u ⋆ u^\star u ⋆ has column a a a
2 u a ⋆ ∑ b ∈ V ⋆ H a b w b . (55) 2u_a^\star\sum_{b\in V^\star}H_{ab}w_b. \tag*{(55)} 2 u a ⋆ b ∈ V ⋆ ∑ H ab w b . (55)
Equations A1 and (42) give H a a = 0 H_{aa}=0 H aa = 0 . Hence each of the at most κ \kappa κ possibly nonzero columns in (55) has norm at most 2 ( κ − 1 ) η n ( x ) 2(\kappa-1)\eta_n(x) 2 ( κ − 1 ) η n ( x ) , and the Euclidean gradient has Frobenius norm at most 2 ( κ − 1 ) κ η n ( x ) 2(\kappa-1)\sqrt{\kappa}\,\eta_n(x) 2 ( κ − 1 ) κ η n ( x ) . Applying (20) proves (57).
For (58), let
M ^ a b = 1 n ∑ i = 1 n B i , a b A i , h = s − u ⋆ . (56) \widehat{M}_{ab}=\frac{1}{n}\sum_{i=1}^{n}B_{i,ab}A_i,\qquad h=s-u^\star. \tag*{(56)} M ab = n 1 i = 1 ∑ n B i , ab A i , h = s − u ⋆ . (56)
Equations (43) and (50) imply
max a , b ∥ M ^ a b ∥ o p ≤ M 0 + η n ( x ) . (57) \max_{a,b}\left\|\widehat{M}_{ab}\right\|_{\mathrm{op}}\le M_0+\eta_n(x). \tag*{(57)} a , b max M ab op ≤ M 0 + η n ( x ) . (57)
The difference between column a a a of the two Euclidean gradients is
2 h a ∑ b = 1 p s b M ^ a b w b + 2 u a ⋆ ∑ b = 1 p h b M ^ a b w b . (58) 2h_a\sum_{b=1}^{p}s_b\widehat{M}_{ab}w_b+2u_a^\star\sum_{b=1}^{p}h_b\widehat{M}_{ab}w_b. \tag*{(58)} 2 h a b = 1 ∑ p s b M ab w b + 2 u a ⋆ b = 1 ∑ p h b M ab w b . (58)
By (57) , the matrices formed by the first and second terms in (58) have Frobenius norms at most
2 κ { M 0 + η n ( x ) } ∥ h ∥ 2 and 2 κ { M 0 + η n ( x ) } ∥ h ∥ 1 , (59) 2\kappa\{M_0+\eta_n(x)\}\|h\|_2 \qquad\text{and}\qquad2\sqrt{\kappa}\{M_0+\eta_n(x)\}\|h\|_1, \tag*{(59)} 2 κ { M 0 + η n ( x )} ∥ h ∥ 2 and 2 κ { M 0 + η n ( x )} ∥ h ∥ 1 , (59)
respectively. Since ∥ h ∥ 2 ≤ ∥ h ∥ 1 \|h\|_2\leq\|h\|_1 ∥ h ∥ 2 ≤ ∥ h ∥ 1 , the Euclidean-gradient difference is bounded by the right-hand side of (58). Both gradients are evaluated at the same W W W , so (22) applies the same linear map P W P_W P W to both. Equation (20) therefore proves (58) for the Riemannian gradients.
Bounds near W ⋆ × { u ⋆ } W^\star\times\{u^\star\} W ⋆ × { u ⋆ }
Lemma 4 relates the distance to W ⋆ W^\star W ⋆ to the population gradient norm and objective loss through (64) and (65) below.
Lemma 4. Under Assumptions A1–A4, there exists ρ 2 , n > 0 \rho_{2,n}>0 ρ 2 , n > 0 such that, for every W ∈ O ( p ) W\in O(p) W ∈ O ( p ) , d O ( W , W ⋆ ) ≤ ρ 2 , n d_O(W,W^\star)\leq\rho_{2,n} d O ( W , W ⋆ ) ≤ ρ 2 , n implies
(i) ∥ grad W J ( W , u ⋆ ) ∥ F ≥ α n 2 d O ( W , W ⋆ ) \|\operatorname{grad}_W\mathcal{J}(W,u^\star)\|_F\geq\frac{\alpha_n}{2}d_O(W,W^\star) ∥ grad W J ( W , u ⋆ ) ∥ F ≥ 2 α n d O ( W , W ⋆ ) ,
(ii) J ⋆ − J ( W , u ⋆ ) ≥ α n 4 d O ( W , W ⋆ ) 2 \mathcal{J}^\star-\mathcal{J}(W,u^\star)\geq\frac{\alpha_n}{4}d_O(W,W^\star)^2 J ⋆ − J ( W , u ⋆ ) ≥ 4 α n d O ( W , W ⋆ ) 2 .
Proof. Equation (24) implies that every coefficient defining J \mathcal{J} J is finite. Since (12) is a finite polynomial in the entries of W W W and s s s , the map ( W , s ) ↦ J ( W , s ) (W,s)\mapsto\mathcal{J}(W,s) ( W , s ) ↦ J ( W , s ) is smooth. By Lee [26, Theorem 5.25], the tubular-neighborhood theorem applied within each connected component of O ( p ) O(p) O ( p ) gives a radius ρ 1 , n > 0 \rho_{1,n}>0 ρ 1 , n > 0 on which the normal exponential map around W ⋆ W^\star W ⋆ is one-to-one. By Lee [26, Theorem 6.40], the radius can be chosen so that every W W W satisfying d O ( W , W ⋆ ) < ρ 1 , n d_O(W,W^\star)<\rho_{1,n} d O ( W , W ⋆ ) < ρ 1 , n has the unique representation
W = Exp U ( W ) ( ξ W ) , W=\operatorname{Exp}_{U(W)}(\xi_W), W = Exp U ( W ) ( ξ W ) ,
U ( W ) ∈ W ⋆ , ξ W ∈ T U ( W ) O ( p ) , ξ W ⊥ T U ( W ) W ⋆ , U(W)\in W^\star,\qquad
\xi_W\in T_{U(W)}O(p),\qquad\xi_W\perp T_{U(W)}W^\star, U ( W ) ∈ W ⋆ , ξ W ∈ T U ( W ) O ( p ) , ξ W ⊥ T U ( W ) W ⋆ ,
∥ ξ W ∥ F = d O ( W , W ⋆ ) . (60) \|\xi_W\|_F=d_O(W,W^\star). \tag*{(60)} ∥ ξ W ∥ F = d O ( W , W ⋆ ) . (60)
The same metric tubular-neighborhood result also gives the converse distance identity
d O ( Exp U ( ζ ) , W ⋆ ) = ∥ ζ ∥ F (61) d_O(\operatorname{Exp}_U(\zeta),W^\star)=\|\zeta\|_F \tag*{(61)} d O ( Exp U ( ζ ) , W ⋆ ) = ∥ ζ ∥ F (61)
for every U ∈ W ⋆ U\in W^\star U ∈ W ⋆ and every ζ ∈ T U O ( p ) \zeta\in T_UO(p) ζ ∈ T U O ( p ) satisfying ζ ⊥ T U W ⋆ \zeta\perp T_UW^\star ζ ⊥ T U W ⋆ and ∥ ζ ∥ F < ρ 1 , n \|\zeta\|_F<\rho_{1,n} ∥ ζ ∥ F < ρ 1 , n . The two componentwise radii can be replaced by their minimum because W ⋆ W^\star W ⋆ intersects both components by (31) .
We next extend the curvature in (27) uniformly to nearby points. Consider
K = { ( U , ν ) ∈ W ⋆ × R p × p : ν ∈ T U O ( p ) , ν ⊥ T U W ⋆ , ∥ ν ∥ F = 1 } . (62) \mathcal{K}=\{(U,\nu)\in W^\star\times\mathbb{R}^{p\times p}:\nu\in T_UO(p),\ \nu\perp T_UW^\star,\ \|\nu\|_F=1\}. \tag*{(62)} K = {( U , ν ) ∈ W ⋆ × R p × p : ν ∈ T U O ( p ) , ν ⊥ T U W ⋆ , ∥ ν ∥ F = 1 } . (62)
The set K \mathcal{K} K is compact. Indeed, take any sequence ( U j , ν j ) (U_j,\nu_j) ( U j , ν j ) in K \mathcal{K} K . Compactness of W ⋆ W^\star W ⋆ and of the Euclidean unit sphere yields a subsequence converging to some ( U , ν ) (U,\nu) ( U , ν ) . The identities U j T ν j + ν j T U j = 0 U_j^{\mathsf T}\nu_j+\nu_j^{\mathsf T}U_j=0 U j T ν j + ν j T U j = 0 pass to the limit, so ν ∈ T U O ( p ) \nu\in T_UO(p) ν ∈ T U O ( p ) by (16) . A smooth local parametrization of W ⋆ W^\star W ⋆ around U U U allows every vector in T U W ⋆ T_UW^\star T U W ⋆ to be approximated by vectors in T U j W ⋆ T_{U_j}W^\star T U j W ⋆ . Passing to the limit in the corresponding inner products gives ν ⊥ T U W ⋆ \nu\perp T_UW^\star ν ⊥ T U W ⋆ . Thus ( U , ν ) ∈ K (U,\nu)\in\mathcal{K} ( U , ν ) ∈ K , so K \mathcal{K} K is a closed subset of a compact set.
For ( U , ν ) ∈ K (U,\nu)\in\mathcal{K} ( U , ν ) ∈ K , define
γ U , ν ( r ) = Exp U ( r ν ) , ζ U , ν ( r ) = d d r γ U , ν ( r ) . (63) \gamma_{U,\nu}(r)=\operatorname{Exp}_U(r\nu),\qquad
\zeta_{U,\nu}(r)=\frac{d}{dr}\gamma_{U,\nu}(r). \tag*{(63)} γ U , ν ( r ) = Exp U ( r ν ) , ζ U , ν ( r ) = d r d γ U , ν ( r ) . (63)
Lee [26, Proposition 5.19(b)–(c)] implies that (63) is a geodesic and depends smoothly on ( U , ν , r ) (U,\nu,r) ( U , ν , r ) . Therefore
Φ ( U , ν , r ) = ⟨ ζ U , ν ( r ) , Hess W W J ( γ U , ν ( r ) , u ⋆ ) [ ζ U , ν ( r ) ] ⟩ (64) \Phi(U,\nu,r)=\left\langle\zeta_{U,\nu}(r),\operatorname{Hess}_{WW}\mathcal{J}(\gamma_{U,\nu}(r),u^\star)[\zeta_{U,\nu}(r)]\right\rangle \tag*{(64)} Φ ( U , ν , r ) = ⟨ ζ U , ν ( r ) , Hess W W J ( γ U , ν ( r ) , u ⋆ ) [ ζ U , ν ( r )] ⟩ (64)
is continuous. At r = 0 r=0 r = 0 , ζ U , ν ( 0 ) = ν \zeta_{U,\nu}(0)=\nu ζ U , ν ( 0 ) = ν , and (27) gives Φ ( U , ν , 0 ) ≤ − α n \Phi(U,\nu,0)\leq-\alpha_n Φ ( U , ν , 0 ) ≤ − α n on K \mathcal{K} K . Compactness of (62) therefore yields a radius satisfying
0 < ρ 2 , n < ρ 1 , n (65) 0<\rho_{2,n}<\rho_{1,n} \tag*{(65)} 0 < ρ 2 , n < ρ 1 , n (65)
such that
Φ ( U , ν , r ) ≤ − α n 2 , ( U , ν ) ∈ K , 0 ≤ r ≤ ρ 2 , n . (66) \Phi(U,\nu,r) \le-\frac{\alpha_n}{2}, \qquad(U,\nu) \in\mathcal{K}, \qquad0 \le r \le\rho_{2,n}. \tag*{(66)} Φ ( U , ν , r ) ≤ − 2 α n , ( U , ν ) ∈ K , 0 ≤ r ≤ ρ 2 , n . (66)
Fix W W W with d O ( W , W ⋆ ) ≤ ρ 2 , n d_O(W,W^\star) \le\rho_{2,n} d O ( W , W ⋆ ) ≤ ρ 2 , n and use (60) . If ξ W ≠ 0 \xi_W \ne0 ξ W = 0 , let
ν W = ξ W ∥ ξ W ∥ F , γ W ( t ) = Exp U ( W ) ( t ξ W ) , q W ( t ) = J ( γ W ( t ) , u ⋆ ) . (67) \nu_W=\frac{\xi_W}{\|\xi_W\|_F}, \qquad\gamma_W(t)=\operatorname{Exp}_{U(W)}(t\xi_W), \qquad q_W(t)=\mathcal{J}(\gamma_W(t),u^\star). \tag*{(67)} ν W = ∥ ξ W ∥ F ξ W , γ W ( t ) = Exp U ( W ) ( t ξ W ) , q W ( t ) = J ( γ W ( t ) , u ⋆ ) . (67)
Then
γ ˙ W ( t ) = ∥ ξ W ∥ F ζ U ( W ) , ν W ( t ∥ ξ W ∥ F ) , ∥ γ ˙ W ( t ) ∥ F = ∥ ξ W ∥ F . (68) \dot{\gamma}_W(t)=\|\xi_W\|_F\zeta_{U(W),\nu_W}(t\|\xi_W\|_F), \qquad\|\dot{\gamma}_W(t)\|_F=\|\xi_W\|_F. \tag*{(68)} γ ˙ W ( t ) = ∥ ξ W ∥ F ζ U ( W ) , ν W ( t ∥ ξ W ∥ F ) , ∥ γ ˙ W ( t ) ∥ F = ∥ ξ W ∥ F . (68)
Since γ W \gamma_W γ W is a geodesic, Absil et al. [2 ] , Definition 5.5.1 and Proposition 5.5.2 yields
q W ′ ′ ( t ) = ⟨ γ ˙ W ( t ) , Hess W W J ( γ W ( t ) , u ⋆ ) [ γ ˙ W ( t ) ] ⟩ ≤ − α n 2 ∥ ξ W ∥ F 2 , 0 ≤ t ≤ 1 , (69) q_W^{\prime\prime}(t)=\left\langle\dot{\gamma}_W(t),\operatorname{Hess}_{WW}\mathcal{J}(\gamma_W(t),u^\star)[\dot{\gamma}_W(t)]\right\rangle
\le-\frac{\alpha_n}{2}\|\xi_W\|_F^2,\qquad0\le t\le1, \tag*{(69)} q W ′′ ( t ) = ⟨ γ ˙ W ( t ) , Hess W W J ( γ W ( t ) , u ⋆ ) [ γ ˙ W ( t )] ⟩ ≤ − 2 α n ∥ ξ W ∥ F 2 , 0 ≤ t ≤ 1 , (69)
where the inequality follows from (66) and (68) . Equation (25) gives
q W ′ ( 0 ) = ⟨ grad W J ( U ( W ) , u ⋆ ) , ξ W ⟩ = 0. (70) q_W^\prime(0)=\left\langle\operatorname{grad}_W\mathcal{J}(U(W),u^\star),\xi_W\right\rangle=0. \tag*{(70)} q W ′ ( 0 ) = ⟨ grad W J ( U ( W ) , u ⋆ ) , ξ W ⟩ = 0. (70)
Integrating (69) once and using (68) yields
α n 2 ∥ ξ W ∥ F 2 ≤ − q W ′ ( 1 ) ≤ ∥ grad W J ( W , u ⋆ ) ∥ F ∥ ξ W ∥ F . (71) \frac{\alpha_n}{2}\|\xi_W\|_F^2\le-q_W^\prime(1)\le\|\operatorname{grad}_W\mathcal{J}(W,u^\star)\|_F\|\xi_W\|_F. \tag*{(71)} 2 α n ∥ ξ W ∥ F 2 ≤ − q W ′ ( 1 ) ≤ ∥ grad W J ( W , u ⋆ ) ∥ F ∥ ξ W ∥ F . (71)
Equations (60) and (71) prove (64). Taylor’s expansion, together with (70) and (69) , yields
J ( W , u ⋆ ) = J ⋆ + ∫ 0 1 ( 1 − t ) q W ′ ′ ( t ) d t ≤ J ⋆ − α n 4 ∥ ξ W ∥ F 2 . (72) \mathcal{J}(W,u^\star)=\mathcal{J}^\star+\int_0^1(1-t)q_W^{\prime\prime}(t)\,dt\le\mathcal{J}^\star-\frac{\alpha_n}{4}\|\xi_W\|_F^2. \tag*{(72)} J ( W , u ⋆ ) = J ⋆ + ∫ 0 1 ( 1 − t ) q W ′′ ( t ) d t ≤ J ⋆ − 4 α n ∥ ξ W ∥ F 2 . (72)
Equations (60) and (72) prove (65). □
Lemma 5 shows that the selected-coordinate derivatives of J ( W , s ) \mathcal{J}(W,s) J ( W , s ) remain positive and uniformly exceed the unselected-coordinate derivatives throughout (73) below.
Lemma 5. Under Assumptions A1–A5, there is r 0 ∈ ( 0 , 1 ) r_0\in(0,1) r 0 ∈ ( 0 , 1 ) , possibly depending on n n n and p p p , such that every ( W , s ) ∈ O ( p ) × S κ (W,s)\in O(p)\times S_\kappa ( W , s ) ∈ O ( p ) × S κ satisfying
d O ( W , W ⋆ ) ≤ r 0 , ∥ s − u ⋆ ∥ 2 ≤ r 0 (73) d_O(W,W^\star)\le r_0,\qquad\|s-u^\star\|_2\le r_0 \tag*{(73)} d O ( W , W ⋆ ) ≤ r 0 , ∥ s − u ⋆ ∥ 2 ≤ r 0 (73) also satisfies
min a ∈ V ⋆ { 2 D 0 ( W ) s } a − max { 0 , max b ∉ V ⋆ { 2 D 0 ( W ) s } b } ≥ 3 m n 4 . (74) \min_{a\in V^\star}\{2D_0(W)s\}_a-\max\left\{0,\max_{b\notin V^\star}\{2D_0(W)s\}_b\right\}\ge\frac{3m_n}{4}. \tag*{(74)} a ∈ V ⋆ min { 2 D 0 ( W ) s } a − max { 0 , b ∈ / V ⋆ max { 2 D 0 ( W ) s } b } ≥ 4 3 m n . (74)
Proof. Define
Δ ( W , s ) = min a ∈ V ⋆ { 2 D 0 ( W ) s } a − max { 0 , max b ∉ V ⋆ { 2 D 0 ( W ) s } b } . (75) \Delta(W,s)=\min_{a\in V^\star}\{2D_0(W)s\}_a-\max\left\{0,\max_{b\notin V^\star}\{2D_0(W)s\}_b\right\}. \tag*{(75)} Δ ( W , s ) = a ∈ V ⋆ min { 2 D 0 ( W ) s } a − max { 0 , b ∈ / V ⋆ max { 2 D 0 ( W ) s } b } . (75)
The map in (75) is continuous. By (28) and compactness of W ⋆ W^\star W ⋆ , there exists ρ 3 , n > 0 \rho_{3,n}>0 ρ 3 , n > 0 such that
Δ ( W , s ) ≥ 3 m n 4 (76) \Delta(W,s)\ge\frac{3m_n}{4} \tag*{(76)} Δ ( W , s ) ≥ 4 3 m n (76)
whenever d O ( W , W ⋆ ) ≤ ρ 3 , n d_O(W,W^\star)\le\rho_{3,n} d O ( W , W ⋆ ) ≤ ρ 3 , n and ∥ s − u ⋆ ∥ 2 ≤ ρ 3 , n \|s-u^\star\|_2\le\rho_{3,n} ∥ s − u ⋆ ∥ 2 ≤ ρ 3 , n . Let
L 0 , n = sup W ∈ O ( p ) ∥ D 0 ( W ) ∥ o p . (77) L_{0,n}=\sup_{W\in O(p)}\|D_0(W)\|_{\mathrm{op}}. \tag*{(77)} L 0 , n = W ∈ O ( p ) sup ∥ D 0 ( W ) ∥ op . (77)
Equations (11) and (50) imply L 0 , n ≤ p M 0 < ∞ L_{0,n}\le pM_0<\infty L 0 , n ≤ p M 0 < ∞ . Choose r 0 r_0 r 0 so that
0 < r 0 ≤ min { ρ 2 , n , ρ 3 , n , 1 2 } , r 0 L 0 , n ≤ m n 8 . (78) 0<r_0\le\min\left\{\rho_{2,n},\rho_{3,n},\frac{1}{2}\right\},\qquad r_0L_{0,n}\le\frac{m_n}{8}. \tag*{(78)} 0 < r 0 ≤ min { ρ 2 , n , ρ 3 , n , 2 1 } , r 0 L 0 , n ≤ 8 m n . (78)
The choice r 0 ≤ ρ 3 , n r_0\le\rho_{3,n} r 0 ≤ ρ 3 , n and (76) prove (74) . □
Corollary 1 bounds J ⋆ − J ( W , s ) J^\star-\mathcal{J}(W,s) J ⋆ − J ( W , s ) using d O ( W , W ⋆ ) d_O(W,W^\star) d O ( W , W ⋆ ) and ∥ s − u ⋆ ∥ 1 \lVert s-u^\star\rVert_1 ∥ s − u ⋆ ∥ 1 .
Corollary 1. Under Assumptions A1–A5, the radius r 0 r_0 r 0 satisfying (84) can be chosen so that every ( W , s ) ∈ O ( p ) × S κ (W,s)\in O(p)\times S_\kappa ( W , s ) ∈ O ( p ) × S κ satisfying (79) obeys
J ⋆ − J ( W , s ) ≥ α n 4 d O ( W , W ⋆ ) 2 + m n 4 ∥ s − u ⋆ ∥ 1 . (79) J^\star-\mathcal{J}(W,s)\ge\frac{\alpha_n}{4}d_O(W,W^\star)^2+\frac{m_n}{4}\lVert s-u^\star\rVert_1. \tag*{(79)} J ⋆ − J ( W , s ) ≥ 4 α n d O ( W , W ⋆ ) 2 + 4 m n ∥ s − u ⋆ ∥ 1 . (79)
Proof. Let
h = s − u ⋆ , A s = ∑ a ∈ V ⋆ ( 1 − s a ) , B s = ∑ b ∉ V ⋆ s b . (80) h=s-u^\star,\qquad A_s=\sum_{a\in V^\star}(1-s_a),\qquad B_s=\sum_{b\notin V^\star}s_b. \tag*{(80)} h = s − u ⋆ , A s = a ∈ V ⋆ ∑ ( 1 − s a ) , B s = b ∈ / V ⋆ ∑ s b . (80)
Feasibility in (2) gives 0 ≤ B s ≤ A s 0\le B_s\le A_s 0 ≤ B s ≤ A s and
∥ h ∥ 1 = A s + B s ≤ 2 A s . (81) \lVert h\rVert_1=A_s+B_s\le2A_s. \tag*{(81)} ∥ h ∥ 1 = A s + B s ≤ 2 A s . (81)
Equations (79) and (84) give d O ( W , W ⋆ ) ≤ r 0 ≤ ρ 3 , n d_O(W,W^\star)\le r_0\le\rho_{3,n} d O ( W , W ⋆ ) ≤ r 0 ≤ ρ 3 , n . Thus (82) applies with s = u ⋆ s=u^\star s = u ⋆ . Using 0 ≤ B s ≤ A s 0\le B_s\le A_s 0 ≤ B s ≤ A s and (82), we obtain
⟨ 2 D 0 ( W ) u ⋆ , u ⋆ − s ⟩ = ∑ a ∈ V ⋆ { 2 D 0 ( W ) u ⋆ } a ( 1 − s a ) − ∑ b ∉ V ⋆ { 2 D 0 ( W ) u ⋆ } b s b ≥ A s min a ∈ V ⋆ { 2 D 0 ( W ) u ⋆ } a − B s max { 0 , max b ∉ V ⋆ { 2 D 0 ( W ) u ⋆ } b } ≥ A s [ min a ∈ V ⋆ { 2 D 0 ( W ) u ⋆ } a − max { 0 , max b ∉ V ⋆ { 2 D 0 ( W ) u ⋆ } b } ] ≥ 3 m n 4 A s ≥ 3 m n 8 ∥ s − u ⋆ ∥ 1 . (82) \begin{aligned}
\langle2D_0(W)u^\star,u^\star-s\rangle
&=\sum_{a\in V^\star}\{2D_0(W)u^\star\}_a(1-s_a)-\sum_{b\notin V^\star}\{2D_0(W)u^\star\}_bs_b\\
&\ge A_s\min_{a\in V^\star}\{2D_0(W)u^\star\}_a-B_s\max\left\{0,\max_{b\notin V^\star}\{2D_0(W)u^\star\}_b\right\}\\
&\ge A_s\left[\min_{a\in V^\star}\{2D_0(W)u^\star\}_a-\max\left\{0,\max_{b\notin V^\star}\{2D_0(W)u^\star\}_b\right\}\right]\\
&\ge\frac{3m_n}{4}A_s\ge\frac{3m_n}{8}\lVert s-u^\star\rVert_1. \tag*{(82)}
\end{aligned} ⟨ 2 D 0 ( W ) u ⋆ , u ⋆ − s ⟩ = a ∈ V ⋆ ∑ { 2 D 0 ( W ) u ⋆ } a ( 1 − s a ) − b ∈ / V ⋆ ∑ { 2 D 0 ( W ) u ⋆ } b s b ≥ A s a ∈ V ⋆ min { 2 D 0 ( W ) u ⋆ } a − B s max { 0 , b ∈ / V ⋆ max { 2 D 0 ( W ) u ⋆ } b } ≥ A s [ a ∈ V ⋆ min { 2 D 0 ( W ) u ⋆ } a − max { 0 , b ∈ / V ⋆ max { 2 D 0 ( W ) u ⋆ } b } ] ≥ 4 3 m n A s ≥ 8 3 m n ∥ s − u ⋆ ∥ 1 . (82)
The following identity
J ( W , u ⋆ ) − J ( W , s ) = ⟨ 2 D 0 ( W ) u ⋆ , u ⋆ − s ⟩ − h ⊤ D 0 ( W ) h (83) \mathcal{J}(W,u^\star)-\mathcal{J}(W,s)=\langle2D_0(W)u^\star,u^\star-s\rangle-h^\top D_0(W)h \tag*{(83)} J ( W , u ⋆ ) − J ( W , s ) = ⟨ 2 D 0 ( W ) u ⋆ , u ⋆ − s ⟩ − h ⊤ D 0 ( W ) h (83)
and (88) yield
J ( W , u ⋆ ) − J ( W , s ) ≥ 3 m n 8 ∥ h ∥ 1 − ∥ D 0 ( W ) ∥ o p ∥ h ∥ 2 2 . (84) \mathcal{J}(W,u^\star)-\mathcal{J}(W,s)\ge\frac{3m_n}{8}\lVert h\rVert_1-\lVert D_0(W)\rVert_{\mathrm{op}}\lVert h\rVert_2^2. \tag*{(84)} J ( W , u ⋆ ) − J ( W , s ) ≥ 8 3 m n ∥ h ∥ 1 − ∥ D 0 ( W ) ∥ op ∥ h ∥ 2 2 . (84)
If ∥ h ∥ 2 ≤ r 0 \lVert h\rVert_2\le r_0 ∥ h ∥ 2 ≤ r 0 , then ∥ h ∥ 2 2 ≤ r 0 ∥ h ∥ 1 \lVert h\rVert_2^2\le r_0\lVert h\rVert_1 ∥ h ∥ 2 2 ≤ r 0 ∥ h ∥ 1 . Equations (90) and (84) therefore give
J ( W , u ⋆ ) − J ( W , s ) ≥ m n 4 ∥ s − u ⋆ ∥ 1 . (85) \mathcal{J}(W,u^\star)-\mathcal{J}(W,s)\ge\frac{m_n}{4}\lVert s-u^\star\rVert_1. \tag*{(85)} J ( W , u ⋆ ) − J ( W , s ) ≥ 4 m n ∥ s − u ⋆ ∥ 1 . (85)
Equations (79) and (84) give d O ( W , W ⋆ ) ≤ r 0 ≤ ρ 2 , n d_O(W,W^\star)\le r_0\le\rho_{2,n} d O ( W , W ⋆ ) ≤ r 0 ≤ ρ 2 , n , so (65) applies. Combining (65) and (91) proves (85).
For an empirical pair ( W , s ) (W,s) ( W , s ) , define
r W ( W , s ) = ∥ grad W J ‾ n ( W , s ) ∥ F , r s ( W , s ) = sup v ∈ S κ ⟨ ∇ s J ‾ n ( W , s ) , v − s ⟩ . (86) r_W(W,s)=\lVert\operatorname{grad}_W\overline{J}_n(W,s)\rVert_F,\qquad r_s(W,s)=\sup_{v\in S_\kappa}\langle\nabla_s\overline{J}_n(W,s),v-s\rangle. \tag*{(86)} r W ( W , s ) = ∥ grad W J n ( W , s ) ∥ F , r s ( W , s ) = v ∈ S κ sup ⟨ ∇ s J n ( W , s ) , v − s ⟩ . (86)
The second residual is nonnegative because v = s v=s v = s is feasible. It is the maximum of a linear function over the compact convex set in (2). Both residuals are zero at a local maximizer.
For rank-κ \kappa κ orthogonal projectors P P P and Q Q Q , Θ ( P , Q ) \Theta(P,Q) Θ ( P , Q ) denotes the diagonal matrix of principal angles between their ranges.
Let ( W ^ , s ^ ) ∈ O ( p ) × S κ (\widehat W,\widehat s)\in O(p)\times S_\kappa ( W , s ) ∈ O ( p ) × S κ and ε W , ε s ≥ 0 \varepsilon_W,\varepsilon_s\ge0 ε W , ε s ≥ 0 satisfy
d O ( W ^ , W ⋆ ) < r 0 , ∥ s ^ − u ⋆ ∥ 2 < r 0 , (87) d_O(\widehat W,W^\star)<r_0,\qquad\lVert\widehat s-u^\star\rVert_2<r_0, \tag*{(87)} d O ( W , W ⋆ ) < r 0 , ∥ s − u ⋆ ∥ 2 < r 0 , (87)
r_W(\widehat W,\widehat s)\le\varepsilon_W,\qquad r_s(\widehat W,\widehat s)\le\varepsilon_s.
{#eq:94}
For the following residual bounds, suppose that
\eta_n(x)\le\frac{m_n}{16\kappa}.
{#eq:95}
Theorem 2 bounds ∥ s ^ − u ⋆ ∥ 1 \lVert\widehat s-u^\star\rVert_1 ∥ s − u ⋆ ∥ 1 using r s ( W ^ , s ^ ) r_s(\widehat W,\widehat s) r s ( W , s ) .
Theorem 2. Under Assumptions A1–A5, on G x G_x G x , conditions (87) –(95) imply
(i) ∥ s ^ − u ⋆ ∥ 1 ≤ 4 ε s m n \|\widehat{s}-u^\star\|_1 \le\frac{4\varepsilon_s}{m_n} ∥ s − u ⋆ ∥ 1 ≤ m n 4 ε s , (96)
(ii) min a ∈ V ⋆ s ^ a > max b ∉ V ⋆ s ^ b \min_{a\in V^\star}\widehat{s}_a > \max_{b\notin V^\star}\widehat{s}_b min a ∈ V ⋆ s a > max b ∈ / V ⋆ s b , Top κ ( s ^ ) = V ⋆ \operatorname{Top}_{\kappa}(\widehat{s})=V^\star Top κ ( s ) = V ⋆ (97)
In particular, ε s = 0 \varepsilon_s=0 ε s = 0 implies s ^ = u ⋆ \widehat{s}=u^\star s = u ⋆ .
Proof. Equations (74) and (53) imply
min a ∈ V ⋆ { ∇ s J ‾ n ( W ^ , s ^ ) } a − max { 0 , max b ∉ V ⋆ { ∇ s J ‾ n ( W ^ , s ^ ) } b } ≥ 3 m n 4 − 4 κ η n ( x ) ≥ m n 2 . (88) \min_{a\in V^\star}\{\nabla_s\overline{J}_n(\widehat{W},\widehat{s})\}_a-\max\left\{0,\max_{b\notin V^\star}\{\nabla_s\overline{J}_n(\widehat{W},\widehat{s})\}_b\right\}\ge\frac{3m_n}{4}-4\kappa\eta_n(x)\ge\frac{m_n}{2}. \tag*{(88)} a ∈ V ⋆ min { ∇ s J n ( W , s ) } a − max { 0 , b ∈ / V ⋆ max { ∇ s J n ( W , s ) } b } ≥ 4 3 m n − 4 κ η n ( x ) ≥ 2 m n . (88)
where the last inequality uses (95).
Define
A ^ = ∑ a ∈ V ⋆ ( 1 − s ^ a ) , B ^ = ∑ b ∉ V ⋆ s ^ b . (89) \widehat{A}=\sum_{a\in V^\star}(1-\widehat{s}_a),\qquad\widehat{B}=\sum_{b\notin V^\star}\widehat{s}_b. \tag*{(89)} A = a ∈ V ⋆ ∑ ( 1 − s a ) , B = b ∈ / V ⋆ ∑ s b . (89)
Feasibility gives 0 ≤ B ^ ≤ A ^ 0\le\widehat{B}\le\widehat{A} 0 ≤ B ≤ A . As in the mass comparison leading to (82) , the empirical score gap in (88) yields
⟨ ∇ s J ‾ n ( W ^ , s ^ ) , u ⋆ − s ^ ⟩ ≥ A ^ [ min a ∈ V ⋆ { ∇ s J ‾ n ( W ^ , s ^ ) } a − max { 0 , max b ∉ V ⋆ { ∇ s J ‾ n ( W ^ , s ^ ) } b } ] ≥ m n 2 A ^ . (90) \left\langle\nabla_s\overline{J}_n(\widehat{W},\widehat{s}),u^\star-\widehat{s}\right\rangle
\ge\widehat{A}\left[\min_{a\in V^\star}\{\nabla_s\overline{J}_n(\widehat{W},\widehat{s})\}_a-\max\left\{0,\max_{b\notin V^\star}\{\nabla_s\overline{J}_n(\widehat{W},\widehat{s})\}_b\right\}\right]
\ge\frac{m_n}{2}\widehat{A}. \tag*{(90)} ⟨ ∇ s J n ( W , s ) , u ⋆ − s ⟩ ≥ A [ a ∈ V ⋆ min { ∇ s J n ( W , s ) } a − max { 0 , b ∈ / V ⋆ max { ∇ s J n ( W , s ) } b } ] ≥ 2 m n A . (90)
Since u ⋆ ∈ S κ u^\star\in S_\kappa u ⋆ ∈ S κ , (86) and (94) bound the left-hand side of (90) by ε s \varepsilon_s ε s . Thus
A ^ ≤ 2 ε s m n , ∥ s ^ − u ⋆ ∥ 1 = A ^ + B ^ ≤ 4 ε s m n , (91) \widehat{A}\le\frac{2\varepsilon_s}{m_n},\qquad\|\widehat{s}-u^\star\|_1=\widehat{A}+\widehat{B}\le\frac{4\varepsilon_s}{m_n}, \tag*{(91)} A ≤ m n 2 ε s , ∥ s − u ⋆ ∥ 1 = A + B ≤ m n 4 ε s , (91)
which proves (96).
For every coordinate j j j , (87) and (78) give
∣ s ^ j − u j ⋆ ∣ ≤ ∥ s ^ − u ⋆ ∥ 2 < r 0 ≤ 1 2 . (92) |\widehat{s}_j-u^\star_j|\le\|\widehat{s}-u^\star\|_2<r_0\le\frac{1}{2}. \tag*{(92)} ∣ s j − u j ⋆ ∣ ≤ ∥ s − u ⋆ ∥ 2 < r 0 ≤ 2 1 . (92)
Consequently, s ^ a > 1 / 2 \widehat{s}_a>1/2 s a > 1/2 for a ∈ V ⋆ a\in V^\star a ∈ V ⋆ and s ^ b < 1 / 2 \widehat{s}_b<1/2 s b < 1/2 for b ∉ V ⋆ b\notin V^\star b ∈ / V ⋆ , which proves (97). The last assertion follows from (96) with ε s = 0 \varepsilon_s=0 ε s = 0 .
We denote
b n ( x , ε W , ε s ) = 2 α n { ε W + 2 ( κ − 1 ) κ η n ( x ) + 8 ( κ + κ ) { M 0 + η n ( x ) } ε s m n } . (93) b_n(x,\varepsilon_W,\varepsilon_s)=\frac{2}{\alpha_n}\left\{\varepsilon_W+2(\kappa-1)\sqrt{\kappa}\,\eta_n(x)+\frac{8(\kappa+\sqrt{\kappa})\{M_0+\eta_n(x)\}\varepsilon_s}{m_n}\right\}. \tag*{(93)} b n ( x , ε W , ε s ) = α n 2 { ε W + 2 ( κ − 1 ) κ η n ( x ) + m n 8 ( κ + κ ) { M 0 + η n ( x )} ε s } . (93)
Corollary 2 bounds d O ( W ^ , W ⋆ ) d_O(\widehat{W},W^\star) d O ( W , W ⋆ ) in terms of ε W \varepsilon_W ε W , ε s \varepsilon_s ε s , and η n ( x ) \eta_n(x) η n ( x ) .
Corollary 2. Under Assumptions A1–A5, on G x G_x G x , conditions (87) –(95) imply
d V ⋆ ( W ^ , W ⋆ ) ≤ d O ( W ^ , W ⋆ ) ≤ b n ( x , ε W , ε s ) . (94) d_{V^\star}(\widehat{W},W^\star)\le d_O(\widehat{W},W^\star)\le b_n(x,\varepsilon_W,\varepsilon_s). \tag*{(94)} d V ⋆ ( W , W ⋆ ) ≤ d O ( W , W ⋆ ) ≤ b n ( x , ε W , ε s ) . (94)
Proof. For the alignment bound, the triangle inequality, followed by (58), (57), (94), and (96), yields
∥ grad W J ( W ^ , u ⋆ ) ∥ F ≤ r W ( W ^ , s ^ ) + ∥ grad W J ‾ n ( W ^ , s ^ ) − grad W J ‾ n ( W ^ , u ⋆ ) ∥ F + ∥ grad W ( J ‾ n − J ) ( W ^ , u ⋆ ) ∥ F ≤ ε W + 8 ( κ + κ ) { M 0 + η n ( x ) } ε s m n + 2 ( κ − 1 ) κ η n ( x ) . (95) \begin{aligned}
\|\operatorname{grad}_W J(\widehat{W},u^\star)\|_F
\le r_W(\widehat{W},\widehat{s})+\|\operatorname{grad}_W\overline{J}_n(\widehat{W},\widehat{s})-\operatorname{grad}_W\overline{J}_n(\widehat{W},u^\star)\|_F+\|\operatorname{grad}_W(\overline{J}_n-J)(\widehat{W},u^\star)\|_F \\
&\le\varepsilon_W+\frac{8(\kappa+\sqrt{\kappa})\{M_0+\eta_n(x)\}\varepsilon_s}{m_n}+2(\kappa-1)\sqrt{\kappa}\,\eta_n(x). \tag*{(95)}
\end{aligned} ∥ grad W J ( W , u ⋆ ) ∥ F ≤ r W ( W , s ) + ∥ grad W J n ( W , s ) − grad W J n ( W , u ⋆ ) ∥ F + ∥ grad W ( J n − J ) ( W , u ⋆ ) ∥ F ≤ ε W + m n 8 ( κ + κ ) { M 0 + η n ( x )} ε s + 2 ( κ − 1 ) κ η n ( x ) . (95)
Combining (64) and (105) gives the upper bound on d O d_O d O in (94) .
For every U ∈ W ⋆ U\in\mathcal{W}^\star U ∈ W ⋆ , the chordal distance is no larger than the geodesic distance, so
∥ ( W ^ − U ) P V ⋆ ∥ F ≤ ∥ W ^ − U ∥ F ≤ d O ( W ^ , U ) . (96) \|(\widehat{W}-U)P_{V^\star}\|_F\le\|\widehat{W}-U\|_F\le d_O(\widehat{W},U). \tag*{(96)} ∥ ( W − U ) P V ⋆ ∥ F ≤ ∥ W − U ∥ F ≤ d O ( W , U ) . (96)
Taking the infimum in (105) proves d V ⋆ ≤ d O d_{V^\star}\le d_O d V ⋆ ≤ d O in (94) .
Corollary 3 transfers (104) to W ^ P V ⋆ W ^ T − Π ⋆ \widehat{W}P_{V_\star}\widehat{W}^{\mathsf T}-\Pi^\star W P V ⋆ W T − Π ⋆ .
Corollary 3. Under Assumptions A1–A5, on G x \mathcal{G}_x G x , conditions (93)–(95) imply
∥ W ^ P V ⋆ W ^ T − Π ⋆ ∥ F 2 ≤ 2 b n ( x , ε W , ε s ) , (97) \left\|\widehat{W}P_{V_\star}\widehat{W}^{\mathsf T}-\Pi^\star\right\|_{F}^{2}\le2b_n(x,\varepsilon_W,\varepsilon_s), \tag*{(97)} W P V ⋆ W T − Π ⋆ F 2 ≤ 2 b n ( x , ε W , ε s ) , (97) (ii)
∥ sin Θ ( W ^ P V ⋆ W ^ T , Π ⋆ ) ∥ F 2 ≤ 2 b n ( x , ε W , ε s ) 2 . (98) \left\|\sin\Theta\left(\widehat{W}P_{V_\star}\widehat{W}^{\mathsf T},\Pi^\star\right)\right\|_{F}^{2}\le2b_n(x,\varepsilon_W,\varepsilon_s)^2. \tag*{(98)} sin Θ ( W P V ⋆ W T , Π ⋆ ) F 2 ≤ 2 b n ( x , ε W , ε s ) 2 . (98)
Proof. For every U ∈ W ⋆ U\in\mathcal{W}^\star U ∈ W ⋆ , (26) gives
W ^ P V ⋆ W ^ T − Π ⋆ = ( W ^ − U ) P V ⋆ W ^ T + U P V ⋆ ( W ^ − U ) T . (99) \widehat{W}P_{V_\star}\widehat{W}^{\mathsf T}-\Pi^\star=(\widehat{W}-U)P_{V_\star}\widehat{W}^{\mathsf T}+UP_{V_\star}(\widehat{W}-U)^{\mathsf T}. \tag*{(99)} W P V ⋆ W T − Π ⋆ = ( W − U ) P V ⋆ W T + U P V ⋆ ( W − U ) T . (99)
The Frobenius norm of each term on the right-hand side of (108) is at most ∥ ( W ^ − U ) P V ⋆ ∥ F \|(\widehat{W}-U)P_{V_\star}\|_{F} ∥ ( W − U ) P V ⋆ ∥ F . Taking the infimum over U ∈ W ⋆ U\in\mathcal{W}^\star U ∈ W ⋆ yields
∥ W ^ P V ⋆ W ^ T − Π ⋆ ∥ F ≤ 2 d V ⋆ ( W ^ , W ⋆ ) , (100) \left\|\widehat{W}P_{V_\star}\widehat{W}^{\mathsf T}-\Pi^\star\right\|_{F}\le2d_{V_\star}(\widehat{W},\mathcal{W}^\star), \tag*{(100)} W P V ⋆ W T − Π ⋆ F ≤ 2 d V ⋆ ( W , W ⋆ ) , (100)
which proves (106). Finally, rank-κ \kappa κ orthogonal projectors P P P and Q Q Q satisfy
∥ P − Q ∥ F 2 = 2 κ − 2 Tr ( P Q ) = 2 ∥ sin Θ ( P , Q ) ∥ F 2 . (101) \|P-Q\|_{F}^{2}=2\kappa-2\operatorname{Tr}(PQ)=2\|\sin\Theta(P,Q)\|_{F}^{2}. \tag*{(101)} ∥ P − Q ∥ F 2 = 2 κ − 2 Tr ( P Q ) = 2∥ sin Θ ( P , Q ) ∥ F 2 . (101)
Equations (106) and (110) prove (107).
Existence of an empirical local maximizer
All interiors and boundaries in this section are taken relative to
X κ = O ( p ) × S κ . (102) \mathcal{X}_{\kappa}=O(p)\times\mathcal{S}_{\kappa}. \tag*{(102)} X κ = O ( p ) × S κ . (102)
For 0 < r < r 0 0<r<r_0 0 < r < r 0 , define
N ‾ r = { ( W , s ) ∈ X κ : d O ( W , W ⋆ ) ≤ r , ∥ s − u ⋆ ∥ 2 ≤ r } , (103) \overline{\mathcal{N}}_r=\{(W,s)\in\mathcal{X}_{\kappa}:d_O(W,\mathcal{W}^\star)\le r,\ \|s-u^\star\|_2\le r\}, \tag*{(103)} N r = {( W , s ) ∈ X κ : d O ( W , W ⋆ ) ≤ r , ∥ s − u ⋆ ∥ 2 ≤ r } , (103)
and
N r = { ( W , s ) ∈ X κ : d O ( W , W ⋆ ) < r , ∥ s − u ⋆ ∥ 2 < r } . (104) \mathcal{N}_r=\{(W,s)\in\mathcal{X}_{\kappa}:d_O(W,\mathcal{W}^\star)<r,\ \|s-u^\star\|_2<r\}. \tag*{(104)} N r = {( W , s ) ∈ X κ : d O ( W , W ⋆ ) < r , ∥ s − u ⋆ ∥ 2 < r } . (104)
The following lemma characterizes the relative boundary of the set above.
Lemma 6. The relative boundary of (112) is
∂ X κ N ‾ r = B r = { ( W , s ) ∈ X κ : d O ( W , W ⋆ ) = r , ∥ s − u ⋆ ∥ 2 ≤ r } \partial_{\mathcal{X}_{\kappa}}\overline{\mathcal{N}}_r=B_r=\{(W,s)\in\mathcal{X}_{\kappa}:d_O(W,\mathcal{W}^\star)=r,\ \|s-u^\star\|_2\le r\} ∂ X κ N r = B r = {( W , s ) ∈ X κ : d O ( W , W ⋆ ) = r , ∥ s − u ⋆ ∥ 2 ≤ r } ∪ { ( W , s ) ∈ X κ : d O ( W , W ⋆ ) ≤ r , ∥ s − u ⋆ ∥ 2 = r } . (105) \qquad\cup\{(W,s)\in\mathcal{X}_{\kappa}:d_O(W,\mathcal{W}^\star)\le r,\ \|s-u^\star\|_2=r\}. \tag*{(105)} ∪ {( W , s ) ∈ X κ : d O ( W , W ⋆ ) ≤ r , ∥ s − u ⋆ ∥ 2 = r } . (105)
Proof. The continuity of the two distance maps shows that every point in (113) is in the relative interior of N ‾ r \overline{\mathcal{N}}_r N r . Conversely, suppose ( W , s ) ∈ N ‾ r (W,s)\in\overline{\mathcal{N}}_r ( W , s ) ∈ N r and d O ( W , W ⋆ ) = r d_O(W,\mathcal{W}^\star)=r d O ( W , W ⋆ ) = r . (60) gives U ∈ W ⋆ U\in\mathcal{W}^\star U ∈ W ⋆ and ξ ⊥ T U W ⋆ \xi\perp T_U\mathcal{W}^\star ξ ⊥ T U W ⋆ such that
W = Exp U ( ξ ) , ∥ ξ ∥ F = r . (106) W=\operatorname{Exp}_U(\xi),\qquad\|\xi\|_F=r. \tag*{(106)} W = Exp U ( ξ ) , ∥ ξ ∥ F = r . (106)
For every sufficiently small δ > 0 \delta>0 δ > 0 ,
W δ = Exp U { ( 1 + δ ) ξ } , d O ( W δ , W ⋆ ) = ( 1 + δ ) r > r , W δ ⟶ W . (107) W_\delta=\operatorname{Exp}_U\{(1+\delta)\xi\},\qquad d_O(W_\delta,\mathcal{W}^\star)=(1+\delta)r>r,\qquad W_\delta\longrightarrow W. \tag*{(107)} W δ = Exp U {( 1 + δ ) ξ } , d O ( W δ , W ⋆ ) = ( 1 + δ ) r > r , W δ ⟶ W . (107)
Equations (84) and (71) give r < r 0 ≤ ρ 2 , n < ρ 1 , n r<r_0\le\rho_{2,n}<\rho_{1,n} r < r 0 ≤ ρ 2 , n < ρ 1 , n . Hence δ \delta δ can be chosen so that (116) remains in the tubular neighborhood; its asserted distance equality follows from (115) and (67). Thus ( W , s ) (W,s) ( W , s ) is not in the relative interior of N ‾ r \overline{\mathcal{N}}_r N r .
Now suppose ( W , s ) ∈ N ‾ r (W,s)\in\overline{\mathcal{N}}_r ( W , s ) ∈ N r and ∥ s − u ⋆ ∥ 2 = r \|s-u^\star\|_2=r ∥ s − u ⋆ ∥ 2 = r . Set h = s − u ⋆ h=s-u^\star h = s − u ⋆ . Feasibility gives
h a ≤ 0 ( a ∈ V ⋆ ) , h b ≥ 0 ( b ∉ V ⋆ ) , 1 T h ≤ 0. (108) h_a\le0\quad(a\in V^\star),\qquad h_b\ge0\quad(b\notin V^\star),\qquad\mathbf{1}^{\mathsf T}h\le0. \tag*{(108)} h a ≤ 0 ( a ∈ V ⋆ ) , h b ≥ 0 ( b ∈ / V ⋆ ) , 1 T h ≤ 0. (108)
Since r < r 0 < 1 r<r_0<1 r < r 0 < 1 , max j ∣ h j ∣ < 1 \max_j|h_j|<1 max j ∣ h j ∣ < 1 . Hence, for every sufficiently small δ > 0 \delta>0 δ > 0 ,
s δ = u ⋆ + ( 1 + δ ) h ∈ S κ , ∥ s δ − u ⋆ ∥ 2 = ( 1 + δ ) r > r , s δ ⟶ s . (109) s_\delta=u^\star+(1+\delta)h\in\mathcal{S}_\kappa,\qquad\|s_\delta-u^\star\|_2=(1+\delta)r>r,\qquad s_\delta\longrightarrow s. \tag*{(109)} s δ = u ⋆ + ( 1 + δ ) h ∈ S κ , ∥ s δ − u ⋆ ∥ 2 = ( 1 + δ ) r > r , s δ ⟶ s . (109)
To verify the feasibility asserted in (118), choose δ \delta δ small enough that every coordinate remains in [ 0 , 1 ] [0,1] [ 0 , 1 ] ; then
1 T s δ = κ + ( 1 + δ ) 1 T h ≤ κ (110) \mathbf{1}^{\mathsf T}s_\delta=\kappa+(1+\delta)\mathbf{1}^{\mathsf T}h\le\kappa \tag*{(110)} 1 T s δ = κ + ( 1 + δ ) 1 T h ≤ κ (110)
by (117). Thus ( W , s ) (W,s) ( W , s ) is not in the relative interior of N ‾ r \overline{\mathcal{N}}_r N r . Since N ‾ r \overline{\mathcal{N}}_r N r is relatively closed, these arguments prove (114).
Assumption A6. For 0 < r < r 0 0<r<r_0 0 < r < r 0 ,
η n ( x ) ≤ m n 16 κ , (111) \eta_n(x) \le\frac{m_n}{16\kappa}, \tag*{(111)} η n ( x ) ≤ 16 κ m n , (111) 2 κ 2 η n ( x ) < 1 4 min { α n r 2 , m n r 2 } . (112) 2\kappa^2\eta_n(x) < \frac{1}{4}\min\{\alpha_n r^2,m_n r^2\}. \tag*{(112)} 2 κ 2 η n ( x ) < 4 1 min { α n r 2 , m n r 2 } . (112)
On G x \mathcal{G}_x G x , (120a) ensures that each { ∇ s J ˉ n ( W , s ) } a \{\nabla_s\bar{J}_n(W,s)\}_a { ∇ s J ˉ n ( W , s ) } a , a ∈ V ⋆ a\in V^\star a ∈ V ⋆ , exceeds both zero and every { ∇ s J ˉ n ( W , s ) } b \{\nabla_s\bar{J}_n(W,s)\}_b { ∇ s J ˉ n ( W , s ) } b , b ∉ V ⋆ b\notin V^\star b ∈ / V ⋆ , by at least m n / 2 m_n/2 m n /2 for ( W , s ) (W,s) ( W , s ) satisfying (79), as in (98). Condition (120b) makes the uniform bound in (52) sufficiently smaller than the lower bound for J ⋆ − J ( W , s ) J^\star-\mathcal{J}(W,s) J ⋆ − J ( W , s ) on B r B_r B r as in (122) below.
Theorem 3 establishes that J ˉ n \bar{J}_n J ˉ n has local maximizers in N ‾ r \overline{N}_r N r .
Theorem 3. Under Assumptions A1–A6, on G x \mathcal{G}_x G x . Every maximizer ( W ^ , s ^ ) (\widehat{W},\widehat{s}) ( W , s ) of J ˉ n \bar{J}_n J ˉ n over N ‾ r \overline{N}_r N r is a local maximizer on X κ \mathcal{X}_\kappa X κ and satisfies
d O ( W ^ , W ⋆ ) < r , ∥ s ^ − u ⋆ ∥ 2 < r . (113) d_{\mathrm{O}}(\widehat{W},W^\star)<r,\qquad\|\widehat{s}-u^\star\|_2<r. \tag*{(113)} d O ( W , W ⋆ ) < r , ∥ s − u ⋆ ∥ 2 < r . (113) At least one such maximizer exists.
Proof. The set X κ \mathcal{X}_\kappa X κ is compact. (33) gives continuity of the set-distance, so N ‾ r \overline{N}_r N r in (112) is a nonempty compact subset of X κ \mathcal{X}_\kappa X κ . Since J ˉ n \bar{J}_n J ˉ n is continuous, it attains its maximum over N ‾ r \overline{N}_r N r .
We adapt the argument used in the proof of Theorem 3 in Ning and Liu [31 ] . The comparison is over the relative boundary in (114). For every ( W , s ) ∈ B r (W,s)\in B_r ( W , s ) ∈ B r , (85) and ∥ s − u ⋆ ∥ 1 ≥ ∥ s − u ⋆ ∥ 2 \|s-u^\star\|_1\ge\|s-u^\star\|_2 ∥ s − u ⋆ ∥ 1 ≥ ∥ s − u ⋆ ∥ 2 give
J ⋆ − J ( W , s ) ≥ 1 4 min { α n r 2 , m n r 2 } . (114) J^\star-\mathcal{J}(W,s)\ge\frac{1}{4}\min\{\alpha_n r^2,m_n r^2\}. \tag*{(114)} J ⋆ − J ( W , s ) ≥ 4 1 min { α n r 2 , m n r 2 } . (114)
The curvature term in (85) gives the α n r 2 / 4 \alpha_n r^2/4 α n r 2 /4 bound on the first face of (114), whereas its support term gives the m n r 2 / 4 m_n r^2/4 m n r 2 /4 bound on the second face. For any U ∈ W ⋆ U\in W^\star U ∈ W ⋆ , equations (52) and (122) yield
J ˉ n ( U , u ⋆ ) − J ˉ n ( W , s ) = J ⋆ − J ( W , s ) + ( J ˉ n − J ) ( U , u ⋆ ) − ( J ˉ n − J ) ( W , s ) ≥ 1 4 min { α n r 2 , m n r 2 } − 2 κ 2 η n ( x ) > 0. (115) \begin{aligned}
\bar{J}_n(U,u^\star)-\bar{J}_n(W,s)=J^\star-\mathcal{J}(W,s)+(\bar{J}_n-\mathcal{J})(U,u^\star)-(\bar{J}_n-\mathcal{J})(W,s) \\
&\ge\frac{1}{4}\min\{\alpha_n r^2,m_n r^2\}-2\kappa^2\eta_n(x)>0. \tag*{(115)}
\end{aligned} J ˉ n ( U , u ⋆ ) − J ˉ n ( W , s ) = J ⋆ − J ( W , s ) + ( J ˉ n − J ) ( U , u ⋆ ) − ( J ˉ n − J ) ( W , s ) ≥ 4 1 min { α n r 2 , m n r 2 } − 2 κ 2 η n ( x ) > 0. (115)
where the strict inequality is due to (120b). The point ( U , u ⋆ ) (U,u^\star) ( U , u ⋆ ) belongs to N ‾ r \overline{N}_r N r . Hence (123) excludes B r B_r B r from the set of restricted maximizers. By (114), every restricted maximizer belongs to N r N_r N r , proving (121).
Since N r N_r N r is open relative to X κ \mathcal{X}_\kappa X κ , every restricted maximizer has a relative neighborhood in X κ \mathcal{X}_\kappa X κ contained in N r N_r N r . It is therefore a local maximizer of J ˉ n \bar{J}_n J ˉ n on the original feasible set X κ \mathcal{X}_\kappa X κ , including when its support vector lies on a coordinate or respective face of S κ \mathcal{S}_\kappa S κ .
Corollary 4 evaluates r W r_W r W and r s r_s r s at the maximizers in Theorem 3.
Corollary 4. Under Assumptions A1–A6, on G x \mathcal{G}_x G x . Every maximizer in Theorem 3 satisfies
(i) r W ( W ^ , s ^ ) = 0 , (ii) r s ( W ^ , s ^ ) = 0. (116) \text{(i)}\quad r_W(\widehat{W},\widehat{s})=0,\qquad\text{(ii)}\quad r_s(\widehat{W},\widehat{s})=0. \tag*{(116)} (i) r W ( W , s ) = 0 , (ii) r s ( W , s ) = 0. (116)
Proof. Fix any such maximizer. Holding its support block fixed and varying the orthogonal block along smooth curves gives
grad W J ˉ n ( W ^ , s ^ ) = 0. (117) \operatorname{grad}_W\bar{J}_n(\widehat{W},\widehat{s})=0. \tag*{(117)} grad W J ˉ n ( W , s ) = 0. (117)
For every v ∈ S κ v\in\mathcal{S}_\kappa v ∈ S κ , the segment
t ⟼ s ^ + t ( v − s ^ ) , 0 ≤ t ≤ 1 , (118) t\longmapsto\widehat{s}+t(v-\widehat{s}),\qquad0\le t\le1, \tag*{(118)} t ⟼ s + t ( v − s ) , 0 ≤ t ≤ 1 , (118)
is feasible. The one-sided derivative at t = 0 t=0 t = 0 is nonpositive by local maximality, and hence
⟨ ∇ s J ˉ n ( W ^ , s ^ ) , v − s ^ ⟩ ≤ 0 , v ∈ S κ . (119) \left\langle\nabla_s\bar{J}_n(\widehat{W},\widehat{s}),v-\widehat{s}\right\rangle\le0,\qquad v\in\mathcal{S}_\kappa. \tag*{(119)} ⟨ ∇ s J ˉ n ( W , s ) , v − s ⟩ ≤ 0 , v ∈ S κ . (119)
Taking the supremum in (127), with v = s ^ v=\widehat{s} v = s attaining zero, gives r s ( W ^ , s ^ ) = 0 r_s(\widehat{W},\widehat{s})=0 r s ( W , s ) = 0 by (92). (117) gives r W ( W ^ , s ^ ) = 0 r_W(\widehat{W},\widehat{s})=0 r W ( W , s ) = 0 , proving (124).
Corollary 5 combines (116) and (96) to obtain s ^ = u ⋆ \widehat{s}=u^\star s = u ⋆ .
Corollary 5. Under Assumptions A1–A6, on G x \mathcal{G}_x G x . Every maximizer in Theorem 3 satisfies
(i) s ^ = u ⋆ , (ii) supp ( s ^ ) = Top κ ( s ^ ) = V ⋆ . (120) \begin{aligned}
\text{(i)}\quad&\widehat{s}=u^\star,\\
\text{(ii)}\quad&\operatorname{supp}(\widehat{s})=\operatorname{Top}_{\kappa}(\widehat{s})=V^\star. \tag*{(120)}
\end{aligned} (i) (ii) s = u ⋆ , supp ( s ) = Top κ ( s ) = V ⋆ . (120)
Proof. Equation (113) , (116) , and (111) verify (87) , (94), and (95), respectively, with ε W = ε s = 0 \varepsilon_W=\varepsilon_s=0 ε W = ε s = 0 . Therefore Theorem 2 applies, and (96) gives s ^ = u ⋆ \widehat{s}=u^\star s = u ⋆ . Since u ⋆ = 1 V ⋆ u^\star=\mathbf{1}_{V^\star} u ⋆ = 1 V ⋆ by definition, its support and its κ \kappa κ largest coordinates both equal V ⋆ V^\star V ⋆ , proving (120) .
Corollary 6 specializes (94) to ε W = ε s = 0 \varepsilon_W=\varepsilon_s=0 ε W = ε s = 0 .
Corollary 6. Under Assumptions A1–A6, on G x \mathcal{G}_x G x . Every maximizer in Theorem 3 satisfies
d V ⋆ ( W ^ , W ⋆ ) ≤ d O ( W ^ , W ⋆ ) ≤ 4 ( κ − 1 ) κ η n ( x ) α n . (121) d_{V^\star}(\widehat{W},W^\star)\le d_O(\widehat{W},W^\star)\le\frac{4(\kappa-1)\sqrt{\kappa}\,\eta_n(x)}{\alpha_n}. \tag*{(121)} d V ⋆ ( W , W ⋆ ) ≤ d O ( W , W ⋆ ) ≤ α n 4 ( κ − 1 ) κ η n ( x ) . (121)
Proof. Equations (113) and (116) , together with (111) , verify (87) –(95) with ε W = ε s = 0 \varepsilon_W=\varepsilon_s=0 ε W = ε s = 0 . Hence Corollary 2 applies. Equation (93) gives
b n ( x , 0 , 0 ) = 4 ( κ − 1 ) κ η n ( x ) α n . (122) b_n(x,0,0)=\frac{4(\kappa-1)\sqrt{\kappa}\,\eta_n(x)}{\alpha_n}. \tag*{(122)} b n ( x , 0 , 0 ) = α n 4 ( κ − 1 ) κ η n ( x ) . (122)
Substitution of (122) into (94) yields (121) .
Corollary 7 specializes (97) and (98) to ε W = ε s = 0 \varepsilon_W=\varepsilon_s=0 ε W = ε s = 0 .
Corollary 7. Under Assumptions A1–A6, on G x \mathcal{G}_x G x . Every maximizer in Theorem 3 satisfies
(i) ∥ W ^ P V ⋆ W ^ T − Π ⋆ ∥ F ≤ 8 ( κ − 1 ) κ η n ( x ) α n , (123) \text{(i)}\quad\left\|\widehat{W}P_{V^\star}\widehat{W}^{\mathsf{T}}-\Pi^\star\right\|_F\le\frac{8(\kappa-1)\sqrt{\kappa}\,\eta_n(x)}{\alpha_n}, \tag*{(123)} (i) W P V ⋆ W T − Π ⋆ F ≤ α n 8 ( κ − 1 ) κ η n ( x ) , (123) (ii) ∥ sin Θ ( W ^ P V ⋆ W ^ T , Π ⋆ ) ∥ F 2 ≤ 32 κ ( κ − 1 ) 2 η n ( x ) 2 α n 2 . (124) \text{(ii)}\quad\left\|\sin\Theta\left(\widehat{W}P_{V^\star}\widehat{W}^{\mathsf{T}},\Pi^\star\right)\right\|_F^2\le\frac{32\kappa(\kappa-1)^2\eta_n(x)^2}{\alpha_n^2}. \tag*{(124)} (ii) sin Θ ( W P V ⋆ W T , Π ⋆ ) F 2 ≤ α n 2 32 κ ( κ − 1 ) 2 η n ( x ) 2 . (124)
Proof. The same substitutions into (87) –(95) allow Corollary 3 to be applied with ε W = ε s = 0 \varepsilon_W=\varepsilon_s=0 ε W = ε s = 0 . Substitution of (122) into (97) and (98) yields (123) and (124) , respectively.
If the deterministic inequalities in (120) hold, then (44) and Theorem 3 together with Corollaries 4–7 imply that (113) , (120) , (121) , (123) , and (124) hold simultaneously with probability at least 1 − 2 e − x 1-2e^{-x} 1 − 2 e − x .
Theorem 1 follows from Theorem 3, Theorem 2, and Corollary 3.
Proof of Theorem 1. By Lemma 1, P ( G x ) ≥ 1 − 2 e − x \mathbb{P}(\mathcal{G}_x)\ge1-2e^{-x} P ( G x ) ≥ 1 − 2 e − x . On G x \mathcal{G}_x G x , Theorem 3 and (120) give at least one local maximizer of J ˉ n \bar{J}_n J ˉ n satisfying
d O ( W ^ , W ⋆ ) < r , ∥ s ^ − u ⋆ ∥ 2 < r . (125) d_O(\widehat{W},W^\star)<r,\qquad\|\widehat{s}-u^\star\|_2<r. \tag*{(125)} d O ( W , W ⋆ ) < r , ∥ s − u ⋆ ∥ 2 < r . (125)
Since J = n J ˉ n J=n\bar{J}_n J = n J ˉ n with n > 0 n>0 n > 0 , the local maximizers of J J J and J ˉ n \bar{J}_n J ˉ n coincide.
Now let ( W ^ , s ^ ) (\widehat{W},\widehat{s}) ( W , s ) be any local maximizer satisfying (125) . Varying W W W along smooth curves in O ( p ) O(p) O ( p ) and s s s along the feasible segments s ^ + t ( v − s ^ ) \widehat{s}+t(v-\widehat{s}) s + t ( v − s ) yields
grad W J ˉ n ( W ^ , s ^ ) = 0 , ⟨ ∇ s J ˉ n ( W ^ , s ^ ) , v − s ^ ⟩ ≤ 0 , v ∈ S κ . (126) \operatorname{grad}_W\bar{J}_n(\widehat{W},\widehat{s})=0,\qquad
\left\langle\nabla_s\bar{J}_n(\widehat{W},\widehat{s}),v-\widehat{s}\right\rangle\le0,\quad v\in\mathcal{S}_\kappa. \tag*{(126)} grad W J ˉ n ( W , s ) = 0 , ⟨ ∇ s J ˉ n ( W , s ) , v − s ⟩ ≤ 0 , v ∈ S κ . (126)
Consequently, both residuals in (86) are zero. Since r < r 0 r<r_0 r < r 0 , (125) implies (87) . Thus Theorem 2, with ε W = ε s = 0 \varepsilon_W=\varepsilon_s=0 ε W = ε s = 0 , yields s ^ = u ⋆ \widehat{s}=u^\star s = u ⋆ and V ^ = Top κ ( s ^ ) = V ⋆ \widehat{V}=\operatorname{Top}_\kappa(\widehat{s})=V^\star V = Top κ ( s ) = V ⋆ . Corollary 3 and (122) give the projector bound in (4) . All these conclusions hold on the event G x \mathcal{G}_x G x , which proves the theorem.
Sufficient conditions
We verify the assumptions for a specified shared-signal family of the observed matrices. For the fixed V ⋆ V^\star V ⋆ introduced above, suppose
2 ≤ ∣ V ⋆ ∣ = κ < p . (127) 2 \leq\lvert V^\star\rvert= \kappa< p. \tag*{(127)} 2 ≤ ∣ V ⋆ ∣ = κ < p . (127)
For ℓ = 1 , … , L \ell= 1,\ldots,L ℓ = 1 , … , L , let the fixed matrices C ( ℓ ) ∈ R p × p C^{(\ell)} \in\mathbb{R}^{p\times p} C ( ℓ ) ∈ R p × p satisfy
C ( ℓ ) = C ( ℓ ) T , diag ( C ( ℓ ) ) = 0 , C ( ℓ ) = P V ⋆ C ( ℓ ) P V ⋆ . (128) C^{(\ell)} = C^{(\ell)\mathsf{T}}, \qquad\operatorname{diag}\left(C^{(\ell)}\right)=0, \qquad C^{(\ell)} = P_{V^\star}C^{(\ell)}P_{V^\star}. \tag*{(128)} C ( ℓ ) = C ( ℓ ) T , diag ( C ( ℓ ) ) = 0 , C ( ℓ ) = P V ⋆ C ( ℓ ) P V ⋆ . (128)
Suppose that
C i = ∑ ℓ = 1 L z i ℓ C ( ℓ ) , z i = ( z i 1 , … , z i L ) T , Σ z = E ( z i z i T ) ≻ 0 , (129) C_i = \sum_{\ell=1}^{L} z_{i\ell}C^{(\ell)}, \qquad z_i=(z_{i1},\ldots,z_{iL})^{\mathsf{T}}, \qquad\Sigma_z=\mathbb{E}(z_i z_i^{\mathsf{T}})\succ0, \tag*{(129)} C i = ℓ = 1 ∑ L z i ℓ C ( ℓ ) , z i = ( z i 1 , … , z i L ) T , Σ z = E ( z i z i T ) ≻ 0 , (129)
where Σ z \Sigma_z Σ z is a finite second-moment matrix, and that, for a fixed W ⋆ ∈ O ( p ) W^\star\in O(p) W ⋆ ∈ O ( p ) and σ A , σ B ≥ 0 \sigma_A,\sigma_B\geq0 σ A , σ B ≥ 0 ,
A i = W ⋆ C i W ⋆ T + σ A E i A , B i = C i + σ B E i B . (130) A_i=W^\star C_i W^{\star\mathsf{T}}+\sigma_A E_i^A, \qquad B_i=C_i+\sigma_B E_i^B. \tag*{(130)} A i = W ⋆ C i W ⋆ T + σ A E i A , B i = C i + σ B E i B . (130)
The noise matrices satisfy
E ( E i A ) = E ( E i B ) = 0 p × p , E i A = E i A T , E i B = E i B T , diag ( E i B ) = 0 almost surely . (131) \mathbb{E}(E_i^A)=\mathbb{E}(E_i^B)=0_{p\times p}, \qquad E_i^A=E_i^{A\mathsf{T}}, \qquad E_i^B=E_i^{B\mathsf{T}}, \qquad\operatorname{diag}(E_i^B)=0\quad\text{almost surely}. \tag*{(131)} E ( E i A ) = E ( E i B ) = 0 p × p , E i A = E i A T , E i B = E i B T , diag ( E i B ) = 0 almost surely . (131)
Assume that, for every a , b a,b a , b ,
E ( C i , a b E i A ) = 0 p × p , \mathbb{E}(C_{i,ab}E_i^A)=0_{p\times p}, E ( C i , ab E i A ) = 0 p × p ,
E ( E i , a b B W ⋆ C i W ⋆ T ) = 0 p × p , \mathbb{E}(E_{i,ab}^B W^\star C_i W^{\star\mathsf{T}})=0_{p\times p}, E ( E i , ab B W ⋆ C i W ⋆ T ) = 0 p × p ,
E ( E i , a b B E i A ) = 0 p × p . (132) \mathbb{E}(E_{i,ab}^B E_i^A)=0_{p\times p}. \tag*{(132)} E ( E i , ab B E i A ) = 0 p × p . (132)
and that
⋂ ℓ = 1 L ker ( C ( ℓ ) ) = span { e j : j ∉ V ⋆ } = ker ( P V ⋆ ) . (133) \bigcap_{\ell=1}^{L}\ker\left(C^{(\ell)}\right)=\operatorname{span}\{e_j:j\notin V^\star\}=\ker(P_{V^\star}). \tag*{(133)} ℓ = 1 ⋂ L ker ( C ( ℓ ) ) = span { e j : j ∈ / V ⋆ } = ker ( P V ⋆ ) . (133)
Suppose further that
{ ( z i , E i A , E i B ) } i = 1 n are independent and identically distributed , (134) \left\{\left(z_i,E_i^A,E_i^B\right)\right\}_{i=1}^{n}\ \text{are independent and identically distributed}, \tag*{(134)} { ( z i , E i A , E i B ) } i = 1 n are independent and identically distributed , (134)
and that finite, possibly dimension-dependent constants K A , K B K_A,K_B K A , K B satisfy
max a , b ∥ B i , a b ∥ ψ 2 ≤ K B , sup ∥ x ∥ 2 = ∥ y ∥ 2 = 1 ∥ x T A i y ∥ ψ 2 ≤ K A . (135) \max_{a,b}\lVert B_{i,ab}\rVert_{\psi_2}\leq K_B,\qquad
\sup_{\lVert x\rVert_2=\lVert y\rVert_2=1}\lVert x^{\mathsf{T}}A_i y\rVert_{\psi_2}\leq K_A. \tag*{(135)} a , b max ∥ B i , ab ∥ ψ 2 ≤ K B , ∥ x ∥ 2 = ∥ y ∥ 2 = 1 sup ∥ x T A i y ∥ ψ 2 ≤ K A . (135)
For this model, the quantities in Assumption A3 are given by
W ⋆ = { W ⋆ Q : Q ∈ O ( p ) , Q T C ( ℓ ) Q = C ( ℓ ) for ℓ = 1 , … , L } , \mathcal{W}^\star=\left\{W^\star Q:Q\in O(p),\ Q^{\mathsf{T}}C^{(\ell)}Q=C^{(\ell)}\text{ for }\ell=1,\ldots,L\right\}, W ⋆ = { W ⋆ Q : Q ∈ O ( p ) , Q T C ( ℓ ) Q = C ( ℓ ) for ℓ = 1 , … , L } ,
Π ⋆ = W ⋆ P V ⋆ W ⋆ T , J ⋆ = E ∥ C i ∥ F 2 . (136) \Pi^\star=W^\star P_{V^\star}W^{\star\mathsf{T}},\qquad J^\star=\mathbb{E}\lVert C_i\rVert_F^2. \tag*{(136)} Π ⋆ = W ⋆ P V ⋆ W ⋆ T , J ⋆ = E ∥ C i ∥ F 2 . (136)
Set
m n = 2 min a ∈ V ⋆ ∑ b ∈ V ⋆ ∖ { a } E ( C i , a b 2 ) . (137) m_n=2\min_{a\in V^\star}\sum_{b\in V^\star\setminus\{a\}}\mathbb{E}(C_{i,ab}^2). \tag*{(137)} m n = 2 a ∈ V ⋆ min b ∈ V ⋆ ∖ { a } ∑ E ( C i , ab 2 ) . (137)
Proposition 1 verifies Assumptions A1–A5 for the model in (138).
Proposition 1. Under (135)–(143), Assumptions A1–A5 hold with (144), the strictly positive margin in (145), ν n = C K A K B \nu_n=CK_AK_B ν n = C K A K B for a universal constant C > 0 C>0 C > 0 , and the strictly positive curvature constant α n = α C \alpha_n=\alpha_C α n = α C defined in (161) below.
Proof. Every W ∈ O ( p ) W\in O(p) W ∈ O ( p ) has the unique representation W = W ⋆ Q W=W^\star Q W = W ⋆ Q , where Q = W ⋆ T W ∈ O ( p ) Q=W^{\star\mathsf{T}}W\in O(p) Q = W ⋆ T W ∈ O ( p ) . Expanding the population criterion yields
J ( W ⋆ Q , u ⋆ ) = E Tr ( Q T C i Q C i ) . (138) \mathcal{J}(W^\star Q,u^\star)=\mathbb{E}\operatorname{Tr}\left(Q^{\mathsf{T}}C_iQ C_i\right). \tag*{(138)} J ( W ⋆ Q , u ⋆ ) = E Tr ( Q T C i Q C i ) . (138)
Indeed, for every a , b ∈ V ⋆ a,b\in V^\star a , b ∈ V ⋆ , the three remaining terms in the entrywise expansion have coefficients σ A \sigma_A σ A , σ B \sigma_B σ B , and σ A σ B \sigma_A\sigma_B σ A σ B , respectively, and their unscaled expectations vanish by (132) :
E [ C i , a b e a ⊤ Q ⊤ W ⋆ ⊤ E i A W ⋆ Q e b ] = e a ⊤ Q ⊤ W ⋆ ⊤ E ( C i , a b E i A ) W ⋆ Q e b = 0. (139) \mathbb{E}\left[C_{i,ab}e_a^\top Q^\top W^\star{}^\top E_i^A W^\star Qe_b\right]=e_a^\top Q^\top W^\star{}^\top\mathbb{E}\left(C_{i,ab}E_i^A\right)W^\star Qe_b=0. \tag*{(139)} E [ C i , ab e a ⊤ Q ⊤ W ⋆ ⊤ E i A W ⋆ Q e b ] = e a ⊤ Q ⊤ W ⋆ ⊤ E ( C i , ab E i A ) W ⋆ Q e b = 0. (139)
E [ E i , a b B e a ⊤ Q ⊤ C i Q e b ] = e a ⊤ Q ⊤ W ⋆ ⊤ E ( E i , a b B W ⋆ C i W ⋆ ⊤ ) W ⋆ Q e b = 0 , E [ E i , a b B e a ⊤ Q ⊤ W ⋆ ⊤ E i A W ⋆ Q e b ] = e a ⊤ Q ⊤ W ⋆ ⊤ E ( E i , a b B E i A ) W ⋆ Q e b = 0. (140) \begin{aligned}
\mathbb{E}\left[E_{i,ab}^B e_a^\top Q^\top C_iQe_b\right]&=e_a^\top Q^\top W^\star{}^\top\mathbb{E}\left(E_{i,ab}^B W^\star C_iW^\star{}^\top\right)W^\star Qe_b=0,\\
\mathbb{E}\left[E_{i,ab}^B e_a^\top Q^\top W^\star{}^\top E_i^A W^\star Qe_b\right]&=e_a^\top Q^\top W^\star{}^\top\mathbb{E}\left(E_{i,ab}^B E_i^A\right)W^\star Qe_b=0. \tag*{(140)}
\end{aligned} E [ E i , ab B e a ⊤ Q ⊤ C i Q e b ] E [ E i , ab B e a ⊤ Q ⊤ W ⋆ ⊤ E i A W ⋆ Q e b ] = e a ⊤ Q ⊤ W ⋆ ⊤ E ( E i , ab B W ⋆ C i W ⋆ ⊤ ) W ⋆ Q e b = 0 , = e a ⊤ Q ⊤ W ⋆ ⊤ E ( E i , ab B E i A ) W ⋆ Q e b = 0. (140)
Symmetry identifies the remaining sum with the trace in (138) . Orthogonal invariance of the Frobenius norm therefore yields
J ⋆ − J ( W ⋆ Q , u ⋆ ) = 1 2 E ∥ Q ⊤ C i Q − C i ∥ F 2 . (141) J^\star-J(W^\star Q,u^\star)=\frac{1}{2}\mathbb{E}\left\|Q^\top C_iQ-C_i\right\|_F^2. \tag*{(141)} J ⋆ − J ( W ⋆ Q , u ⋆ ) = 2 1 E Q ⊤ C i Q − C i F 2 . (141)
Moreover, expansion in the fixed matrices C ( ℓ ) C^{(\ell)} C ( ℓ ) gives the second-moment identity
E ∥ Q ⊤ C i Q − C i ∥ F 2 = ∑ ℓ , m = 1 L ( Σ z ) ℓ m ⟨ Q ⊤ C ( ℓ ) Q − C ( ℓ ) , Q ⊤ C ( m ) Q − C ( m ) ⟩ ≥ λ min ( Σ z ) ∑ ℓ = 1 L ∥ Q ⊤ C ( ℓ ) Q − C ( ℓ ) ∥ F 2 . (142) \begin{aligned}
\mathbb{E}\left\|Q^\top C_iQ-C_i\right\|_F^2
&=\sum_{\ell,m=1}^{L}(\Sigma_z)_{\ell m}\left\langle Q^\top C^{(\ell)}Q-C^{(\ell)},Q^\top C^{(m)}Q-C^{(m)}\right\rangle\\
&\geq\lambda_{\min}(\Sigma_z)\sum_{\ell=1}^{L}\left\|Q^\top C^{(\ell)}Q-C^{(\ell)}\right\|_F^2. \tag*{(142)}
\end{aligned} E Q ⊤ C i Q − C i F 2 = ℓ , m = 1 ∑ L ( Σ z ) ℓ m ⟨ Q ⊤ C ( ℓ ) Q − C ( ℓ ) , Q ⊤ C ( m ) Q − C ( m ) ⟩ ≥ λ m i n ( Σ z ) ℓ = 1 ∑ L Q ⊤ C ( ℓ ) Q − C ( ℓ ) F 2 . (142)
The inequality follows by applying the smallest-eigenvalue bound for Σ z \Sigma_z Σ z to the L L L coefficients at each matrix entry and summing over the entries. Since Σ z ≻ 0 \Sigma_z\succ0 Σ z ≻ 0 , the expression in (142) is zero exactly when every C ( ℓ ) C^{(\ell)} C ( ℓ ) is preserved by Q Q Q . Thus (136) gives the full population maximizer set at u ⋆ u^\star u ⋆ .
Define
H C = { Q ∈ O ( p ) : Q ⊤ C ( ℓ ) Q = C ( ℓ ) for ℓ = 1 , … , L } . (143) \mathcal{H}_C=\left\{Q\in O(p):Q^\top C^{(\ell)}Q=C^{(\ell)}\text{ for }\ell=1,\ldots,L\right\}. \tag*{(143)} H C = { Q ∈ O ( p ) : Q ⊤ C ( ℓ ) Q = C ( ℓ ) for ℓ = 1 , … , L } . (143)
This is a closed subgroup of the compact group O ( p ) O(p) O ( p ) . Cartan’s closed subgroup theorem implies that it is an embedded Lie subgroup [25 Theorem 20.12] . Consequently, W ⋆ = W ⋆ H C \mathcal{W}^\star=\mathcal{W}^\star\mathcal{H}_C W ⋆ = W ⋆ H C is a nonempty compact smooth embedded submanifold of O ( p ) O(p) O ( p ) . Each of its points maximizes J ( ⋅ , u ⋆ ) J(\cdot,u^\star) J ( ⋅ , u ⋆ ) by (141) ; hence its Riemannian gradient is zero.
For Q ∈ H C Q\in\mathcal{H}_C Q ∈ H C , the defining equalities are equivalent to
C ( ℓ ) Q = Q C ( ℓ ) , ℓ = 1 , … , L . (144) C^{(\ell)}Q=QC^{(\ell)},\qquad\ell=1,\ldots,L. \tag*{(144)} C ( ℓ ) Q = Q C ( ℓ ) , ℓ = 1 , … , L . (144)
It follows that Q Q Q preserves the common kernel in (133) . Orthogonality then implies preservation of its orthogonal complement, range ( P V ⋆ ) \operatorname{range}(P_{V^\star}) range ( P V ⋆ ) , and therefore
Q P V ⋆ Q ⊤ = P V ⋆ , ( W ⋆ Q ) P V ⋆ ( W ⋆ Q ) ⊤ = Π ⋆ . (145) QP_{V^\star}Q^\top=P_{V^\star},\qquad(W^\star Q)P_{V^\star}(W^\star Q)^\top=\Pi^\star. \tag*{(145)} Q P V ⋆ Q ⊤ = P V ⋆ , ( W ⋆ Q ) P V ⋆ ( W ⋆ Q ) ⊤ = Π ⋆ . (145)
If R ∈ O ( p ) R\in O(p) R ∈ O ( p ) satisfies R P V ⋆ = P V ⋆ RP_{V^\star}=P_{V^\star} R P V ⋆ = P V ⋆ , orthogonality gives
R ⊤ P V ⋆ = P V ⋆ R = P V ⋆ . (146) R^\top P_{V^\star}=P_{V^\star}R=P_{V^\star}. \tag*{(146)} R ⊤ P V ⋆ = P V ⋆ R = P V ⋆ . (146)
The support condition in (128) now implies
R ⊤ C ( ℓ ) R = R ⊤ P V ⋆ C ( ℓ ) P V ⋆ R = C ( ℓ ) . (147) R^\top C^{(\ell)}R=R^\top P_{V^\star}C^{(\ell)}P_{V^\star}R=C^{(\ell)}. \tag*{(147)} R ⊤ C ( ℓ ) R = R ⊤ P V ⋆ C ( ℓ ) P V ⋆ R = C ( ℓ ) . (147)
Thus R ∈ H C R\in\mathcal{H}_C R ∈ H C , and the group property gives U R ∈ W ⋆ UR\in\mathcal{W}^\star U R ∈ W ⋆ whenever U ∈ W ⋆ U\in\mathcal{W}^\star U ∈ W ⋆ . These identities verify every part of Assumption A3.
The Lie algebra of H C \mathcal{H}_C H C is
h C = { Ω ∈ R p × p : Ω ⊤ = − Ω , C ( ℓ ) Ω = Ω C ( ℓ ) for ℓ = 1 , … , L } . (148) \mathfrak{h}_C=\left\{\Omega\in\mathbb{R}^{p\times p}:\Omega^\top=-\Omega,\ C^{(\ell)}\Omega=\Omega C^{(\ell)}\text{ for }\ell=1,\ldots,L\right\}. \tag*{(148)} h C = { Ω ∈ R p × p : Ω ⊤ = − Ω , C ( ℓ ) Ω = Ω C ( ℓ ) for ℓ = 1 , … , L } . (148)
Indeed, differentiating the defining equalities of H C \mathcal{H}_C H C at the identity gives the displayed commutation relations; conversely, these relations imply that exp ( t Ω ) \exp(t\Omega) exp ( t Ω ) commutes with every C ( ℓ ) C^{(\ell)} C ( ℓ ) for all t t t . For a skew-symmetric Ω \Omega Ω , differentiating (141) along Q ( t ) = exp ( t Ω ) Q(t)=\exp(t\Omega) Q ( t ) = exp ( t Ω ) yields
− d 2 d t 2 J ( W ⋆ exp ( t Ω ) , u ⋆ ) ∣ t = 0 = E ∥ C i Ω − Ω C i ∥ F 2 . (149) -\left.\frac{d^2}{dt^2}J(W^\star\exp(t\Omega),u^\star)\right|_{t=0}=\mathbb{E}\left\|C_i\Omega-\Omega C_i\right\|_F^2. \tag*{(149)} − d t 2 d 2 J ( W ⋆ exp ( t Ω ) , u ⋆ ) t = 0 = E ∥ C i Ω − Ω C i ∥ F 2 . (149)
To see the coefficient explicitly, the matrix F i ( t ) = exp ( − t Ω ) C i exp ( t Ω ) − C i F_i(t)=\exp(-t\Omega)C_i\exp(t\Omega)-C_i F i ( t ) = exp ( − t Ω ) C i exp ( t Ω ) − C i satisfies F i ( 0 ) = 0 F_i(0)=0 F i ( 0 ) = 0 and F i ′ ( 0 ) = C i Ω − Ω C i F_i'(0)=C_i\Omega-\Omega C_i F i ′ ( 0 ) = C i Ω − Ω C i ; hence the second derivative of ∥ F i ( t ) ∥ F 2 / 2 \|F_i(t)\|_F^2/2 ∥ F i ( t ) ∥ F 2 /2 at zero is ∥ F i ′ ( 0 ) ∥ F 2 \|F_i'(0)\|_F^2 ∥ F i ′ ( 0 ) ∥ F 2 . The finite second moment in (129) justifies differentiation after expectation, or equivalently differentiation of the finite second-moment expansion.
The same expansion as in (142) gives
E ∥ C i Ω − Ω C i ∥ F 2 = ∑ ℓ , m = 1 L ( Σ z ) ℓ m ⟨ C ( ℓ ) Ω − Ω C ( ℓ ) , C ( m ) Ω − Ω C ( m ) ⟩ ≥ λ min ( Σ z ) ∑ ℓ = 1 L ∥ C ( ℓ ) Ω − Ω C ( ℓ ) ∥ F 2 . (150) \begin{aligned}
\mathbb{E}\lVert C_i\Omega-\Omega C_i\rVert_F^2
=\sum_{\ell,m=1}^{L}(\Sigma_z)_{\ell m}\left\langle C^{(\ell)}\Omega-\Omega C^{(\ell)},C^{(m)}\Omega-\Omega C^{(m)}\right\rangle\\
&\geq\lambda_{\min}(\Sigma_z)\sum_{\ell=1}^{L}\lVert C^{(\ell)}\Omega-\Omega C^{(\ell)}\rVert_F^2. \tag*{(150)}
\end{aligned} E ∥ C i Ω − Ω C i ∥ F 2 = ℓ , m = 1 ∑ L ( Σ z ) ℓ m ⟨ C ( ℓ ) Ω − Ω C ( ℓ ) , C ( m ) Ω − Ω C ( m ) ⟩ ≥ λ m i n ( Σ z ) ℓ = 1 ∑ L ∥ C ( ℓ ) Ω − Ω C ( ℓ ) ∥ F 2 . (150)
Consequently,
E ∥ C i Ω − Ω C i ∥ F 2 = 0 ⟺ Ω ∈ h C . (151) \mathbb{E}\lVert C_i\Omega-\Omega C_i\rVert_F^2=0\quad\Longleftrightarrow\quad\Omega\in\mathfrak{h}_C. \tag*{(151)} E ∥ C i Ω − Ω C i ∥ F 2 = 0 ⟺ Ω ∈ h C . (151)
The orthogonal complement of h C \mathfrak{h}_C h C within the skew-symmetric matrices has positive dimension. To verify this, choose unit vectors v ∈ range ( P V ⋆ ) v\in\operatorname{range}(P_{V^\star}) v ∈ range ( P V ⋆ ) and w ∈ ker ( P V ⋆ ) w\in\operatorname{ker}(P_{V^\star}) w ∈ ker ( P V ⋆ ) . By (133) , there is an ℓ \ell ℓ such that C ( ℓ ) v ≠ 0 C^{(\ell)}v\ne0 C ( ℓ ) v = 0 . The skew-symmetric matrix Ω v , w = v w T − w v T \Omega_{v,w}=vw^{\mathsf{T}}-wv^{\mathsf{T}} Ω v , w = v w T − w v T satisfies
{ C ( ℓ ) Ω v , w − Ω v , w C ( ℓ ) } w = C ( ℓ ) v ≠ 0 , (152) \left\{C^{(\ell)}\Omega_{v,w}-\Omega_{v,w}C^{(\ell)}\right\}w=C^{(\ell)}v\ne0, \tag*{(152)} { C ( ℓ ) Ω v , w − Ω v , w C ( ℓ ) } w = C ( ℓ ) v = 0 , (152)
so h C \mathfrak{h}_C h C is a proper subspace. Define
α C = min Ω T = − Ω , Ω ⊥ h C ∥ Ω ∥ F = 1 E ∥ C i Ω − Ω C i ∥ F 2 . (153) \alpha_C=\min_{\substack{\Omega^{\mathsf{T}}=-\Omega,\ \Omega\perp\mathfrak{h}_C\\\lVert\Omega\rVert_F=1}}\mathbb{E}\lVert C_i\Omega-\Omega C_i\rVert_F^2. \tag*{(153)} α C = Ω T = − Ω , Ω ⊥ h C ∥ Ω ∥ F = 1 min E ∥ C i Ω − Ω C i ∥ F 2 . (153)
The constraint set is nonempty and compact, and the objective is continuous and strictly positive there by (151) . Hence α C > 0 \alpha_C>0 α C > 0 .
For Q 0 ∈ H C Q_0\in\mathcal{H}_C Q 0 ∈ H C and U = W ⋆ Q 0 U=W^\star Q_0 U = W ⋆ Q 0 , left multiplication by U U U is an isometry for the Frobenius metric, and
T U W ⋆ = { U Ω : Ω ∈ h C } , T_U\mathcal{W}^\star=\{U\Omega:\Omega\in\mathfrak{h}_C\}, T U W ⋆ = { U Ω : Ω ∈ h C } ,
{ ξ ∈ T U O ( p ) : ξ ⊥ T U W ⋆ } = { U Ω : Ω T = − Ω , Ω ⊥ h C } . (154) \{\xi\in T_U\mathcal{O}(p):\xi\perp T_U\mathcal{W}^\star\}=\{U\Omega:\Omega^{\mathsf{T}}=-\Omega,\ \Omega\perp\mathfrak{h}_C\}. \tag*{(154)} { ξ ∈ T U O ( p ) : ξ ⊥ T U W ⋆ } = { U Ω : Ω T = − Ω , Ω ⊥ h C } . (154)
For such ξ = U Ω \xi=U\Omega ξ = U Ω , the curve t ↦ U exp ( t Ω ) t\mapsto U\exp(t\Omega) t ↦ U exp ( t Ω ) is the geodesic with initial velocity ξ \xi ξ [13 Section 2.2.2, Eq. (2.14)] . Since Q 0 Q_0 Q 0 preserves every C i C_i C i , one has
J ( W ⋆ Q 0 exp ( t Ω ) , u ⋆ ) = J ( W ⋆ exp ( t Ω ) , u ⋆ ) . (155) \mathcal{J}(W^\star Q_0\exp(t\Omega),u^\star)=\mathcal{J}(W^\star\exp(t\Omega),u^\star). \tag*{(155)} J ( W ⋆ Q 0 exp ( t Ω ) , u ⋆ ) = J ( W ⋆ exp ( t Ω ) , u ⋆ ) . (155)
The geodesic second-derivative identity [2 Proposition 5.5.4] , (149) , and (153) therefore imply
− ⟨ ξ , Hess W W J ( U , u ⋆ ) [ ξ ] ⟩ ≥ α C ∥ Ω ∥ F 2 = α C ∥ ξ ∥ F 2 . (156) -\left\langle\xi,\operatorname{Hess}_{WW}\mathcal{J}(U,u^\star)[\xi]\right\rangle\geq\alpha_C\lVert\Omega\rVert_F^2=\alpha_C\lVert\xi\rVert_F^2. \tag*{(156)} − ⟨ ξ , Hess W W J ( U , u ⋆ ) [ ξ ] ⟩ ≥ α C ∥ Ω ∥ F 2 = α C ∥ ξ ∥ F 2 . (156)
This proves Assumption A4 with α n = α C \alpha_n=\alpha_C α n = α C .
For U = W ⋆ Q ∈ W ⋆ U=W^\star Q\in\mathcal{W}^\star U = W ⋆ Q ∈ W ⋆ , expansion of (11) , followed by (144) and (132) , yields
{ D 0 ( U ) } a b = { E ( C i , a b 2 ) , a , b ∈ V ⋆ , 0 , { a , b } ⊈ V ⋆ . (157) \{D_0(U)\}_{ab}=
\begin{cases}
\mathbb{E}(C_{i,ab}^2), & a,b\in V^\star,\\
0, & \{a,b\}\not\subseteq V^\star.
\end{cases} \tag*{(157)} { D 0 ( U ) } ab = { E ( C i , ab 2 ) , 0 , a , b ∈ V ⋆ , { a , b } ⊆ V ⋆ . (157)
As diag ( C i ) = 0 \operatorname{diag}(C_i)=0 diag ( C i ) = 0 , this implies
{ 2 D 0 ( U ) u ⋆ } a = { 2 ∑ b ∈ V ⋆ ∖ { a } E ( C i , a b 2 ) , a ∈ V ⋆ , 0 , a ∉ V ⋆ . (158) \{2D_0(U)u^\star\}_a=
\begin{cases}
2\sum_{b\in V^\star\setminus\{a\}}\mathbb{E}(C_{i,ab}^2), & a\in V^\star,\\
0, & a\notin V^\star.
\end{cases} \tag*{(158)} { 2 D 0 ( U ) u ⋆ } a = { 2 ∑ b ∈ V ⋆ ∖ { a } E ( C i , ab 2 ) , 0 , a ∈ V ⋆ , a ∈ / V ⋆ . (158)
The selected sums are positive. Indeed, if such a sum were zero for some a ∈ V ⋆ a\in V^\star a ∈ V ⋆ , then E ( C i , a b 2 ) = 0 \mathbb{E}(C_{i,ab}^2)=0 E ( C i , ab 2 ) = 0 for every b b b . By (129) and Σ z ≻ 0 \Sigma_z\succ0 Σ z ≻ 0 , this would give C a b ( ℓ ) = 0 C_{ab}^{(\ell)}=0 C ab ( ℓ ) = 0 for all b , ℓ b,\ell b , ℓ . Its symmetry would then imply C e a ( ℓ ) = 0 C_{ea}^{(\ell)}=0 C e a ( ℓ ) = 0 for every ℓ \ell ℓ , contradicting (133) . Thus (137) is strictly positive, and (158) proves Assumption A5.
The structural conditions and (134) give Assumption A1. For unit vectors x , y x,y x , y , Lemma 2.7.7 of [43 ] implies
∥ B i , a b x T A i y ∥ ψ 1 ≤ C ∥ B i , a b ∥ ψ 2 ∥ x T A i y ∥ ψ 2 ≤ C K A K B . (159) \lVert B_{i,ab}x^{\mathsf{T}}A_i y\rVert_{\psi_1}\leq C\lVert B_{i,ab}\rVert_{\psi_2}\lVert x^{\mathsf{T}}A_i y\rVert_{\psi_2}\leq CK_AK_B. \tag*{(159)} ∥ B i , ab x T A i y ∥ ψ 1 ≤ C ∥ B i , ab ∥ ψ 2 ∥ x T A i y ∥ ψ 2 ≤ C K A K B . (159)
This proves Assumption A2 and completes the verification.
For a concrete instance, take L = 1 L=1 L = 1 , C i = z i C C_i=z_iC C i = z i C , and
C a b = { c , a , b ∈ V ⋆ , a ≠ b , 0 , otherwise , c ≠ 0. (160) C_{ab}=
\begin{cases}
c, & a,b\in V^\star,\ a\ne b,\\
0, & \text{otherwise},
\end{cases}
\qquad c\ne0. \tag*{(160)} C ab = { c , 0 , a , b ∈ V ⋆ , a = b , otherwise , c = 0. (160)
Let z i ∼ N ( 0 , 1 ) z_i\sim N(0,1) z i ∼ N ( 0 , 1 ) , and let G i A , G i B ∈ R p × p G_i^A,G_i^B\in\mathbb{R}^{p\times p} G i A , G i B ∈ R p × p have independent N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) entries, with all these variables and matrices mutually independent across modalities and subjects. Set
E i A = 1 2 ( G i A + G i A T ) , E i , a b B = { 1 2 ( G i , a b B + G i , b a B ) , a ≠ b , 0 , a = b . (161) E_i^A=\frac{1}{2}\left(G_i^A+G_i^{A\mathsf{T}}\right),\qquad
E_{i,ab}^B=
\begin{cases}
\frac{1}{2}\left(G_{i,ab}^B+G_{i,ba}^B\right), & a\ne b,\\
0, & a=b.
\end{cases} \tag*{(161)} E i A = 2 1 ( G i A + G i A T ) , E i , ab B = { 2 1 ( G i , ab B + G i , ba B ) , 0 , a = b , a = b . (161)
Define A i , B i A_i,B_i A i , B i by (130) for any fixed W ⋆ ∈ O ( p ) W^\star\in O(p) W ⋆ ∈ O ( p ) . Symmetry, centering, and independence verify (131) , (132) , and (134) .
Note that three distinct eigenvalues of C C C are c ( κ − 1 ) c(\kappa-1) c ( κ − 1 ) , − c -c − c , 0 0 0 , with multiplicities 1 1 1 , κ − 1 \kappa-1 κ − 1 , and p − κ p-\kappa p − κ , respectively. Thus its kernel is exactly ker ( P V ⋆ ) \ker(P_{V^\star}) ker ( P V ⋆ ) . Let λ 1 , … , λ p \lambda_1,\ldots,\lambda_p λ 1 , … , λ p denote these eigenvalues in an orthonormal eigenbasis. In this basis, the identity ( C Ω − Ω C ) a b = ( λ a − λ b ) Ω a b (C\Omega-\Omega C)_{ab}=(\lambda_a-\lambda_b)\Omega_{ab} ( C Ω − Ω C ) ab = ( λ a − λ b ) Ω ab shows that h C \mathfrak{h}_C h C consists of the skew-symmetric blocks within the eigenspaces and that its orthogonal complement consists of the blocks between distinct eigenspaces. The smallest absolute difference between distinct eigenvalues within the spectrum is ∣ c ∣ \lvert c\rvert ∣ c ∣ . Hence
∥ C Ω − Ω C ∥ F 2 ≥ c 2 ∥ Ω ∥ F 2 , Ω T = − Ω , Ω ⊥ h C . (162) \left\|C\Omega-\Omega C\right\|_F^2\ge c^2\left\|\Omega\right\|_F^2,\qquad
\Omega^{\mathsf{T}}=-\Omega,\quad\Omega\perp\mathfrak{h}_C. \tag*{(162)} ∥ C Ω − Ω C ∥ F 2 ≥ c 2 ∥ Ω ∥ F 2 , Ω T = − Ω , Ω ⊥ h C . (162)
Since E ( z i 2 ) = 1 \mathbb{E}(z_i^2)=1 E ( z i 2 ) = 1 , the constants are therefore α n = c 2 \alpha_n=c^2 α n = c 2 , m n = 2 ( κ − 1 ) c 2 m_n=2(\kappa-1)c^2 m n = 2 ( κ − 1 ) c 2 , and J ⋆ = κ ( κ − 1 ) c 2 J^\star=\kappa(\kappa-1)c^2 J ⋆ = κ ( κ − 1 ) c 2 . For every pair of unit vectors x , y x,y x , y , independence and the symmetrized Gaussian construction yield
Var ( x T A i y ) = ( x T W ⋆ C W ⋆ T y ) 2 + σ A 2 2 { 1 + ( x T y ) 2 } ≤ c 2 ( κ − 1 ) 2 + σ A 2 , (163) \operatorname{Var}(x^{\mathsf{T}}A_i y)=(x^{\mathsf{T}}W^\star C W^{\star\mathsf{T}}y)^2+\frac{\sigma_A^2}{2}\{1+(x^{\mathsf{T}}y)^2\}\le c^2(\kappa-1)^2+\sigma_A^2, \tag*{(163)} Var ( x T A i y ) = ( x T W ⋆ C W ⋆ T y ) 2 + 2 σ A 2 { 1 + ( x T y ) 2 } ≤ c 2 ( κ − 1 ) 2 + σ A 2 , (163)
max a , b Var ( B i , a b ) = c 2 + σ B 2 2 . (164) \max_{a,b}\operatorname{Var}(B_{i,ab})=c^2+\frac{\sigma_B^2}{2}. \tag*{(164)} a , b max Var ( B i , ab ) = c 2 + 2 σ B 2 . (164)
Therefore, for a universal constant C ψ > 0 C_\psi>0 C ψ > 0 determined by the convention for the ψ 2 \psi_2 ψ 2 norm, (135) holds with K A = C ψ c 2 ( κ − 1 ) 2 + σ A 2 K_A=C_\psi\sqrt{c^2(\kappa-1)^2+\sigma_A^2} K A = C ψ c 2 ( κ − 1 ) 2 + σ A 2 , and K B = C ψ c 2 + σ B 2 / 2 K_B=C_\psi\sqrt{c^2+\sigma_B^2/2} K B = C ψ c 2 + σ B 2 /2 . The population coefficient bound (50) holds with E ( B i , a b A i ) = C a b W ⋆ C W ⋆ T \mathbb{E}(B_{i,ab}A_i)=C_{ab}W^\star C W^{\star\mathsf{T}} E ( B i , ab A i ) = C ab W ⋆ C W ⋆ T , and M 0 = c 2 ( κ − 1 ) M_0=c^2(\kappa-1) M 0 = c 2 ( κ − 1 ) .
Full Ossa algorithm pseudocode
Algorithm 1 gives the canonical OSSA single-support OSSA solver. Algorithm 2 gives the overlap-regularized K K K -support extension.
When K = 1 K=1 K = 1 and λ = 0 \lambda=0 λ = 0 , the inner ℓ \ell ℓ -loop collapses to a single s s s -update, the aggregate M i M_i M i reduces to S B i S SB_iS S B i S , and the algorithm reduces exactly to Algorithm 1. For K ≥ 2 K\ge2 K ≥ 2 , the Gauss-Seidel sweep updates each support against the current W W W and the current values of the other supports, with the overlap penalty entering linearly through − λ ∑ r ≠ ℓ s ( r ) -\lambda\sum_{r\ne\ell}s^{(r)} − λ ∑ r = ℓ s ( r ) . As in the canonical OSSA case, backtracking guarantees a monotone objective sequence, and multiple random restarts are used to mitigate local optima.
Algorithm 2 Overlap-regularized K-clique OSSA
Require: Symmetric matrices $\{A_i, B_i\}_{i=1}^n$ in one community; number of supports $K$; per-support budget $\kappa$; overlap penalty $\lambda \ge 0$; initial steps $\eta_W, \eta_s$; backtracking factor $\beta \in (0,1)$
Ensure: Alignment $W$, relaxed supports $\{s^{(\ell)}\}_{\ell=1}^K$, and hard supports $\{\widehat{V}^{(\ell)}\}_{\ell=1}^K$
1: Initialize $W \leftarrow I_p$ or a random orthogonal matrix; initialize $s^{(\ell)} \in \mathcal{S}_\kappa$ for $\ell=1,\ldots,K$
2: repeat
3: $\mathcal{S}^{(\ell)} \leftarrow \operatorname{diag}(s^{(\ell)})$ for $\ell=1,\ldots,K$
4: $M_i \leftarrow \sum_{\ell=1}^K \mathcal{S}^{(\ell)}B_i\mathcal{S}^{(\ell)}$ for $i=1,\ldots,n$
5: $G_W \leftarrow 2\sum_{i=1}^n A_iWM_i$ and $W^+(\eta) \leftarrow \Pi_{O(p)}(W+\eta G_W)$
6: Choose the largest $\eta \in \{\eta_W\beta^m:m\ge 0\}$ satisfying $J_K(W^+(\eta),\{s^{(\ell)}\}) \ge J_K(W,\{s^{(\ell)}\})$, and set $W \leftarrow W^+(\eta)$
7: $D \leftarrow \operatorname{sym}\{\sum_{i=1}^n(W^\top A_iW)\circ B_i\}$
8: for $\ell=1,\ldots,K$ do ▷ Gauss-Seidel sweep over supports
9: $g^{(\ell)} \leftarrow 2Ds^{(\ell)}-\lambda\sum_{r\ne\ell}s^{(r)}$
10: $s^{(\ell,+)}(\eta) \leftarrow \Pi_{\mathcal{S}_\kappa}(s^{(\ell)}+\eta g^{(\ell)})$
11: Choose the largest $\eta \in \{\eta_s\beta^m:m\ge 0\}$ satisfying $J_K(W,\ldots,s^{(\ell,+)}(\eta),\ldots) \ge J_K(W,\ldots,s^{(\ell)},\ldots)$, and set $s^{(\ell)} \leftarrow s^{(\ell,+)}(\eta)$
12: end for
13: until the objective and iterate changes satisfy the stopping tolerances
14: $\widehat{V}^{(\ell)} \leftarrow \operatorname{Top}_\kappa(s^{(\ell)})$ for $\ell=1,\ldots,K$
15: return $W,\{s^{(\ell)}\}_{\ell=1}^K,\{\widehat{V}^{(\ell)}\}_{\ell=1}^K
Implementation constants. Unless otherwise stated, we use initial step sizes η W = 5 × 10 − 2 \eta_W=5\times10^{-2} η W = 5 × 1 0 − 2 , η s = 5 × 10 − 2 \eta_s=5\times10^{-2} η s = 5 × 1 0 − 2 , backtracking factor β = 0.5 \beta=0.5 β = 0.5 with a floor η min = 10 − 12 \eta_{\min}=10^{-12} η m i n = 1 0 − 12 , relative objective tolerance tol o u t e r = 10 − 5 \operatorname{tol}_{\mathrm{outer}}=10^{-5} tol outer = 1 0 − 5 , per-block objective-improvement threshold tol i n n e r = 10 − 7 \operatorname{tol}_{\mathrm{inner}}=10^{-7} tol inner = 1 0 − 7 , and a maximum of 20 outer block-coordinate iterations (with up to 30 projected-gradient iterations per W W W -block and per support-vector update, each using backtracking line search). Random orthogonal initializations are generated by QR decomposition of an i.i.d. N ( 0 , 1 ) \mathcal{N}(0,1) N ( 0 , 1 ) Gaussian matrix (equivalently, samples from the Haar measure on O ( p ) O(p) O ( p ) ). Support initializations are generated by drawing each entry i.i.d. uniform on [ 0 , 1 ] [0,1] [ 0 , 1 ] and then projecting onto S κ \mathcal{S}_\kappa S κ via the clip-and-soft-threshold simplex projection, we verified that uniform s = ( κ / p ) 1 p s=(\kappa/p)\mathbf{1}_p s = ( κ / p ) 1 p and binary κ \kappa κ -hot random initializations produce indistinguishable selections within restart-to-restart variability. For the ABCD experiments, we use 16 random restarts for canonical OSSA evaluation (Algorithm 1), 4 for per-κ \kappa κ selection, and 4 for multi-clique fits (Algorithm 2). The canonical single-clique simulation sweeps use 8 random restarts; settings for the remaining simulation diagnostics are reported in Appendices D.4–D.7. The restart with the largest training objective is retained. For the ABCD bootstrap stability analysis we use 2 restarts with a lighter ( max o u t e r , max i t e r W , s ) = ( 10 , 15 ) (\max_{\mathrm{outer}},\max_{\mathrm{iter}_{W,s}})=(10,15) ( max outer , max iter W , s ) = ( 10 , 15 ) schedule and tol o u t e r = 10 − 4 \operatorname{tol}_{\mathrm{outer}}=10^{-4} tol outer = 1 0 − 4 , tol i n n e r = 10 − 6 \operatorname{tol}_{\mathrm{inner}}=10^{-6} tol inner = 1 0 − 6 to keep the 100-bootstrap budget tractable, retaining the same step sizes and backtracking factor. Detailed optimization settings are listed in Table 5 .
Table 5. OSSA optimization budgets used at each stage of the pipeline. Joint support-and-alignment fits use initial step sizes η W = η s = 5 × 10 − 2 \eta_W=\eta_s=5\times10^{-2} η W = η s = 5 × 1 0 − 2 , backtracking factor β = 0.5 \beta=0.5 β = 0.5 with floor η min = 10 − 12 \eta_{\min}=10^{-12} η m i n = 1 0 − 12 , and projected-uniform s s s initialization. Fixed-support baseline W W W -refits hold s s s fixed and use three W W W initializations, including the identity (Appendix § 10 .9). “Outer” is the maximum number of block-coordinate sweeps for joint fits; for fixed-support W W W -refits, it gives the maximum number of W W W -update iterations per initialization. “Inner” is the maximum number of projected-gradient iterations per W W W -block and per support-vector update; each iteration uses backtracking line search. “Restarts” is the number of optimization runs from the specified initializations; the run with the largest training objective is retained.
Computational cost. In a community of size p p p , one dense outer iteration costs O ( n p 3 ) O(np^3) O ( n p 3 ) for the W W W -block matrix products and O ( n p 2 ) O(np^2) O ( n p 2 ) for forming D ( W ) D(W) D ( W ) , plus O ( K p 2 ) O(Kp^2) O ( K p 2 ) for support gradients and O ( K p log p ) O(Kp\log p) O ( K p log p ) for capped-simplex projections. The polar projection costs O ( p 3 ) O(p^3) O ( p 3 ) . Memory is O ( n p 2 ) O(np^2) O ( n p 2 ) for dense subject matrices. In the ABCD experiments, the largest community has about 30 nodes, so runtime is dominated by the number of subject-level matrix products and restarts rather than by the cubic polar step.
Additional experimental results and diagnostics
This appendix collects simulation sweep curves, robustness analyses, and ABCD training-side diagnostics referenced from Sections 3 and 4. Unless otherwise stated, the simulation experiments use the canonical OSSA generative model of Section 3.1 or the multi-clique extension of Section 3.2, with the same nuisance structure.
Complete simulation generator
In Section 3.1, the main text writes ζ i A = ξ i A + τ i A \zeta_i^A=\xi_i^A+\tau_i^A ζ i A = ξ i A + τ i A and ζ i B = ξ i B + τ i B \zeta_i^B=\xi_i^B+\tau_i^B ζ i B = ξ i B + τ i B to keep the simulation model concise. For each replicate we draw the data { ( A i , B i ) } i = 1 n \{(A_i,B_i)\}_{i=1}^n {( A i , B i ) } i = 1 n from the following procedure (single-clique unless noted; multi-clique substitutions in brackets). Default ambient size is p = 40 p=40 p = 40 for the canonical OSSA experiments and p = 50 p=50 p = 50 for the multi-clique experiments, with n = 30 n=30 n = 30 subjects per replicate. “LR r ( V , c ) \operatorname{LR}_r(V,c) LR r ( V , c ) ” denotes a symmetric rank-r r r random block of magnitude c c c , supported on V ⊆ [ p ] V\subseteq[p] V ⊆ [ p ] , generated as U U ⊤ ∘ Σ UU^\top\circ\Sigma U U ⊤ ∘ Σ with U ∈ R ∣ V ∣ × r U\in\mathbb{R}^{|V|\times r} U ∈ R ∣ V ∣ × r having i.i.d. N ( 0 , c 2 / r ) N(0,c^2/r) N ( 0 , c 2 / r ) entries and Σ \Sigma Σ a symmetrized random ± 1 \pm1 ± 1 sign matrix (entries Σ a b = 1 2 ( σ a b + σ b a ) \Sigma_{ab}=\frac{1}{2}(\sigma_{ab}+\sigma_{ba}) Σ ab = 2 1 ( σ ab + σ ba ) with σ a b ∼ i . i . d . Unif { − 1 , + 1 } \sigma_{ab}\overset{\mathrm{i.i.d.}}{\sim}\operatorname{Unif}\{-1,+1\} σ ab ∼ i.i.d. Unif { − 1 , + 1 } ), embedded as zero outside V × V V\times V V × V .
Draw planted support(s). Sample V ⋆ ⊆ [ p ] V^\star\subseteq[p] V ⋆ ⊆ [ p ] uniformly without replacement of size κ = 10 \kappa=10 κ = 10 . For the multi-clique generator, sample K ∈ { 2 , 3 } K\in\{2,3\} K ∈ { 2 , 3 } supports V ⋆ , ( ℓ ) ⊆ [ p ] V^{\star,(\ell)}\subseteq[p] V ⋆ , ( ℓ ) ⊆ [ p ] via a random permutation of [ p ] [p] [ p ] and consecutive blocks of size κ \kappa κ , with adjacent supports sharing exactly r ∈ { 0 , 4 } r\in\{0,4\} r ∈ { 0 , 4 } nodes (so they are pairwise disjoint when r = 0 r=0 r = 0 ). Defaults: K = 2 , κ = 10 , r = 0 K=2,\kappa=10,r=0 K = 2 , κ = 10 , r = 0 (disjoint); K = 2 , κ = 10 , r = 4 K=2,\kappa=10,r=4 K = 2 , κ = 10 , r = 4 (overlap-4); K = 3 , κ = 8 , r = 0 K=3,\kappa=8,r=0 K = 3 , κ = 8 , r = 0 (K = 3 K=3 K = 3 disjoint).
Draw low-rank block U i U_i U i and sign matrix Σ i \Sigma_i Σ i . Sample U i ∈ R κ × r s i g U_i\in\mathbb{R}^{\kappa\times r_{\mathrm{sig}}} U i ∈ R κ × r sig with i.i.d. N ( 0 , c s i g 2 / r s i g ) N(0,c_{\mathrm{sig}}^2/r_{\mathrm{sig}}) N ( 0 , c sig 2 / r sig ) entries and the symmetric sign mask Σ i \Sigma_i Σ i as above. Defaults r s i g = 3 r_{\mathrm{sig}}=3 r sig = 3 , c s i g = 1.5 c_{\mathrm{sig}}=1.5 c sig = 1.5 .
Form C i C_i C i (Canonical OSSA) or C i t o t C_i^{\mathrm{tot}} C i tot (multi) and embed. Canonical OSSA: C i = LR r s i g ( V ⋆ , c s i g ) C_i=\operatorname{LR}_{r_{\mathrm{sig}}}(V^\star,c_{\mathrm{sig}}) C i = LR r sig ( V ⋆ , c sig ) . Multi: C i t o t = ∑ ℓ = 1 K LR r s i g ( V ⋆ , ( ℓ ) , c s i g ) C_i^{\mathrm{tot}}=\sum_{\ell=1}^{K}\operatorname{LR}_{r_{\mathrm{sig}}}(V^{\star,(\ell)},c_{\mathrm{sig}}) C i tot = ∑ ℓ = 1 K LR r sig ( V ⋆ , ( ℓ ) , c sig ) with an independent ( U i ( ℓ ) , Σ i ( ℓ ) ) (U_i^{(\ell)},\Sigma_i^{(\ell)}) ( U i ( ℓ ) , Σ i ( ℓ ) ) for each support. Both are zero outside their planted supports.
Draw background matrices ξ i A , ξ i B \xi_i^A,\xi_i^B ξ i A , ξ i B . Each is a fresh i.i.d. rank-r b g r_{\mathrm{bg}} r bg symmetric block with the same LR recipe but supported on all p p p nodes, with amplitudes c b g A = c b g B = 0.6 c_{\mathrm{bg}}^A=c_{\mathrm{bg}}^B=0.6 c bg A = c bg B = 0.6 (Canonical OSSA) and c b g A = c b g B = 0.4 c_{\mathrm{bg}}^A=c_{\mathrm{bg}}^B=0.4 c bg A = c bg B = 0.4 (multi-clique), r b g = 4 r_{\mathrm{bg}}=4 r bg = 4 . Backgrounds are independent across modalities.
Draw modality-specific nuisance blocks τ i A , τ i B \tau_i^A,\tau_i^B τ i A , τ i B (Canonical OSSA only). Two disjoint modality-specific nuisance variation node sets D A , D B ⊆ [ p ] ∖ V ⋆ D^A,D^B\subseteq[p]\setminus V^\star D A , D B ⊆ [ p ] ∖ V ⋆ , each of size ∣ D ∣ = 12 |D|=12 ∣ D ∣ = 12 , are sampled once per replicate (not per subject) by a random permutation of [ p ] ∖ V ⋆ [p]\setminus V^\star [ p ] ∖ V ⋆ and consecutive slicing. For each subject i i i we then draw τ i B = LR r d e c ( D B , c d e c B ) \tau_i^B=\operatorname{LR}_{r_{\mathrm{dec}}}(D^B,c_{\mathrm{dec}}^B) τ i B = LR r dec ( D B , c dec B ) and τ i A = LR r d e c ( D A , c d e c A ) \tau_i^A=\operatorname{LR}_{r_{\mathrm{dec}}}(D^A,c_{\mathrm{dec}}^A) τ i A = LR r dec ( D A , c dec A ) independently, with r d e c = 3 r_{\mathrm{dec}}=3 r dec = 3 and c d e c A = c d e c B = 1.5 c_{\mathrm{dec}}^A=c_{\mathrm{dec}}^B=1.5 c dec A = c dec B = 1.5 . The multi-clique generator omits this step.
Draw noise matrices E i A , E i B E_i^A,E_i^B E i A , E i B . Symmetric Gaussian: E i A = 1 2 ( G i A + G i A ⊤ ) E_i^A=\frac{1}{2}(G_i^A+G_i^{A\top}) E i A = 2 1 ( G i A + G i A ⊤ ) with G i A ∼ N ( 0 , 1 ) p × p G_i^A\sim N(0,1)^{p\times p} G i A ∼ N ( 0 , 1 ) p × p (and analogously for E i B E_i^B E i B ), then scaled by σ A , σ B \sigma_A,\sigma_B σ A , σ B . Defaults σ A = σ B = 0.3 \sigma_A=\sigma_B=0.3 σ A = σ B = 0.3 (Canonical OSSA) and σ A = σ B = 0.4 \sigma_A=\sigma_B=0.4 σ A = σ B = 0.4 (multi-clique). Sweep ranges in the appendix vary σ ∈ [ 0.1 , 0.5 ] \sigma\in[0.1,0.5] σ ∈ [ 0.1 , 0.5 ] .
B i = 1 2 ( B ~ i + B ~ i T ) , A i = 1 2 ( A ~ i + A ~ i T ) , B_i = \frac{1}{2}\left(\widetilde{B}_i+\widetilde{B}_i^{\mathsf{T}}\right), \qquad A_i = \frac{1}{2}\left(\widetilde{A}_i+\widetilde{A}_i^{\mathsf{T}}\right), B i = 2 1 ( B i + B i T ) , A i = 2 1 ( A i + A i T ) ,
where B ~ i = C i + ξ i B + τ i B + E i B \widetilde{B}_i=C_i+\xi_i^B+\tau_i^B+E_i^B B i = C i + ξ i B + τ i B + E i B and A ~ i = W ⋆ C i ( W ⋆ ) T + ξ i A + τ i A + E i A \widetilde{A}_i=W^\star C_i(W^\star)^{\mathsf{T}}+\xi_i^A+\tau_i^A+E_i^A A i = W ⋆ C i ( W ⋆ ) T + ξ i A + τ i A + E i A (replace C i C_i C i by C i t o t C_i^{\mathrm{tot}} C i tot and drop the τ \tau τ terms in the multi-clique case), then enforce diag ( A i ) = diag ( B i ) = 0 \operatorname{diag}(A_i)=\operatorname{diag}(B_i)=0 diag ( A i ) = diag ( B i ) = 0 .
Draw W ⋆ W^\star W ⋆ . Sample G ∼ N ( 0 , 1 ) p × p G\sim N(0,1)^{p\times p} G ∼ N ( 0 , 1 ) p × p , take its (sign-corrected) QR factor Q Q Q so that Q ∼ Haar ( O ( p ) ) Q\sim\operatorname{Haar}(O(p)) Q ∼ Haar ( O ( p )) , and set
W ⋆ = polar ( ( 1 − α ) I p + α Q ) = U ~ V ~ T , U ~ Σ ~ V ~ T = SVD ( ( 1 − α ) I p + α Q ) , W^\star=\operatorname{polar}\left((1-\alpha)I_p+\alpha Q\right)=\widetilde{U}\widetilde{V}^{\mathsf{T}}, \qquad\widetilde{U}\widetilde{\Sigma}\widetilde{V}^{\mathsf{T}}=\operatorname{SVD}\left((1-\alpha)I_p+\alpha Q\right), W ⋆ = polar ( ( 1 − α ) I p + α Q ) = U V T , U Σ V T = SVD ( ( 1 − α ) I p + α Q ) ,
which equals I p I_p I p at α = 0 \alpha=0 α = 0 and a Haar-random orthogonal matrix at α = 1 \alpha=1 α = 1 , and is itself orthogonal for every α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] . The rotation strength is swept over α ∈ { 0 , 0.25 , 0.5 , 0.75 , 1 } \alpha\in\{0,0.25,0.5,0.75,1\} α ∈ { 0 , 0.25 , 0.5 , 0.75 , 1 } for OSSA, OSSA-noW, and the support-selection baselines; the OSSA-ORACLE reference uses α ∈ { 0 , 0.2 , 0.4 , 0.6 , 0.8 , 1 } \alpha\in\{0,0.2,0.4,0.6,0.8,1\} α ∈ { 0 , 0.2 , 0.4 , 0.6 , 0.8 , 1 } . The headline canonical OSSA configuration uses α = 1 \alpha=1 α = 1 and the multi-clique configuration uses α = 0.6 \alpha=0.6 α = 0.6 .
Full canonical OSSA sweep curves
Figure 3 reports the full rotation and noise trajectories summarized by Table 1 . The rotation sweep isolates the coordinate-mismatch setting, while the noise sweep shows that OSSA remains above the fixed-W W W baselines even when the planted support is observed through stronger subject-level noise.
Figure 3. Canonical OSSA support recovery (Jaccard with V ⋆ V^\star V ⋆ , mean ± \pm ± s.e., 10 replicates). (a) Rotation sweep α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] at σ = 0.3 \sigma=0.3 σ = 0.3 , n = 30 n=30 n = 30 . (b) Noise sweep σ ∈ [ 0.1 , 0.5 ] \sigma\in[0.1,0.5] σ ∈ [ 0.1 , 0.5 ] at α = 1 \alpha=1 α = 1 , n = 30 n=30 n = 30 . In panel (b), the grey band spans the minimum and maximum mean Jaccard values of SC-Degree, FC-Degree, Joint-SCxFC, Spectral-SC, and Spectral-FC at each noise level; the “Best fixed-W W W ” line follows the upper boundary.
Figure 4 reports the training-side diagnostics used to fix the number of FC communities in the baseline ABCD cohort. The diagnostics are computed only from the training absolute-FC mean within each split and therefore do not use validation or test data. Modularity peaks at Q = 3 Q=3 Q = 3 , while eigengap and silhouette show a strong coarser Q = 2 Q=2 Q = 2 split followed by a stable elbow at Q = 3 Q=3 Q = 3 . We use Q = 3 Q=3 Q = 3 as the smallest stable nontrivial partition beyond the coarse two-community split, and the choice is stable across split seeds. In the experiments, communities are estimated by spectral clustering on the training mean absolute-FC matrix. The multilayer DCSBM result motivates the shared-community assumption but is not used as a literal generative claim for ABCD.
Figure 4. ABCD community-detection diagnostics on the training absolute-FC mean. Light gray traces are per-seed; dark line is the pooled training average. The diagnostics support a stable Q = 3 Q = 3 Q = 3 working partition: modularity peaks at Q = 3 Q = 3 Q = 3 , and eigengap/silhouette show a coarse Q = 2 Q = 2 Q = 2 split with a clear elbow at Q = 3 Q = 3 Q = 3 . No split seed selects a different working partition under this rule.
Sparsity-budget misspecification
In practice the budget κ \kappa κ is rarely known exactly. We sweep the supplied κ ∈ { 4 , 6 , 8 , 10 , 12 , 14 , 16 } \kappa\in\{4,6,8,10,12,14,16\} κ ∈ { 4 , 6 , 8 , 10 , 12 , 14 , 16 } at planted κ ⋆ = 10 \kappa^\star=10 κ ⋆ = 10 , holding all other settings at the moderate-rotation, moderate-noise slice p = 40 p=40 p = 40 , n = 30 n=30 n = 30 , α = 0.6 \alpha=0.6 α = 0.6 , σ = 0.4 \sigma=0.4 σ = 0.4 (8 replicates per supplied κ \kappa κ , 6 random restarts), and report Jaccard, precision, and recall against V ⋆ V^\star V ⋆ .
OSSA degrades gracefully on both sides of the truth (Figure 5 ). Under-specification (κ < κ ⋆ \kappa< \kappa^\star κ < κ ⋆ ) yields high precision but limited recall (e.g., κ = 4 \kappa= 4 κ = 4 : precision 1.00, recall 0.40, Jaccard 0.40); over-specification (κ > κ ⋆ \kappa> \kappa^\star κ > κ ⋆ ) yields perfect recall and reduced precision (e.g., κ = 16 \kappa= 16 κ = 16 : precision 0.62, recall 1.00, Jaccard 0.62). At the truth κ = 10 \kappa= 10 κ = 10 , OSSA attains Jaccard 0.81 ± \pm ± 0.06 and precision 0.89. The strongest non-OSSA baseline at κ = 10 \kappa= 10 κ = 10 is JOINT-SCXFC at 0.49, which tracks below OSSA across the entire grid. OSSA-NOW matches or slightly exceeds OSSA at α = 0.6 \alpha= 0.6 α = 0.6 for κ ≤ 10 \kappa\le10 κ ≤ 10 (where W = I W = I W = I is a useful approximation at moderate rotation) but degrades faster on the over-specified side. For this budget-misspecification sweep, we also include SPECTRAL-SC and SPECTRAL-FC, which rank nodes by the absolute loading of the leading eigenvector of the training mean SC and FC matrices, respectively. Missing or extra budget translates into the corresponding precision/recall trade-off at the planted nodes rather than catastrophic Jaccard loss, indicating that OSSA is a usable estimator when κ \kappa κ is supplied heuristically.
Figure 5. Robustness to sparsity-budget misspecification at κ ⋆ = 10 \kappa^\star= 10 κ ⋆ = 10 , α = 0.6 \alpha= 0.6 α = 0.6 , σ = 0.4 \sigma= 0.4 σ = 0.4 (mean ± \pm ± s.e., 8 replicates). (a) Jaccard with V ⋆ \mathcal{V}^\star V ⋆ vs. supplied κ \kappa κ . (b) Precision and recall vs. supplied κ \kappa κ for OSSA, OSSA-NOW, and the strongest non-OSSA baseline (JOINT-SCXFC); solid = precision, dashed = recall.
Selection stability
We assess stability of the selected support along two complementary axes on a single base dataset at α = 0.6 \alpha= 0.6 α = 0.6 , σ = 0.4 \sigma= 0.4 σ = 0.4 , n = 30 n = 30 n = 30 , κ ⋆ = 10 \kappa^\star= 10 κ ⋆ = 10 : per-node selection frequency across 40 bootstrap resamples (with replacement) of the subjects. Each bootstrap fit uses one random initialization, so the bootstrap curve captures both subject-resampling variability and single-start optimization variability. We also examine the distribution of pairwise Jaccard between 15 random initializations on the same (non-resampled) data for OSSA and OSSA-NOW (Figure 6 b).
Figure 6. Selection stability of OSSA at α = 0.6 \alpha= 0.6 α = 0.6 , σ = 0.4 \sigma= 0.4 σ = 0.4 , n = 30 n = 30 n = 30 . (a) Per-node bootstrap selection frequency, sorted descending; circled markers indicate planted nodes (∣ V ⋆ ∣ = 10 |V^\star| = 10 ∣ V ⋆ ∣ = 10 ). (b) Violin distribution of pairwise Jaccard between 15 random restarts on the same data, for OSSA and OSSA-NOW.
Bootstrap selection frequency on the 10 planted nodes is substantially higher than on non-planted nodes for OSSA (0.46 vs. 0.18; Figure 6a), consistent with concentration on V ⋆ V^\star V ⋆ rather than a restart-dependent local optimum. The moderate pairwise Jaccard similarity across restarts indicates sensitivity of the fitted support to initialization, consistent with the nonconvexity of the joint optimization problem. For the main experiments, we use multiple restarts and keep the run with the largest training objective. However, we note that this selection rule does not guarantee a global maximizer or eliminate variation across independently generated sets of restarts. OSSA-NOW achieves higher restart concentration at this moderate rotation (α = 0.6 \alpha= 0.6 α = 0.6 , where W = I W = I W = I is a useful approximation to W ⋆ W^\star W ⋆ and the smaller-dimensional optimization is easier to stabilize) but pays the cost in recovery quality at α = 1 \alpha= 1 α = 1 (Section 3.1, Table 1).
Multi-clique simulation details
This subsection gives the full design behind Section 3.2. We use one community with p = 50 p = 50 p = 50 nodes and n = 30 n = 30 n = 30 subjects. Each replicate contains K K K planted supports { V ℓ ⋆ } ℓ = 1 K \{V^\star_\ell\}_{\ell=1}^K { V ℓ ⋆ } ℓ = 1 K , each carrying an independently sampled mixed-sign low-rank signal block. The subject-level signal is
C i t o t = ∑ ℓ = 1 K C i ( ℓ ) , C_i^{\mathrm{tot}} = \sum_{\ell=1}^{K} C_i^{(\ell)}, C i tot = ℓ = 1 ∑ K C i ( ℓ ) ,
and the observed matrices are
B i = C i t o t + ξ i B + σ B E i B , A i = W ⋆ C i t o t W ⋆ ⊤ + ξ i A + σ A E i A . B_i = C_i^{\mathrm{tot}} + \xi_i^B + \sigma_B E_i^B,\qquad A_i = W^\star C_i^{\mathrm{tot}} W^{\star\top} + \xi_i^A + \sigma_A E_i^A. B i = C i tot + ξ i B + σ B E i B , A i = W ⋆ C i tot W ⋆ ⊤ + ξ i A + σ A E i A .
We fix rotation strength α = 0.6 \alpha= 0.6 α = 0.6 and noise level σ = 0.4 \sigma= 0.4 σ = 0.4 . We evaluate three planted regimes: two disjoint settings, ( K , κ ) = ( 2 , 10 ) (K, \kappa) = (2, 10) ( K , κ ) = ( 2 , 10 ) and ( 3 , 8 ) (3, 8) ( 3 , 8 ) , and one overlapping setting with K = 2 K = 2 K = 2 , κ = 10 \kappa= 10 κ = 10 , and exactly four shared nodes. The overlapping nodes receive additive signal from both planted supports. No extra modality-specific nuisance variation blocks are added, because the other planted supports already act as structured distractors for each target support.
We compare OSSA-K K K against four size-matched competitors. SPECTRAL-SC-K K K : compute the top K K K eigenvectors of the training mean SC matrix B ˉ \bar{B} B ˉ . For component ℓ \ell ℓ , rank nodes by ∣ v ℓ ( j ) ∣ |v_\ell(j)| ∣ v ℓ ( j ) ∣ and select the top κ \kappa κ nodes. If a disjoint version is used, previously selected nodes are removed before the next component. COMMUNICABILITY-K K K clusters nodes using communicability distance. SEQUENTIAL-OSSA repeatedly fits canonical OSSA, masks the selected nodes, and refits until K K K supports are obtained. RANDOM-K K K samples K K K supports uniformly. Unlike OSSA-K K K , SEQUENTIAL-OSSA estimates a fresh rotation at each step and enforces disjoint supports by construction.
For this diagnostic simulation, λ \lambda λ for OSSA-K K K is selected on the grid reported in Appendix D.7, choosing the smallest value within one standard error of the peak best-match Jaccard. Because planted labels are available here, this λ b e s t \lambda_{\mathrm{best}} λ best rule is used only to summarize the recoverability envelope of the method; it is not used as a real-data tuning rule. We report best-match Jaccard after Hungarian assignment to the planted supports, together with the mean pairwise overlap of the fitted supports. All methods use six random restarts, with eight replicates for K = 2 K = 2 K = 2 and six for K = 3 K = 3 K = 3 .
Table 6. Full multi-clique support recovery (mean ± \pm ± s.e.). JACC: best-match Jaccard. OVL: mean pairwise overlap of fitted supports. In the two disjoint regimes all methods produce fitted overlap 0.00 ± \pm ± 0.00; overlap is therefore reported only for the r = 4 r=4 r = 4 regime.
Continuous λ \lambda λ -trajectory
The λ b e s t \lambda_{\mathrm{best}} λ best values summarized in § 3.2 and Appendix § 10 .6 are read off a dense log-spaced grid spanning four decades. We fit OSSA-K K K at λ ∈ { 0 , 1 , 2 , 3 , 5 , 10 , 20 , 30 , 50 , 70 , 100 , 150 , 200 , 300 , 500 , 700 , 1000 , 2000 , 3000 } \lambda\in\{0, 1, 2, 3, 5, 10, 20, 30, 50, 70, 100, 150, 200, 300, 500, 700, 1000, 2000, 3000\} λ ∈ { 0 , 1 , 2 , 3 , 5 , 10 , 20 , 30 , 50 , 70 , 100 , 150 , 200 , 300 , 500 , 700 , 1000 , 2000 , 3000 } on each of the three regimes from § 3.2 (K = 2 K=2 K = 2 disjoint, K = 2 K=2 K = 2 with r = 4 r=4 r = 4 shared nodes, K = 3 K=3 K = 3 disjoint), using the same seeds and replicate counts as the main experiment (8 replicates for K = 2 K=2 K = 2 , 6 for K = 3 K=3 K = 3 , 6 random restarts per fit). The vertical line in each panel of Figure 7 marks the selected λ b e s t \lambda_{\mathrm{best}} λ best for that regime. This oracle selection is used only to summarize whether the λ \lambda λ -path contains a recoverability region. It is not a deployable tuning rule and is not used in ABCD.
Figure 7. Continuous λ \lambda λ -trajectory of OSSA-K K K across three planted regimes (mean ± \pm ± s.e.; 8 replicates for K = 2 K=2 K = 2 , 6 for K = 3 K=3 K = 3 ). Top row: mean pairwise overlap of fitted supports; dashed line marks the planted overlap. Bottom row: best-match Jaccard with the planted supports. Columns: K = 2 K=2 K = 2 disjoint, K = 2 K=2 K = 2 with r = 4 r=4 r = 4 shared nodes, K = 3 K=3 K = 3 disjoint. Vertical dotted line marks λ b e s t \lambda_{\mathrm{best}} λ best summarized in Table 2 . Full baseline values are reported in Appendix Table 6.
Table 2. Multi-support simulation summary (mean ± \pm ± s.e.). The OSSA-K K K and best-baseline columns report best-match Jaccard. Fitted overlap is the mean pairwise support overlap. The full baseline table is in Appendix § 10 .6.
The trajectories share a common shape: at small λ \lambda λ the supports collapse (high pairwise overlap, low Jaccard against the planted partition); raising λ \lambda λ separates the supports until fitted overlap matches the planted value (with λ b e s t \lambda_{\mathrm{best}} λ best near this crossing); further increases drive the supports into full disjointness. In the disjoint regimes, fitted overlap reaches zero between λ = 100 \lambda=100 λ = 100 and λ = 200 \lambda=200 λ = 200 . For K = 2 K=2 K = 2 , Jaccard remains near 0.95 across λ ∈ [ 150 , 300 ] \lambda\in[150, 300] λ ∈ [ 150 , 300 ] , whereas for K = 3 K=3 K = 3 it peaks at λ = 150 \lambda=150 λ = 150 and declines over the same interval. In the r = 4 r=4 r = 4 regime, fitted overlap shows an overall decrease from κ = 10 \kappa=10 κ = 10 at λ = 0 \lambda=0 λ = 0 to approximately r = 4 r=4 r = 4 near λ b e s t = 200 \lambda_{\mathrm{best}}=200 λ best = 200 (3.75 ± \pm ± 0.56), with Jaccard peaking near this crossing and declining as larger penalties force the supports toward full disjointness.
ABCD -robustness
We verify that OSSA’s lead over the nine comparison methods in Table 7 is preserved at κ ∈ { 3 , 5 , 8 , 10 } \kappa\in\{3,5,8,10\} κ ∈ { 3 , 5 , 8 , 10 } , not only at the design choice κ = 3 \kappa= 3 κ = 3 . Each row summarizes the same 30 (seed, community) units. The SC-degree-quartile-matched null uses 1000 draws per unit at κ = 3 \kappa= 3 κ = 3 and 30 draws per unit at κ ∈ { 5 , 8 , 10 } \kappa\in\{5,8,10\} κ ∈ { 5 , 8 , 10 } (Table 7 ).
Table 7.
The headline pattern is that OSSA achieves the largest mean null-corrected gain M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln at every tested budget. At κ = 3 \kappa= 3 κ = 3 , SC-DEGREE, JOINT-SCXFC, and COMMUNICABILITY have positive mean null-corrected gains (+0.59 to +0.69), showing that these selectors achieve higher aligned correlations than the degree-matched null average. At the tested budgets κ ≥ 5 \kappa\ge5 κ ≥ 5 , SC-DEGREE, JOINT-SCXFC, COMMUNICABILITY, FC-DEGREE, and SDI have near-zero or negative mean null-corrected gains M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln . OSSA, in contrast, retains M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln gain of +0.37 to +0.41 at κ ∈ { 5 , 8 , 10 } \kappa\in\{5,8,10\} κ ∈ { 5 , 8 , 10 } , exceeding all compared baselines at each of these budgets.
Table 7: ABCD κ \kappa κ -robustness: OSSA vs. nine comparison methods at κ ∈ { 3 , 5 , 8 , 10 } \kappa\in\{3,5,8,10\} κ ∈ { 3 , 5 , 8 , 10 } , mean ± \pm ± s.e. across 30 (seed, community) units. The table reports M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln gain, defined as M 2 , a l n M_{2,\mathrm{aln}} M 2 , aln minus the mean SC-degree-quartile-matched null.
ABCD baseline W-fitting protocol
For each baseline support V ^ q m \hat{V}^{m}_{q} V ^ q m , the per-method alignment W q m W^{m}_{q} W q m is obtained by running the OSSA W W W -block of Algorithm 1 on training subjects with s = 1 V ^ q m s = \mathbf{1}_{\hat{V}^{m}_{q}} s = 1 V ^ q m held fixed, using three initializations (including the identity), up to 200 W W W -update iterations per initialization, and monotone backtracking. The run with the largest training objective is retained. At κ = 3 \kappa= 3 κ = 3 , the M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln random-null W r W_{r} W r is fit using a lighter schedule of up to 50 iterations from a single random orthogonal initialization to keep the 1000-draw null tractable per (seed, community) unit. The deep-learning baselines (BRAINGNN, BRAINNETCNN) are fit on a 3 × 3 3 \times3 3 × 3 (learning rate, weight decay) grid selected by validation loss.
Deep-learning baseline details. BRAINGNN and BRAINNETCNN are reimplemented in NumPy with hand-derived gradients and trained per (split-seed, community, κ \kappa κ ) on the same train/val/test split as OSSA.
Input modality. BRAINGNN: per-community training mean D ˉ = 1 n ∑ i A i ∘ B i \bar{D} = \frac{1}{n}\sum_i A_i \circ B_i D ˉ = n 1 ∑ i A i ∘ B i . BRAINNETCNN: per-subject SC submatrix B i B_i B i .
Prediction target. BRAINGNN: maximize attention-pooled alignment energy a T D ˉ a a^{\mathsf{T}}\bar{D}a a T D ˉ a (a = σ ( θ ) a = \sigma(\theta) a = σ ( θ ) ). BRAINNETCNN: regress the z z z -scored scalar y i = ⟨ A i , B i ⟩ F y_i = \langle A_i,B_i\rangle_F y i = ⟨ A i , B i ⟩ F .
Loss. BRAINGNN: − a T D ˉ a -a^{\mathsf{T}}\bar{D}a − a T D ˉ a . BRAINNETCNN: mean squared error.
Architecture. BRAINGNN: attention vector θ ∈ R p \theta\in\mathbb{R}^{p} θ ∈ R p , a = σ ( θ ) a = \sigma(\theta) a = σ ( θ ) , init N ( 0 , 0.1 2 ) N(0,0.1^2) N ( 0 , 0. 1 2 ) . BRAINNETCNN: 3-stage E2E→ \to → E2N→ \to → N2G with W r o w , W c o l , W 2 ∈ R p × p W_{\mathrm{row}}, W_{\mathrm{col}}, W_2 \in\mathbb{R}^{p \times p} W row , W col , W 2 ∈ R p × p , W 3 ∈ R p W_3 \in\mathbb{R}^{p} W 3 ∈ R p , init i.i.d. N ( 0 , 1 / p ) N(0,1/p) N ( 0 , 1/ p ) .
Optimizer. Adam (β 1 = 0.9 \beta_1=0.9 β 1 = 0.9 , β 2 = 0.999 \beta_2=0.999 β 2 = 0.999 , ε = 10 − 8 \varepsilon=10^{-8} ε = 1 0 − 8 ), full-batch over the community.
Learning-rate grid. η ∈ { 10 − 2 , 10 − 3 , 10 − 4 } \eta\in\{10^{-2},10^{-3},10^{-4}\} η ∈ { 1 0 − 2 , 1 0 − 3 , 1 0 − 4 } .
Weight-decay grid. λ w d ∈ { 0 , 10 − 4 , 10 − 3 } \lambda_{\mathrm{wd}} \in\{0, 10^{-4}, 10^{-3}\} λ wd ∈ { 0 , 1 0 − 4 , 1 0 − 3 } .
Batch size. Full batch (n t r n_{\mathrm{tr}} n tr subjects).
Epochs. BRAIN GNN: 200. BRAIN NETCNN: 20.
Restarts and early stopping. 16 restarts per (seed, q q q , κ \kappa κ ); each draws (η \eta η , λ w d \lambda_{\mathrm{wd}} λ wd ) from the 3 × 3 3 \times3 3 × 3 grid by a seeded RNG. No within-restart early stopping. The best restart is selected on validation.
Validation criterion. BRAIN GNN: − a T D ˉ v a l a -a^{\mathsf{T}}\bar{D}_{\mathrm{val}}a − a T D ˉ val a . BRAIN NETCNN: validation MSE.
Saliency. BRAIN GNN: a v = σ ( θ v ) a_v = \sigma(\theta_v) a v = σ ( θ v ) . BRAIN NETCNN: closed-form gating gradient sal v = 1 n ∑ i ∣ ( W i T h i ( 2 ) − y i ) ( W 3 ) v h i , v ( 2 ) ∣ \operatorname{sal}_v = \frac{1}{n}\sum_i \left|(W_i^{\mathsf{T}}h_i^{(2)} - y_i)(W_3)_v h_{i,v}^{(2)}\right| sal v = n 1 ∑ i ( W i T h i ( 2 ) − y i ) ( W 3 ) v h i , v ( 2 ) at m = 1 m=1 m = 1 .
Saliency → \to → κ \kappa κ -node support. V ^ = Top κ ( ⋅ ) \hat{V} = \operatorname{Top}_{\kappa}(\cdot) V ^ = Top κ ( ⋅ ) , ties broken by ascending node index. The hard support is then passed through the same W W W -refit and held-out metric pipeline as every other baseline.
Table 9. Subject-level paired bootstrap comparisons on held-out subjects from one split. Δ M 1 , a l n \Delta M_{1,\mathrm{aln}} Δ M 1 , aln denotes OSSA minus the comparator. The 95% confidence intervals use 10,000 bootstrap replicates with the same resampled subject indices for all methods. Training-fitted supports and the community partition are held fixed, so the intervals exclude support-selection variability.
ABCD multi-clique λ \lambda λ -sensitivity
Diagnostic criterion. The K K K -support fit is not used as the default estimator in ABCD; it is a diagnostic for whether one FC community contains several dominant aligned structural cores. Since the OSSA objective is a trace alignment criterion, the primary held-out diagnostic is M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln , evaluated on each fitted κ \kappa κ -node support after the same training-side W W W -refit used in Table 3 . The correlation metrics M 2 , a l n M_{2,\mathrm{aln}} M 2 , aln and M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln gain are retained as scale-free diagnostics of aligned FC–SC patterns after rotation, with degree-matched correction applied only to M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln gain; they complement but do not replace the objective optimized by OSSA.
Support geometry. Figure 8 shows a collapse-to-separation transition. For λ ≤ 10 2 \lambda\le10^2 λ ≤ 1 0 2 , the fitted supports nearly coincide: for K = 2 K = 2 K = 2 , the mean pairwise Jaccard is 0.983 and ∣ U ∣ / κ = 1.011 |U|/\kappa= 1.011 ∣ U ∣/ κ = 1.011 ; for K = 3 K = 3 K = 3 , the supports fully collapse with Jaccard 1.000 and ∣ U ∣ / κ = 1.000 |U|/\kappa= 1.000 ∣ U ∣/ κ = 1.000 . Increasing λ \lambda λ first produces partial separation and then full disjointness. At λ = 10 4 \lambda= 10^{4} λ = 1 0 4 , the pairwise Jaccard is 0, with ∣ U ∣ / κ = 2.000 |U|/\kappa= 2.000 ∣ U ∣/ κ = 2.000 for K = 2 K = 2 K = 2 and 3.000 for K = 3 K = 3 K = 3 . Thus the optimizer can separate the supports when forced, but the path does not reveal a stable intermediate multi-core regime.
Figure 8. ABCD multi-clique λ \lambda λ -diagnostic. Top row: support geometry as λ \lambda λ varies. At small λ \lambda λ , the K K K supports collapse onto the same κ \kappa κ -node set. At large λ \lambda λ , the overlap penalty forces separation. Bottom row: held-out metrics evaluated on each κ = 3 \kappa= 3 κ = 3 support after the Table 3-style training-side W W W -refit. M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln is the primary held-out OSSA objective and decreases after forced separation. M 2 , a l n M_{2,\mathrm{aln}} M 2 , aln and M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln gain are scale-free correlation diagnostics and increase at large λ \lambda λ , indicating secondary correlation-structured motifs rather than multiple dominant high-M 1 M_1 M 1 alignment cores.
Held-out metrics. The held-out metrics separate the primary objective from secondary correlation structure. At λ = 10 2 \lambda= 10^{2} λ = 1 0 2 , where the supports collapse, the mean clique-level M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln is essentially the canonical OSSA value: 10.20 ± \pm ± 0.85 for K = 2 K = 2 K = 2 and 10.43 ± \pm ± 0.85 for K = 3 K = 3 K = 3 , compared with 10.42 ± \pm ± 0.80 for canonical OSSA. Once separation is forced, M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln decreases: at λ = 10 4 \lambda= 10^{4} λ = 1 0 4 , it is 6.42 ± \pm ± 0.51 for K = 2 K = 2 K = 2 and 4.60 ± \pm ± 0.34 for K = 3 K = 3 K = 3 . In contrast, M 2 , a l n M_{2,\mathrm{aln}} M 2 , aln and M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln gain rise at λ = 10 4 \lambda= 10^{4} λ = 1 0 4 , reaching approximately 0.86. We interpret this as evidence for secondary scale-free FC-SC correlation motifs, not as evidence for several dominant OSSA cores, because these supports no longer remain competitive under the primary alignment-magnitude objective. Therefore, under the community construction and λ \lambda λ grid used here, ABCD supports a single dominant high-M 1 M_1 M 1 aligned core at κ = 3 \kappa= 3 κ = 3 , with multi-clique OSSA serving as a diagnostic extension.
Multi-support extensions of ABCD baselines
Protocol. This auxiliary analysis checks whether the single-core conclusion is an artefact of comparing the K K K -support OSSA diagnostic only with single-support baselines. We extend the non-neural support selectors in Table 3 to K ∈ { 2 , 3 } K \in\{2,3\} K ∈ { 2 , 3 } supports at the same budget κ = 3 \kappa= 3 κ = 3 . For ranking-based selectors, the K K K supports are consecutive disjoint κ \kappa κ -node blocks from the training-only node ranking. Thus V ( 1 ) V^{(1)} V ( 1 ) contains the top κ \kappa κ nodes, V ( 2 ) V^{(2)} V ( 2 ) contains the next κ \kappa κ nodes after removing V ( 1 ) V^{(1)} V ( 1 ) , and so on. Random-K K K samples K K K disjoint κ \kappa κ -node blocks uniformly within each community and averages over R = 200 R = 200 R = 200 draws per seed-community unit. OSSA-K K K and OSSA-noW-K K K are evaluated on the same overlap-penalty grid λ ∈ { 10 2 , 10 3 , 10 4 } \lambda\in\{10^{2}, 10^{3}, 10^{4}\} λ ∈ { 1 0 2 , 1 0 3 , 1 0 4 } . Each fitted κ \kappa κ -node support is then evaluated by the same fixed-support training-side W W W -refit and held-out metrics used in Table 3 . We report mean-clique metrics, averaging over the K K K supports within each seed-community unit, so that a larger K K K is judged by per-support yield rather than by a mechanically larger union.
Figure 9. ABCD multi-support extensions of Table 3 baselines: mean-clique M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln (κ = 3 \kappa= 3 κ = 3 , 30 seed-community units, error bars = s.e.). Figure 9: ABCD multi-support extensions of the Table 3 baselines, evaluated by the primary held-out objective M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln . Bars report mean-clique M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln , averaging over the K K K fitted κ = 3 \kappa= 3 κ = 3 supports within each seed-community unit; error bars are standard errors over the 30 seed-community units. The dashed line shows the single-support OSSA reference used in this multi-support diagnostic. OSSA-K remains close to this value only when supports collapse or partially overlap; forced separation lowers the primary alignment magnitude. Ranking-based multi-support extensions are substantially lower.
Primary held-out alignment. Figure 9 shows that extending the baselines to several supports does not produce multiple competitive high-M 1 M_{1} M 1 cliques. OSSA-K remains close to the canonical single-support value only in collapsed or partially collapsed regimes. At λ = 10 2 \lambda= 10^{2} λ = 1 0 2 , the K = 2 K = 2 K = 2 fit has mean-clique M 1 , a l n = 10.20 ± 0.85 M_{1,\mathrm{aln}} = 10.20 \pm0.85 M 1 , aln = 10.20 ± 0.85 , but its supports nearly coincide (∣ U ∣ / κ = 1.01 |U|/\kappa= 1.01 ∣ U ∣/ κ = 1.01 , mean pairwise Jaccard 0.98); the K = 3 K = 3 K = 3 fit fully collapses and gives M 1 , a l n = 10.43 ± 0.85 M_{1,\mathrm{aln}} = 10.43 \pm0.85 M 1 , aln = 10.43 ± 0.85 . When the overlap penalty forces disjoint supports at λ = 10 4 \lambda= 10^{4} λ = 1 0 4 , mean-clique M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln drops to 6.42 ± 0.51 6.42 \pm0.51 6.42 ± 0.51 for K = 2 K = 2 K = 2 and 4.60 ± 0.34 4.60 \pm0.34 4.60 ± 0.34 for K = 3 K = 3 K = 3 . The ranking-based K K K -support baselines are lower throughout: their best mean-clique M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln is 2.06 ± 0.23 2.06 \pm0.23 2.06 ± 0.23 for K = 2 K = 2 K = 2 and 1.53 ± 0.17 1.53 \pm0.17 1.53 ± 0.17 for K = 3 K = 3 K = 3 . Thus forcing multiple disjoint supports does not appear beneficial as a dimension-reduction step in ABCD.
Support-index degradation. For ranking-based extensions, the support index makes the same pattern more explicit. Figure 10 shows that, for SC-DEGREE, FC-DEGREE, JOINT-SCxFC and COMMUNICABILITY, V ( 1 ) V^{(1)} V ( 1 ) , the first κ \kappa κ -node block, corresponds to the original single-support baseline, whereas the later supports have much smaller held-out M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln . This degradation is expected when the FC-derived communities are already small: after the first high-signal support has been removed, the remaining disjoint blocks do not provide comparable high-M 1 M_{1} M 1 structural cores.
Scale-free diagnostics. The scale-free diagnostics tell a complementary story rather than changing the primary conclusion. As in Appendix D.10, high-λ \lambda λ separated OSSA-K fits can increase M 2 , a l n M_{2,\mathrm{aln}} M 2 , aln or M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln gain, but these metrics measure within-support FC-SC correlation after scale normalization. They do not replace the trace-alignment magnitude optimized by OSSA. We therefore interpret the high-λ \lambda λ scale-free gains as secondary correlation-structured motifs, not as evidence for several dominant high-M 1 M_{1} M 1 aligned cores.
Structural connectivity within consensus supports
Table 4 in the main text reports the subject-averaged SC edge weights and their degree-matched reference ratios. Each consensus support forms a within-lobe triangle. The temporal and occipital supports lie in the right hemisphere, whereas the frontal support includes the left medial orbitofrontal region and bilateral frontal poles.
Figure 10. Per-support degradation for ranking-based baseline extensions with K ∈ { 2 , 3 } K \in\{2,3\} K ∈ { 2 , 3 } . Each method forms K K K consecutive disjoint κ = 3 \kappa= 3 κ = 3 blocks from its training-only ranking. V ( 1 ) V^{(1)} V ( 1 ) corresponds to the original single-support baseline; for SC-DEGREE, FC-DEGREE, JOINT-SCXFC and COMMUNICABILITY, the later supports have much smaller held-out M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln . The dashed line shows the single-support OSSA reference used in this multi-support diagnostic.
Empirical diagnostics of the fitted alignment
At κ = 3 \kappa= 3 κ = 3 , the normalized squared projector distance ∥ W ^ P V ^ W ^ ⊤ − P V ^ ∥ F 2 / ( 2 κ ) \lVert\widehat{W}P_{\widehat{V}}\widehat{W}^{\top} - P_{\widehat{V}}\rVert_{F}^{2}/(2\kappa) ∥ W P V W ⊤ − P V ∥ F 2 / ( 2 κ ) has community-wise means ranging from 0.54 to 0.67 over ten split seeds. Reference means based on 1,000 Haar-random orthogonal matrices of each community’s dimension range from 0.80 to 0.90. All 30 seed–community units lie below the 2.5th percentile of their corresponding Haar reference distribution.
For regional loadings ℓ a = ∑ j ∈ V ^ W ^ a j 2 \ell_a = \sum_{j\in\widehat{V}} \widehat{W}_{aj}^{2} ℓ a = ∑ j ∈ V W aj 2 , we quantify concentration using the participation ratio P R = ( ∑ a ℓ a ) 2 / ∑ a ℓ a 2 \mathrm{PR} = (\sum_a \ell_a)^2/\sum_a \ell_a^2 PR = ( ∑ a ℓ a ) 2 / ∑ a ℓ a 2 , which measures the effective number of contributing regions. Community-wise mean PR values over ten split seeds are approximately 5–10, compared with 10–19 under the Haar reference. The corresponding mean peak regional loadings, max a ℓ a \max_a \ell_a max a ℓ a , are approximately 0.59–0.69.
We measured the fraction of ∥ W ^ P V ^ W ^ ⊤ ∥ F 2 \lVert\widehat{W}P_{\widehat{V}}\widehat{W}^{\top}\rVert_{F}^{2} ∥ W P V W ⊤ ∥ F 2 contributed by matrix entries corresponding to contralateral homologous regions. Across the three communities, its means over ten split seeds are approximately 3.2–8.9 times the corresponding Haar-reference means.
For each community, we compared the fitted projectors W ^ P V ^ W ^ ⊤ \widehat{W}P_{\widehat{V}}\widehat{W}^{\top} W P V W ⊤ across all 45 pairs of the ten split seeds using squared Frobenius distance divided by 2 κ 2\kappa 2 κ . Mean distances were 0.0002, 0.113 and 0.0001 for the frontal, temporal and occipital communities, respectively. The observed stability is consistent with reproducibility of the spectral structure of mean training FC and does not by itself establish biological specificity.
Table 10 : Sensitivity to community construction using the same training mean ∣ F C ∣ |FC| ∣ F C ∣ . Node recovery summarizes retention of the original nine selected regions under each construction. Held-out M 1 M_{1} M 1 values are not directly comparable across Q Q Q , because community size changes the number of candidate edges.
Table 10. Sensitivity to community construction using the same training mean ∣ F C ∣ |FC| ∣ F C ∣ . Node recovery summarizes retention of the original nine selected regions under each construction. Held-out M 1 M_{1} M 1 values are not directly comparable across Q Q Q , because community size changes the number of candidate edges.
ABCD second-visit replication details
This appendix documents the second-visit replication summarised in § 4 on the ABCD Year-2 follow-up (“second-visit”) release. The protocol is identical to the baseline (Year-1) evaluation: no hyperparameter is retuned, no seed is reshuffled, and the same per-method W W W -fit budget, multi-clique grid, and aggregation rules are reused.
Data and pipeline. The ABCD second-visit release contributes 1,909 subjects parcellated by the same 68-region Desikan-Killiany atlas as the baseline [11 ] . The canonical preprocessing pipeline (transposition to ( N , p , p ) (N,p,p) ( N , p , p ) , exact symmetrization, diagonal enforcement, Fisher-z z z then non-negative clipping for FC, and log ( 1 + ⋅ ) \log(1+\cdot) log ( 1 + ⋅ ) for SC) and the cohort-median 5 σ 5\sigma 5 σ QC rule are applied without modification. QC drops 12 subjects (none with simultaneous FC and SC flags) and leaves n A B C D 2 = 1 , 897 n_{\mathrm{ABCD2}}=1,897 n ABCD2 = 1 , 897 subjects. The 60/20/20 deterministic splits over the same 10 seeds yield n t r a i n = 1 , 138 n_{\mathrm{train}}=1,138 n train = 1 , 138 and n v a l = n t e s t ∈ { 379 , 380 } n_{\mathrm{val}}=n_{\mathrm{test}}\in\{379,380\} n val = n test ∈ { 379 , 380 } per seed. The one-time test-evaluation rule of the baseline protocol is reused: each (method, metric, split) tuple is touched exactly once on the second-visit cohort.
Community partition. Spectral diagnostics on the training absolute-FC mean again select Q ∗ = 3 Q^{*}=3 Q ∗ = 3 in every one of the 10 split seeds. The pooled training average likewise yields Q p o o l = 3 Q_{\mathrm{pool}}=3 Q pool = 3 . Cross-seed ARI on the modal-Q Q Q partitions is 0.99 ± 0.01 0.99\pm0.01 0.99 ± 0.01 (min 0.96 across the 45 seed pairs), indicating near-perfect agreement up to label permutation (Figure 11 ). The pooled community sizes ( 31 , 23 , 14 ) (31,23,14) ( 31 , 23 , 14 ) are within one node of the baseline pooled sizes ( 30 , 23 , 15 ) (30,23,15) ( 30 , 23 , 15 ) , supporting that the same three-community organisation is recovered at the second visit.
Figure 11. ABCD second-visit community-detection diagnostics. Light gray traces are per-seed; the dark line is the pooled training average. The eigengap of L s y m L_{\mathrm{sym}} L sym , Newman-Girvan modularity, and silhouette all peak at Q ∗ = 3 Q^{*}=3 Q ∗ = 3 , with no seed disagreeing, identical to the baseline cohort.
Per-community budget. The per-community budget κ = 3 \kappa= 3 κ = 3 from the baseline cohort is reused without retuning. Figure 12 summarizes validation J ( κ ) / κ J(\kappa)/\kappa J ( κ ) / κ after matching communities across split seeds to the pooled reference partition by maximum node overlap. Among the tested budgets κ ≥ 3 \kappa\ge3 κ ≥ 3 , the mean is highest at κ = 3 \kappa= 3 κ = 3 in each community, consistent with the baseline results.
Figure 12. ABCD second-visit sparsity sweep after matching communities across splits to the pooled partition by maximum node overlap. Points show means and error bars show s.e.; counts below 10 are labeled, and single-split results have no error bar. Larger budgets may use different split subsets. The κ = 1 \kappa= 1 κ = 1 point is a trivial zero-objective floor. For tested budgets κ ≥ 3 \kappa\ge3 κ ≥ 3 , mean validation J ( κ ) / κ J(\kappa)/\kappa J ( κ ) / κ decreases in all three communities.
Canonical OSSA evaluation. The summary appears in § 4 (“Second-visit replication”); this appendix provides per-method numbers and per-community decomposition (Table 11 ). At κ = 3 \kappa= 3 κ = 3 over 30 (seed, community) units, OSSA attains M 1 , a l n = 10.16 ± 0.87 M_{1,\mathrm{aln}} = 10.16 \pm0.87 M 1 , aln = 10.16 ± 0.87 , with the ablation OSSA-NOW (3.23 ± 0.30 3.23 \pm0.30 3.23 ± 0.30 ) and the classical baseline SC-DEGREE (3.02 ± 0.31 3.02 \pm0.31 3.02 ± 0.31 ) clustering at roughly one third of OSSA’s value. The M 2 , r a w → M 2 , a l n M_{2,\mathrm{raw}} \to M_{2,\mathrm{aln}} M 2 , raw → M 2 , aln shift again shows that high-degree or SC-summary baselines can look competitive in raw coordinates (e.g., COMMUNICABILITY: + 0.672 +0.672 + 0.672 , SC-DEGREE: + 0.652 +0.652 + 0.652 ), whereas OSSA leads after rotation-aware evaluation (+ 0.811 +0.811 + 0.811 vs. next-best + 0.672 +0.672 + 0.672 ). The same conclusion holds on the SC-degree-quartile-matched null gain M 3 , a l n M_{3,\mathrm{aln}} M 3 , aln (+ 0.81 +0.81 + 0.81 vs. next-best + 0.67 +0.67 + 0.67 ). After matching each split’s community labels to the pooled partition by maximum node overlap, OSSA leads on M 1 , a l n M_{1,\mathrm{aln}} M 1 , aln in all three communities. For pooled community sizes (31, 23, 14), its scores are 10.17 ± 0.26 10.17 \pm0.26 10.17 ± 0.26 , 4.32 ± 0.04 4.32 \pm0.04 4.32 ± 0.04 , and 15.98 ± 0.07 15.98 \pm0.07 15.98 ± 0.07 , respectively (mean ± \pm ± s.e. across ten splits), versus highest baseline means of 3.66, 1.11, and 5.00.
Table 12. Cross-visit support replication between the ABCD baseline and Year-2 follow-up releases for canonical κ = 3 \kappa= 3 κ = 3 supports. Results are averaged over 30 (seed, community) units. CVSR denotes the support-set Jaccard overlap between visits. nCVSR is the null-corrected replication score relative to size-matched or SC-degree-quartile-matched random supports.
Cross-visit support replication To evaluate whether the selected structural supports remain stable across longitudinal neurodevelopment, we compare the canonical κ = 3 \kappa= 3 κ = 3 supports identified from the baseline and Year-2 ABCD releases. For each split seed and matched FC community, we compute a cross-visit support replication score
C V S R = ∣ V ^ b a s e ∩ V ^ Y 2 ∣ ∣ V ^ b a s e ∪ V ^ Y 2 ∣ \mathrm{CVSR} = \frac{\lvert\widehat{V}_{\mathrm{base}} \cap\widehat{V}_{\mathrm{Y2}} \rvert}{\lvert\widehat{V}_{\mathrm{base}} \cup\widehat{V}_{\mathrm{Y2}} \rvert} CVSR = ∣ V base ∪ V Y2 ∣ ∣ V base ∩ V Y2 ∣
corresponding to the Jaccard overlap between the baseline and second-visit supports. We additionally report the overlap count, overlap fraction, exact replication rate, and a degree-matched null-corrected replication score (nCVSR). Community labels between visits are aligned by maximum-overlap matching prior to evaluation.
Table 12 shows that OSSA remains highly stable across visits, with CVSR = 0.928 ± 0.033 0.928\pm0.033 0.928 ± 0.033 and mean overlap 2.86/3 nodes. Importantly, this stability is achieved simultaneously with the substantially larger held-out alignment scores reported in Tables 3 and 11. Several graph-summary baselines, including SC-DEGREE, FC-DEGREE, COMMUNICABILITY, and JOINT-SCxFC, also exhibit high cross-visit support consistency, suggesting that portions of the dominant structural organization are preserved longitudinally within FC communities. In contrast, the deep-learning baselines exhibit substantially weaker support replication and near-null corrected stability.
Multi-clique sensitivity (λ \lambda λ -diagnostic). We replay the same K ∈ { 1 , 2 , 3 } K \in\{1,2,3\} K ∈ { 1 , 2 , 3 } and log-spaced λ \lambda λ -sweep at κ = 3 \kappa= 3 κ = 3 on the second-visit cohort over the same 30 (seed, community) units (Figure 13); the summary appears in Section 4 (“Second-visit replication”). The diagnostic returns the same single-core signature as the baseline cohort: at λ ≤ 10 2 \lambda\le10^2 λ ≤ 1 0 2 the K = 2 K = 2 K = 2 and K = 3 K = 3 K = 3 fits collapse onto a single dominant support (mean pairwise Jaccard ≥ 0.98 \ge0.98 ≥ 0.98 , normalised union ≤ 1.03 \le1.03 ≤ 1.03 ); at λ ∈ [ 10 3 , 10 4 ] \lambda\in[10^3, 10^4] λ ∈ [ 1 0 3 , 1 0 4 ] a sharp transition forces them into geometric expansion of the union (K = 2 K = 2 K = 2 : 1.0 → \to → 2.0; K = 3 K = 3 K = 3 : 1.0 → \to → 2.97), with no intermediate λ \lambda λ yielding stable partial separation.
Compute resources
All experiments were run on a high-performance computing cluster. CPU jobs used Intel Xeon 6342 processors, with 4 CPU cores and 16 GB of RAM allocated per job (4 GB per core). GPU resources were used only for the deep-learning baselines, which ran on an RTX 8000 GPU. Runtime was measured from loading the preprocessed SC/FC matrices to saving the final metrics and figures. Raw MRI preprocessing is excluded. Table 13 reports peak memory usage (GB) and wall-clock time (minutes) for the main experiment groups.
Table 13. Compute resources for the main reported experiments.
Limitations and broader impact.
Our theory establishes local statistical guarantees for canonical OSSA, including the existence of an empirical local maximizer near the population target. Note that the implemented block ascent method is a finite multi-restart local solver, and we do not claim that its output lies in the specified neighborhood. Extending guarantees to the multi-support objective is future work. Empirically, the results are limited to the Desikan–Killiany atlas, ABCD, predefined FC communities, and small support budgets, so the anatomical supports should be treated as cohort- and pipeline-dependent hypotheses until replicated across parcellations, acquisition protocols, and clinical populations. OSSA may support more interpretable studies of brain development and disease-related network organization, but connectome-derived supports should not be used for individual diagnosis, screening, or group profiling without external validation and uncertainty reporting.
The community-wise formulation can also be applied to predefined overlapping functional communities. Each community would retain its own alignment and support parameters, so the same objective could be fitted independently within each community, with a shared region eligible for selection in more than one. However, support selections across communities would remain uncoupled, and an SC edge included in multiple community subproblems could contribute fully to each corresponding objective. Such independent fits therefore do not describe how a shared region’s structural role is distributed across its functional memberships. Whether the relevant biological structure is best described by independent community-specific cores or by a decomposition of shared structural roles across systems remains an open question that the current formulation cannot resolve. Jointly modeling these shared roles is a direction for future work.
ABCD data use and ethics. The ABCD data were obtained through the official ABCD data access mechanism and used in accordance with the applicable data-use agreement. ABCD participants were enrolled under the study’s institutional review and consent/assent procedures, and our analysis used de-identified connectome-derived data only. We do not attempt individual identification and do not release subject-level neuroimaging data.
Figure 13. ABCD second-visit multi-clique λ \lambda λ -sensitivity on a log-spaced grid (mean ± \pm ± s.e. over 30 (seed, community) units; x x x -axis on a symmetric-log scale to display λ = 0 \lambda= 0 λ = 0 ). Panels show: (a) Validation J J J evaluated on the union of supports; (b) Mean pairwise Jaccard (1 = full collapse); (c) Mean pairwise overlap count (maximum κ = 3 \kappa= 3 κ = 3 ); (d) Normalised union size ∣ ⋃ ℓ V ( ℓ ) ∣ / κ |\bigcup_{\ell}\mathcal{V}^{(\ell)}|/\kappa ∣ ⋃ ℓ V ( ℓ ) ∣/ κ (1 = full collapse, K K K = full separation); (e) Training J J J on log scale; (f) Per-community pairwise Jaccard at K = 2 K = 2 K = 2 . The single-core verdict (collapse at small λ \lambda λ , no per-node yield gain at large λ \lambda λ ) holds in every community, replicating the baseline-cohort conclusion.