Introduction
We consider the following nonlinear eigenvalue problem with eigenvector dependency (NEPv): find a matrix X ∈ C n , k X \in\mathbb{C}^{n,k} X ∈ C n , k with orthonormal columns (i.e., X H X = I k X^{H}X=I_k X H X = I k ) and a square matrix Λ ∈ C k , k \Lambda\in\mathbb{C}^{k,k} Λ ∈ C k , k satisfying
H ( X ) X = X Λ , (1) H(X)X=X\Lambda, \tag*{(1)} H ( X ) X = X Λ , (1)
where H : C n , k → C n , n H:\mathbb{C}^{n,k}\to\mathbb{C}^{n,n} H : C n , k → C n , n is a given Hermitian matrix-valued function. Here, the eigenvalues of Λ ≡ X H H ( X ) X \Lambda\equiv X^{H}H(X)X Λ ≡ X H H ( X ) X correspond to a subset of k k k eigenvalues of H ( X ) H(X) H ( X ) . We assume that they are the k k k smallest throughout the paper. The largest or those at other prescribed positions can be treated analogously. Typically, k ≪ n k \ll n k ≪ n . In addition, we assume that H H H is right unitarily invariant , i.e.,
H ( X ) = H ( X Q ) , for all Q ∈ C k , k with Q H Q = I k . (2) H(X)=H(XQ), \qquad\text{for all } Q \in\mathbb{C}^{k,k} \text{ with } Q^{H}Q=I_k. \tag*{(2)} H ( X ) = H ( X Q ) , for all Q ∈ C k , k with Q H Q = I k . (2)
This implies that any solution ( X , Λ ) (X,\Lambda) ( X , Λ ) would give rise to an equivalent class of solution ( X Q , Q H Λ Q ) (XQ,Q^{H}\Lambda Q) ( X Q , Q H Λ Q ) . Therefore, a solution X X X is intrinsically the subspace range ( X ) \operatorname{range}(X) range ( X ) .
NEPv (1) arises in a wide range of applications. They have long played important roles in quantum physics and chemistry through the Hartree–Fock and Kohn–Sham equations [10 , 16 , 19 , 21 , 39 , 55 ] . More recently, they have attracted growing interest in machine learning, with applications including sparse PCA, trace ratio optimization, and Rayleigh quotient optimization; see, e.g., [9 , 14 , 53 , 70 , 71 , 75 , 76 , 77 ] . The widespread use of NEPv stems from their fundamental role as first-order optimality conditions for optimization with orthogonality constraints, and the invariance condition (2) reflects that the solution sought is a subspace rather than a particular basis in those applications; see, e.g., [48 ] .
A standard approach to solving (1) is the self-consistent field (SCF) iteration. Starting from an initial matrix X 0 X_0 X 0 with orthonormal columns, SCF repeatedly solves the linear eigenvalue problem
H ( X i ) X i + 1 = X i + 1 Λ i + 1 , i = 0 , 1 , 2 , … , (3) H(X_i)X_{i+1}=X_{i+1}\Lambda_{i+1}, \qquad i=0,1,2,\ldots, \tag*{(3)} H ( X i ) X i + 1 = X i + 1 Λ i + 1 , i = 0 , 1 , 2 , … , (3)
where the columns of X i + 1 X_{i+1} X i + 1 are orthonormal eigenvectors corresponding to the k k k smallest eigenvalues of H ( X i ) H(X_i) H ( X i ) , and Λ i + 1 \Lambda_{i+1} Λ i + 1 is Hermitian but need not be diagonal. We note that the iterate matrix X i + 1 X_{i+1} X i + 1 is generally not unique, with different choices related by an orthonormal rotation X i + 1 Q X_{i+1}Q X i + 1 Q , provided that the k k k smallest eigenvalues are separated from the rest of the spectrum. By the unitary invariance (2), these choices give the same H ( X i + 1 ) H(X_{i+1}) H ( X i + 1 ) and thus do not affect the subsequent iterations. Hence, the SCF (3) is an iteration on subspaces { range ( X i ) } i = 0 ∞ \{\operatorname{range}(X_i)\}_{i=0}^{\infty} { range ( X i ) } i = 0 ∞ , with each X i X_i X i serving as a representative orthonormal basis.
The SCF iteration was originally developed for electronic structure calculations [33 , 60 ] . Under suitable assumptions, local convergence can be established, typically at a linear rate [7 , 17 , 51 , 68 , 74 ] . In practice, slow convergence or failure to converge may occur and has motivated various techniques to stabilize and accelerate SCF, such as damping, level shifting, and mixing of iterates [20 , 45 , 58 , 59 , 64 , 66 ] . However, many of these techniques have been developed for specific computational and physical applications, such as density functional theory, where they exploit particular functional structures of H ( X ) H(X) H ( X ) , and they do not readily apply to general NEPv (1) in a computationally efficient way.
The purpose of this paper is to investigate acceleration techniques of the SCF iteration (3) for unitarily invariant NEPv (1) in its most general form. We focus on two types of acceleration: Anderson acceleration (AA), which combines recent iterates, and Newton acceleration, which uses derivative information of H ( X ) H(X) H ( X ) to achieve superlinear acceleration.
AA is a widely used technique for accelerating fixed-point iterations [5 ] . The basic idea is to form a refined approximation through a linear combination (or mixing) of recent iterates, using suitably chosen coefficients; see, e.g., [6 , 26 , 27 , 67 , 69 ] for details. Applying AA to the SCF (3) requires extra care because the iterates X i X_i X i are not uniquely determined, and directly mixing them depends on the arbitrary unitary rotations X i Q X_iQ X i Q . In electronic structure calculations, AA is closely related to Pulay mixing, also known as direct inversion in the iterative subspace (DIIS) [58 , 59 ] . For these specialized NEPv, the SCF can be expressed in terms of quantities such as the charge density diag ( X X H ) \operatorname{diag}(XX^{H}) diag ( X X H ) , density matrix X X H XX^{H} X X H , or Fock matrix H ( X ) H(X) H ( X ) , which are independent of the chosen basis; see, e.g., [30 , 36 , 46 , 59 ] . For example, for the Kohn–Sham NEPv that arises in density functional theory, where H ( X ) H(X) H ( X ) is fully determined by the charge density ρ ( X ) = diag ( X X H ) ∈ R n \rho(X)=\operatorname{diag}(XX^{H}) \in\mathbb{R}^{n} ρ ( X ) = diag ( X X H ) ∈ R n , the SCF can be recast as a fixed-point iteration ρ i + 1 = g ( ρ i ) \rho_{i+1}=g(\rho_i) ρ i + 1 = g ( ρ i ) in charge densities, and AA can then be applied directly to this iteration; see, e.g., [63 ] . However, for general NEPv (1) such a compact density-based representation of H ( X ) H(X) H ( X ) may not be readily available, while mixing the full matrices H ( X i ) ∈ C n , n H(X_i) \in\mathbb{C}^{n,n} H ( X i ) ∈ C n , n can be costly for large n n n . This calls for an in-depth investigation of AA in these settings, particularly into how to work economically with tall-skinny basis matrices X i X_i X i .
On the other hand, Newton’s method provides another means of locally accelerating SCF by using derivative information to achieve superlinear convergence under suitable assumptions. For NEPv (1), applying Newton’s acceleration also requires care because the solution basis is not uniquely determined. Most existing Newton-type methods are derived for real-variable NEPv with X ∈ R n , k X \in\mathbb{R}^{n,k} X ∈ R n , k and H ( X ) ∈ R n , n H(X) \in\mathbb{R}^{n,n} H ( X ) ∈ R n , n . A direct approach applies Newton’s method to the equations H ( X ) X − X Λ = 0 H(X)X-X\Lambda=0 H ( X ) X − X Λ = 0 and X T X = I k X^{T}X=I_k X T X = I k ; see, e.g., [28 , 73 ] . However, the unitary invariance (2) implies that a solution ( X , Λ ) (X,\Lambda) ( X , Λ ) is not isolated, since ( X Q , Q T Λ Q ) (XQ,Q^{T}\Lambda Q) ( X Q , Q T Λ Q ) remains a solution for every unitary Q Q Q , which leads to a singular Jacobian (derivative) operator that creates difficulties for standard Newton analysis and numerical solution [73 ] . To avoid this singularity, the approach in [40 ] replaces the orthogonality constraint X T X = I k X^{T}X=I_k X T X = I k by a normalization condition C T X = I k C^{T}X=I_k C T X = I k with a fixed matrix C ∈ R n , k C \in\mathbb{R}^{n,k} C ∈ R n , k . This formulation assumes that the NEPv satisfies H ( X Q ) = H ( X ) H(XQ)=H(X) H ( X Q ) = H ( X ) for every nonsingular Q ∈ R k , k Q \in\mathbb{R}^{k,k} Q ∈ R k , k , which is stronger than the unitary invariance (2). Along a different line, Riemannian Newton methods on the Grassmann manifold have been developed for NEPv arising from energy minimization, which removes the basis non-uniqueness by working with subspaces; see, e.g., [3 , 78 ] . These derivations, however, rely on an underlying energy functional and differential-geometric tools. To our knowledge, a Newton acceleration for general NEPv (1), based on an elementary derivation and a correction operator that is nonsingular under suitable assumptions, has yet to be developed.
Contributions. The main contributions of this work are threefold:
For Anderson acceleration, we present three formulations that resolve the basis non-uniqueness of SCF iteration: (i) a parameterization-based framework that exploits the structure of H ( X ) H(X) H ( X ) , (ii) an alignment-based AA, and (iii) an adaptation of Riemannian AA. The first extends the density-based approach to general NEPv, while the latter two work with n × k n \times k n × k basis matrices without requiring a parameterization of H ( X ) H(X) H ( X ) . The regularity properties of the associated SCF maps are established.
For Newton acceleration, we introduce the notion of a basis-aligned update to characterize local corrections to an approximate solution of the NEPv. This naturally removes basis non-uniqueness and leads to a Newton equation for correction through elementary linear algebra operations. It also provides a unified treatment to real and complex NEPv. Under suitable assumptions, we establish the nonsingularity of the correction operator and local quadratic convergence.
Organization. The rest of the paper is organized as follows. Section 2 reviews Anderson acceleration and presents three variants for SCF, including parameterization-based, alignment-based, and Riemannian formulations of AA. Section 3 derives the basis-aligned Newton correction, establishes its local quadratic convergence, and discusses its implementation. Section 4 presents numerical experiments on problems from computational physics and data science. Concluding remarks and future directions are given in Section 5.
Notation. Throughout this paper, we use standard notation from matrix analysis. We denote by R n , k \mathbb{R}^{n,k} R n , k and C n , k \mathbb{C}^{n,k} C n , k the spaces of real and complex n × k n \times k n × k matrices, respectively, with R n = R n , 1 \mathbb{R}^{n}=\mathbb{R}^{n,1} R n = R n , 1 and C n = C n , 1 \mathbb{C}^{n}=\mathbb{C}^{n,1} C n = C n , 1 . The set of complex orthonormal matrices is denoted by U n , k : = { X ∈ C n , k : X H X = I k } \mathbb{U}_{n,k}:=\{X \in\mathbb{C}^{n,k}: X^{H}X=I_k\} U n , k := { X ∈ C n , k : X H X = I k } . The Grassmann manifold of k k k -dimensional subspaces of C n \mathbb{C}^{n} C n (or R n \mathbb{R}^{n} R n in the real case) is denoted by G ( n , k ) \mathcal{G}(n,k) G ( n , k ) . For a matrix A A A , A T A^{T} A T and A H A^{H} A H denote its transpose and conjugate transpose, respectively, range ( A ) \operatorname{range}(A) range ( A ) denotes its column space, and vec ( A ) \operatorname{vec}(A) vec ( A ) denotes the vector obtained by stacking the columns of A A A . For square A A A , tr ( A ) \operatorname{tr}(A) tr ( A ) denotes its trace. The identity matrix of size n n n is denoted by I n I_n I n , with the subscript omitted when its size is clear. We use diag ( A ) \operatorname{diag}(A) diag ( A ) for the vector of diagonal entries of A A A and Diag ( ν ) \operatorname{Diag}(\nu) Diag ( ν ) for the diagonal matrix with diagonal vector ν \nu ν . For a Hermitian A ∈ C n , n A \in\mathbb{C}^{n,n} A ∈ C n , n , its eigenvalues are ordered as λ 1 ( A ) ≤ ⋯ ≤ λ n ( A ) \lambda_1(A) \leq\cdots\leq\lambda_n(A) λ 1 ( A ) ≤ ⋯ ≤ λ n ( A ) . For a block matrix A = [ A 1 , … , A m ] \mathcal{A}=[A_1,\ldots,A_m] A = [ A 1 , … , A m ] , and a vector β = ( β 1 , … , β m ) T ∈ R m \beta=(\beta_1,\ldots,\beta_m)^T \in\mathbb{R}^{m} β = ( β 1 , … , β m ) T ∈ R m , we define the block product A ⊙ β : = ∑ j = 1 m β j A j \mathcal{A}\odot\beta:=\sum_{j=1}^{m}\beta_jA_j A ⊙ β := ∑ j = 1 m β j A j . Unless otherwise stated, ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ denotes the spectral norm for matrices and ∥ ⋅ ∥ F \|\cdot\|_{F} ∥ ⋅ ∥ F denotes the Frobenius norm. For complex matrices, we use the (real) Frobenius inner product ⟨ A , B ⟩ : = Re ( tr ( A H B ) ) \langle A,B\rangle:= \operatorname{Re}(\operatorname{tr}(A^{H}B)) ⟨ A , B ⟩ := Re ( tr ( A H B )) . Differentiability of functions with complex variables is understood with respect to the real and imaginary parts of their entries, and we write D F ( X ) [ E ] DF(X)[E] D F ( X ) [ E ] for the Fréchet derivative of F F F at X X X along the direction E E E . We use the standard big-O O O and little-o o o notation: f = O ( g ) f = O(g) f = O ( g ) means ∣ f ∣ ≤ C ∣ g ∣ |f| \le C|g| ∣ f ∣ ≤ C ∣ g ∣ for some constant C C C as g → 0 g \to0 g → 0 , and f = o ( g ) f = o(g) f = o ( g ) means ∣ f ∣ / ∣ g ∣ → 0 |f|/|g| \to0 ∣ f ∣/∣ g ∣ → 0 . Other notations will be explained as needed.
Anderson Acceleration for NEPv
We consider Anderson Acceleration (AA) of the SCF iteration (3) . Recall that applying AA to SCF requires care because of the unitary invariance (2) of the NEPv. Indeed, each iterate X i + 1 X_{i+1} X i + 1 by the SCF (3) is not uniquely defined: For any unitary matrix Q ∈ U k , k Q \in\mathbb{U}^{k,k} Q ∈ U k , k , the matrix X i + 1 ← X i + 1 Q X_{i+1} \leftarrow X_{i+1}Q X i + 1 ← X i + 1 Q is also a valid solution. Thus, at the level of basis matrices, SCF is a set-valued fixed-point iteration
X i + 1 ∈ g ( X i ) , (4) X_{i+1} \in g(X_i), \tag*{(4)} X i + 1 ∈ g ( X i ) , (4)
where
g ( X ) : = { Y : Y ∈ U n , k is an orthonormal eigenbasis for k smallest eigenvalues of H ( X ) } . (5) g(X) := \{Y : Y \in\mathbb{U}^{n,k}\text{ is an orthonormal eigenbasis for }k\text{ smallest eigenvalues of }H(X)\}. \tag*{(5)} g ( X ) := { Y : Y ∈ U n , k is an orthonormal eigenbasis for k smallest eigenvalues of H ( X )} . (5)
Consequently, the fixed-point residual r ( X ) = g ( X ) − X r(X) = g(X) - X r ( X ) = g ( X ) − X , as used in AA, is not well defined, since it depends on the particular choice of Y ∈ g ( X ) Y \in g(X) Y ∈ g ( X ) and need not vanish even at a true solution X ∗ X^* X ∗ of the NEPv (1) . In this section, we resolve this ambiguity. After a brief review of AA for the fixed-point iteration, we will present three approaches, including a parameterization-based AA framework that exploits the functional structure of the NEPv for computational efficiency, an alignment-based AA that works directly with basis matrices, and a Riemannian AA that uses geometric tools on the Grassmann manifold.
Anderson Acceleration for Fixed-Point Iterations
In this section, we briefly review AA for standard fixed-point iterations; further details on the method and its convergence properties are available in, e.g., [5 , 6 , 26 , 27 , 29 , 67 , 69 ] . Consider the fixed-point equation
x = g ( x ) , (6) x = g(x), \tag*{(6)} x = g ( x ) , (6)
where g : R n → R n g : \mathbb{R}^{n} \to\mathbb{R}^{n} g : R n → R n is continuous. Given an initial x 0 x_0 x 0 , the corresponding fixed-point iteration is
x i + 1 = g ( x i ) , i = 0 , 1 , … (7) x_{i+1} = g(x_i), \qquad i = 0,1,\ldots \tag*{(7)} x i + 1 = g ( x i ) , i = 0 , 1 , … (7)
If the iteration converges, its limit x ∗ : = lim i → ∞ x i x^* := \lim_{i\to\infty} x_i x ∗ := lim i → ∞ x i satisfies (6) . Convergence, however, is not guaranteed and depends on both the mapping g g g and the initial approximation x 0 x_0 x 0 . For initial x 0 x_0 x 0 sufficiently close to a fixed point x ∗ x^* x ∗ , convergence is ensured if g g g is continuously differentiable near x ∗ x^* x ∗ and the spectral radius of the Jacobian matrix g ′ ( x ∗ ) g'(x^*) g ′ ( x ∗ ) (largest absolute value of its eigenvalues) is strictly less than one; see, e.g., [44 ] . In such cases, the convergence is generally linear and can be slow when this spectral radius is close to one.
AA seeks to improve the local convergence of fixed-point iteration by mixing recent iterates [5 ] . Specifically, AA(m m m ) scheme uses the m + 1 m+1 m + 1 most recent iterates x i , … , x i − m x_i,\ldots,x_{i-m} x i , … , x i − m to construct
x i + 1 : = ∑ ℓ = i − m i α ℓ ⋅ g ( x ℓ ) , (8) x_{i+1} := \sum_{\ell=i-m}^{i} \alpha_{\ell}\cdot g(x_{\ell}), \tag*{(8)} x i + 1 := ℓ = i − m ∑ i α ℓ ⋅ g ( x ℓ ) , (8)
where the coefficients { α ℓ } \{\alpha_{\ell}\} { α ℓ } are chosen to minimize the norm of a linear combination of the corresponding residuals:
min ∑ ℓ = i − m i α ℓ = 1 ∥ ∑ ℓ = i − m i α ℓ ⋅ r ( x ℓ ) ∥ with r ( x ) : = g ( x ) − x . (9) \min_{\sum_{\ell=i-m}^{i}\alpha_{\ell}=1}\left\lVert\sum_{\ell=i-m}^{i}\alpha_{\ell}\cdot r(x_{\ell})\right\rVert
\qquad\text{with}\qquad r(x) := g(x)-x. \tag*{(9)} ∑ ℓ = i − m i α ℓ = 1 min ℓ = i − m ∑ i α ℓ ⋅ r ( x ℓ ) with r ( x ) := g ( x ) − x . (9)
The motivation for (9) follows from a local linearization of the residual. If { x ℓ } \{x_{\ell}\} { x ℓ } are sufficiently close to x i x_i x i , and the coefficients { α ℓ } \{\alpha_{\ell}\} { α ℓ } with ∑ ℓ = i − m i α ℓ = 1 \sum_{\ell=i-m}^{i}\alpha_{\ell}=1 ∑ ℓ = i − m i α ℓ = 1 are bounded absolutely by some constant (independent of { x ℓ } \{x_\ell\} { x ℓ } ), then the first-order Taylor’s expansion about x i x_i x i gives
r ( ∑ ℓ = i − m i α ℓ x ℓ ) = ∑ ℓ = i − m i α ℓ ⋅ r ( x ℓ ) + o ( max ℓ = i − m : i − 1 ∥ x ℓ − x i ∥ ) . (10) r\left(\sum_{\ell=i-m}^{i}\alpha_\ell x_\ell\right)=\sum_{\ell=i-m}^{i}\alpha_\ell\cdot r(x_\ell)+o\left(\max_{\ell=i-m:i-1}\left\|x_\ell-x_i\right\|\right). \tag*{(10)} r ( ℓ = i − m ∑ i α ℓ x ℓ ) = ℓ = i − m ∑ i α ℓ ⋅ r ( x ℓ ) + o ( ℓ = i − m : i − 1 max ∥ x ℓ − x i ∥ ) . (10)
Thus, the least-squares problem (9) approximately minimizes the residual norm of the mixed approximation x i + 1 ′ : = ∑ ℓ = i − m i α ℓ x ℓ x'_{i+1}:=\sum_{\ell=i-m}^{i}\alpha_\ell x_\ell x i + 1 ′ := ∑ ℓ = i − m i α ℓ x ℓ . The update (8) then replaces each x ℓ x_\ell x ℓ by its fixed-point image g ( x ℓ ) g(x_\ell) g ( x ℓ ) , incorporating a further fixed-point correction into the mixed approximation. In practice, one may also damp the update (8) by setting x i + 1 ← ( 1 − γ ) x i + 1 ′ + γ x i + 1 x_{i+1}\leftarrow(1-\gamma)x'_{i+1}+\gamma x_{i+1} x i + 1 ← ( 1 − γ ) x i + 1 ′ + γ x i + 1 with a damping parameter γ ∈ [ 0 , 1 ] \gamma\in[0,1] γ ∈ [ 0 , 1 ] ; see, e.g., [63 ] . For simplicity of exposition, we take γ = 1 \gamma=1 γ = 1 (no damping) throughout this paper.
In implementation, the constraint ∑ ℓ = i − m i α ℓ = 1 \sum_{\ell=i-m}^{i}\alpha_\ell=1 ∑ ℓ = i − m i α ℓ = 1 on the mixing coefficients in the least squares (9) can be eliminated by expressing AA( m ) (m) ( m ) in an equivalent difference form; see, e.g., [27 ] . Specifically, the update (8) becomes
x i + 1 = g ( x i ) − ∑ ℓ = i − m i − 1 β ℓ ( g ( x ℓ + 1 ) − g ( x ℓ ) ) , (11) x_{i+1}=g(x_i)-\sum_{\ell=i-m}^{i-1}\beta_\ell\bigl(g(x_{\ell+1})-g(x_\ell)\bigr), \tag*{(11)} x i + 1 = g ( x i ) − ℓ = i − m ∑ i − 1 β ℓ ( g ( x ℓ + 1 ) − g ( x ℓ ) ) , (11)
where the coefficients { β ℓ } \{\beta_\ell\} { β ℓ } solve the unconstrained least-squares problem
min β ∥ r ( x i ) − ∑ ℓ = i − m i − 1 β ℓ ( r ( x ℓ + 1 ) − r ( x ℓ ) ) ∥ . (12) \min_{\beta}\left\|r(x_i)-\sum_{\ell=i-m}^{i-1}\beta_\ell\bigl(r(x_{\ell+1})-r(x_\ell)\bigr)\right\|. \tag*{(12)} β min r ( x i ) − ℓ = i − m ∑ i − 1 β ℓ ( r ( x ℓ + 1 ) − r ( x ℓ ) ) . (12)
The equivalence between (10) and (8) follows from the one-to-one correspondence α i − m = β i − m \alpha_{i-m}=\beta_{i-m} α i − m = β i − m , α ℓ = β ℓ − β ℓ − 1 \alpha_\ell=\beta_\ell-\beta_{\ell-1} α ℓ = β ℓ − β ℓ − 1 for i − m + 1 ≤ ℓ ≤ i − 1 i-m+1\le\ell\le i-1 i − m + 1 ≤ ℓ ≤ i − 1 , and α i = 1 − β i − 1 \alpha_i=1-\beta_{i-1} α i = 1 − β i − 1 . The standard least-squares problem (12) can then be solved by direct QR factorization or iterative methods such as LSQR; see, e.g., [15 , 32 ] .
Table 1.
Algorithm 1 summarizes AA( m ) (m) ( m ) in difference form, where we apply AA from the first iteration using the available history length m i = min { m , i } m_i=\min\{m,i\} m i = min { m , i } . Throughout this paper, we use a prescribed, fixed window size m m m . For greater flexibility, one may also consider adaptive truncation [20 ] or switching between Anderson mixing and fixed-point steps [12 , 54 ] . We stop the algorithm when the fixed-point residual norm is below an error tolerance τ \tau τ .
Parameterization-based Anderson Acceleration
In this section, we describe a general framework for applying AA to SCF through a parameterization of the NEPv (1) that is independent of the chosen orthonormal basis.
Unitary-Invariant Parameterization
Our development is based on the notion of unitarily-invariant parameterization of the NEPv (1) given below.
Definition 1 (ui–parameterization). We call ρ : C n , k → C p \rho:\mathbb{C}^{n,k}\to\mathbb{C}^{p} ρ : C n , k → C p a unitarily-invariant parameterization of the NEPv (1), if
ρ ( X Q ) ≡ ρ ( X ) , for all X ∈ U n , k and Q ∈ U k , k , (13) \rho(XQ)\equiv\rho(X),\qquad\text{for all }X\in\mathbb{U}^{n,k}\text{ and }Q\in\mathbb{U}^{k,k}, \tag*{(13)} ρ ( X Q ) ≡ ρ ( X ) , for all X ∈ U n , k and Q ∈ U k , k , (13) and there exists a Hermitian matrix-valued function H ^ : C p → C n , n \widehat{H}:\mathbb{C}^{p}\to\mathbb{C}^{n,n} H : C p → C n , n such that
H ( X ) = H ^ ( ρ ( X ) ) , for all X ∈ U n , k . (14) H(X)=\widehat{H}(\rho(X)),\qquad\text{for all }X\in\mathbb{U}^{n,k}. \tag*{(14)} H ( X ) = H ( ρ ( X )) , for all X ∈ U n , k . (14)
There is always a ui-parameterization of the NEPv (1), although it is generally not unique. For example, since the Hermitian matrix H ( X ) H(X) H ( X ) is completely defined by its lower triangular entries (including the diagonal), a trivial ui-parameterization is ρ ( X ) : = tril ( H ( X ) ) ∈ C p \rho(X):=\operatorname{tril}(H(X))\in\mathbb{C}^{p} ρ ( X ) := tril ( H ( X )) ∈ C p with p = n ( n + 1 ) 2 p=\frac{n(n+1)}{2} p = 2 n ( n + 1 ) , and H ^ ( ⋅ ) \widehat{H}(\cdot) H ( ⋅ ) reconstructs the full matrix H ( X ) H(X) H ( X ) from its lower triangular part. In practice, since H ( ⋅ ) H(\cdot) H ( ⋅ ) has a structure such as sparsity or other functional structure, one may construct a much more compact ui-parameterization with p ≪ n 2 p\ll n^{2} p ≪ n 2 or even p ≪ n p\ll n p ≪ n as shown in the following examples.
Example 1. Here are three practically relevant examples of ui-parameterization of NEPv.
Sparsity: Suppose that H ( X ) = A + B ( X ) H(X)=A+B(X) H ( X ) = A + B ( X ) , where A A A is a constant matrix and B ( X ) B(X) B ( X ) is a sparse Hermitian matrix with a fixed sparsity pattern Π \Pi Π with p p p non-zero entries in the upper (or lower) triangle. Then, we can define ρ ( X ) ∈ C p \rho(X)\in\mathbb{C}^{p} ρ ( X ) ∈ C p as a collection of the non-zero entries in B ( X ) B(X) B ( X ) , and H ^ \widehat{H} H updates A A A according to the given sparsity pattern Π \Pi Π using the entries of ρ ( X ) \rho(X) ρ ( X ) .
Functional structure through charge density: A Kohn-Sham NEPv from density functional theory [16 , 17 ] involves
H ( X ) = A + Diag ( L † ρ ( X ) ) + Diag ( μ x c ( ρ ( X ) ) T 1 ) , H(X)=A+\operatorname{Diag}(L^{\dagger}\rho(X))+\operatorname{Diag}(\mu_{xc}(\rho(X))^{T}\mathbf{1}), H ( X ) = A + Diag ( L † ρ ( X )) + Diag ( μ x c ( ρ ( X ) ) T 1 ) , where ρ : R n × k → R n \rho:\mathbb{R}^{n\times k}\to\mathbb{R}^{n} ρ : R n × k → R n with ρ ( X ) = diag ( X X T ) \rho(X)=\operatorname{diag}(XX^{T}) ρ ( X ) = diag ( X X T ) is the charge density, μ x c : R n → R n × n \mu_{xc}:\mathbb{R}^{n}\to\mathbb{R}^{n\times n} μ x c : R n → R n × n is a given function accounting for exchange energy and L † L^{\dagger} L † is the pseudo-inverse of a discrete Laplacian L L L . Since the dependence on X X X is entirely through ρ ( X ) \rho(X) ρ ( X ) , we have the ui-parameterization (14) :
H ^ ( ρ ) = A + Diag ( L † ρ ) + Diag ( μ x c ( ρ ) T 1 ) , \widehat{H}(\rho)=A+\operatorname{Diag}(L^{\dagger}\rho)+\operatorname{Diag}(\mu_{xc}(\rho)^{T}\mathbf{1}), H ( ρ ) = A + Diag ( L † ρ ) + Diag ( μ x c ( ρ ) T 1 ) , where ρ ( X ) ∈ R n \rho(X)\in\mathbb{R}^{n} ρ ( X ) ∈ R n has p = n p=n p = n components. Recall that this charge-density parameterization underlies density-based Pulay mixing (DIIS) for SCF; see, e.g., [63 ] .
Functional structure through Rayleigh quotients: Many practical NEPv involve H ( X ) H(X) H ( X ) that depends on X X X only through a small number of Rayleigh quotients tr ( X H M j X ) \operatorname{tr}(X^{H}M_{j}X) tr ( X H M j X ) , where M j ∈ C n × n M_{j}\in\mathbb{C}^{n\times n} M j ∈ C n × n are Hermitian matrices; see e.g. [8 , 14 , 53 ] . In these cases, a ui-parameterization is given by ρ ( X ) : = [ ρ 1 ( X ) , … , ρ p ( X ) ] T \rho(X):=[\rho_{1}(X),\ldots,\rho_{p}(X)]^{T} ρ ( X ) := [ ρ 1 ( X ) , … , ρ p ( X ) ] T , where ρ j ( X ) : = tr ( X H M j X ) \rho_{j}(X):=\operatorname{tr}(X^{H}M_{j}X) ρ j ( X ) := tr ( X H M j X ) , with H ( X ) = H ^ ( ρ ( X ) ) H(X)=\widehat{H}(\rho(X)) H ( X ) = H ( ρ ( X )) for some H ^ : R p → C n × n \widehat{H}:\mathbb{R}^{p}\to\mathbb{C}^{n\times n} H : R p → C n × n . As a representative example, consider the sum-of-trace-ratio NEPv [48 ] , where
H ( X ) = 1 ρ 2 ( X ) ⋅ M 1 − ρ 1 ( X ) ρ 2 ( X ) 2 ⋅ M 2 + M 3 , H(X)=\frac{1}{\rho_{2}(X)}\cdot M_{1}-\frac{\rho_{1}(X)}{\rho_{2}(X)^{2}}\cdot M_{2}+M_{3}, H ( X ) = ρ 2 ( X ) 1 ⋅ M 1 − ρ 2 ( X ) 2 ρ 1 ( X ) ⋅ M 2 + M 3 , with the ui-parameterization given by ρ ( X ) = [ ρ 1 ( X ) , ρ 2 ( X ) ] T ∈ R p \rho(X)=[\rho_{1}(X),\rho_{2}(X)]^{T}\in\mathbb{R}^{p} ρ ( X ) = [ ρ 1 ( X ) , ρ 2 ( X ) ] T ∈ R p with p = 2 p=2 p = 2 , and
H ^ ( ρ ) = 1 ρ 2 ⋅ M 1 − ρ 1 ρ 2 2 ⋅ M 2 + M 3 . \widehat{H}(\rho)=\frac{1}{\rho_{2}}\cdot M_{1}-\frac{\rho_{1}}{\rho_{2}^{2}}\cdot M_{2}+M_{3}. H ( ρ ) = ρ 2 1 ⋅ M 1 − ρ 2 2 ρ 1 ⋅ M 2 + M 3 .
SCF in Parameterized Form
Based on a ui-parameterization ρ \rho ρ of the NEPv, the SCF (3) can be recast as an iteration in terms of the parameters ρ i : = ρ ( X i ) \rho_{i}:=\rho(X_{i}) ρ i := ρ ( X i ) . Given an initial ρ 0 = ρ ( X 0 ) \rho_{0}=\rho(X_{0}) ρ 0 = ρ ( X 0 ) , compute iteratively
ρ i + 1 = ρ ( X i + 1 ) with H ^ ( ρ i ) X i + 1 = X i + 1 Λ i + 1 for i = 0 , 1 , … , (15) \rho_{i+1}=\rho(X_{i+1})\quad\text{with}\quad\widehat{H}(\rho_{i})X_{i+1}=X_{i+1}\Lambda_{i+1}\quad\text{for }i=0,1,\ldots, \tag*{(15)} ρ i + 1 = ρ ( X i + 1 ) with H ( ρ i ) X i + 1 = X i + 1 Λ i + 1 for i = 0 , 1 , … , (15)
where X i + 1 X_{i+1} X i + 1 contains the k k k eigenvectors of H ^ ( ρ i ) ≡ H ( X i ) \widehat{H}(\rho_i) \equiv H(X_i) H ( ρ i ) ≡ H ( X i ) corresponding to the k k k smallest eigenvalues. In the form of fixed-point iteration, we can write (15) as
ρ i + 1 = g ( ρ i ) , (16) \rho_{i+1}=g(\rho_i), \tag*{(16)} ρ i + 1 = g ( ρ i ) , (16)
with the fixed-point mapping g : C p → C p g:\mathbb{C}^{p}\to\mathbb{C}^{p} g : C p → C p defined as
g ( y ) : = { ρ ( Y ) : Y ∈ U n , k is an eigenbasis of the k smallest eigenvalues of H ^ ( y ) } . (17) g(y):=\{\rho(Y):Y\in\mathbb{U}^{n,k}\text{ is an eigenbasis of the }k\text{ smallest eigenvalues of }\widehat{H}(y)\}. \tag*{(17)} g ( y ) := { ρ ( Y ) : Y ∈ U n , k is an eigenbasis of the k smallest eigenvalues of H ( y )} . (17)
Note that g ( y ) g(y) g ( y ) may have multiple values when the k k k -dimensional eigenspace associated with the k k k smallest eigenvalues is not uniquely determined. Such ambiguity, however, does not occur under the eigengap condition λ k < λ k + 1 \lambda_k<\lambda_{k+1} λ k < λ k + 1 for the matrix H ^ ( y ) \widehat{H}(y) H ( y ) . The following lemma formalizes the well-definedness and local differentiability of the parameter-space fixed-point mapping g ( y ) g(y) g ( y ) under this condition.
Lemma 1. Let ρ \rho ρ be a u i ui u i -parameterization of the NEPv (1), with associated matrix-valued function H ^ \widehat{H} H satisfying (12). Suppose that, at y ∈ C p y\in\mathbb{C}^{p} y ∈ C p , the k k k smallest eigenvalues of H ^ ( y ) \widehat{H}(y) H ( y ) are separated from the rest of the spectrum, i.e., λ k ( H ^ ( y ) ) < λ k + 1 ( H ^ ( y ) ) \lambda_k(\widehat{H}(y))<\lambda_{k+1}(\widehat{H}(y)) λ k ( H ( y )) < λ k + 1 ( H ( y )) , and Y ∈ U n , k Y\in\mathbb{U}^{n,k} Y ∈ U n , k is a corresponding eigenbasis. Then
(i) the fixed-point mapping g g g in (15) is single-valued at y y y (i.e., g ( y ) g(y) g ( y ) is uniquely defined);
(ii) the mapping g g g is locally continuous (and differentiable) at y y y , if ρ \rho ρ and H ^ \widehat{H} H are continuous (and differentiable) at Y Y Y and y y y , respectively, both in terms of the real and imaginary parts of their arguments.
Proof. For item (i): The eigengap condition implies that the invariant subspace associated with the k k k smallest eigenvalues of H ^ ( y ) \widehat{H}(y) H ( y ) is unique (see, e.g., [32 ] ). Hence, any two orthonormal bases of this subspace differ only by a right unitary factor. By the unitary invariance of ρ \rho ρ , the value ρ ( X ) \rho(X) ρ ( X ) is independent of the choice of such a basis, and therefore, g ( y ) g(y) g ( y ) is single-valued.
For item (ii): If H ^ \widehat{H} H is continuous (and differentiable), then the entries of the Hermitian matrix H ^ ( y ) \widehat{H}(y) H ( y ) are continuous (and differentiable) functions of the real and imaginary parts of y y y . By classical eigenvalue perturbation theory for Hermitian matrices and the gap condition, there is, locally around y y y , a choice of orthonormal eigenbasis Y ( y ) Y(y) Y ( y ) for the k k k smallest eigenvalues that is continuous (and differentiable); see, e.g., [43 Chap 2.5] . Since ρ \rho ρ is also continuous (and differentiable) by assumption, the composition g ( y ) = ρ ( Y ( y ) ) g(y)=\rho(Y(y)) g ( y ) = ρ ( Y ( y )) is locally continuous (and differentiable).
Conditions for the local convergence of SCF have been established in [7 , 17 , 51 ] . Under these conditions, the fixed point map g g g in (15) is locally contractive. The regularity condition in Lemma 1, together with existing local convergence analyses for AA (e.g., [26 , 67 , 69 ] ), provides a basis for establishing the local convergence of Anderson accelerated SCF (14).
Anderson Acceleration in Parameter Space
By Lemma 1, the parameterized SCF iteration (14) produces a uniquely defined sequence { ρ i } \{\rho_i\} { ρ i } , provided that λ k ( H ^ ( ρ i ) ) < λ k + 1 ( H ^ ( ρ i ) ) \lambda_k(\widehat{H}(\rho_i))<\lambda_{k+1}(\widehat{H}(\rho_i)) λ k ( H ( ρ i )) < λ k + 1 ( H ( ρ i )) at each step. This removes the ambiguity associated with the choice of eigenbasis in (3) and allows AA to be applied directly in parameter space. The resulting adaptation of AA(m m m ) in Algorithm 1 is summarized in Algorithm 2.
We caution that the least squares problem in line 12 of Algorithm 2 may involve complex-valued r i r_i r i and Δ R i \Delta R_i Δ R i . In this case, since the coefficients β ( i ) \beta^{(i)} β ( i ) are restricted to be real (as specified in the algorithm), the complex least-squares problem can be equivalently recast as a real least-squares problem by separating the real and imaginary parts of both the residual and the difference matrix. Specifically, minimizing ∥ r i − Δ R i β ∥ 2 \lVert r_i-\Delta R_i\beta\rVert_2 ∥ r i − Δ R i β ∥ 2 over β ∈ R m i \beta\in\mathbb{R}^{m_i} β ∈ R m i is equivalent to solving
β ( i ) = argmin β ∈ R m i ∥ [ Re ( r i ) Im ( r i ) ] − [ Re ( Δ R i ) Im ( Δ R i ) ] β ∥ 2 , \beta^{(i)}=\underset{\beta\in\mathbb{R}^{m_i}}{\operatorname{argmin}}\left\lVert
\begin{bmatrix}
\operatorname{Re}(r_i)\\
\operatorname{Im}(r_i)
\end{bmatrix}
-
\begin{bmatrix}
\operatorname{Re}(\Delta R_i)\\
\operatorname{Im}(\Delta R_i)
\end{bmatrix}\beta
\right\rVert_2, β ( i ) = β ∈ R m i argmin [ Re ( r i ) Im ( r i ) ] − [ Re ( Δ R i ) Im ( Δ R i ) ] β 2 ,
which is a standard real least-squares problem of size 2 p × m i 2p\times m_i 2 p × m i .
**Algorithm 2** AA($m$) for parameterized SCF in difference form
**Input:** Initial $X_0 \in \mathbb{U}^{n,k}$, ui-parameterization $\rho$ with function $\widehat{H}$ satisfying (12), $m \in \mathbb{N}$, $\tau > 0$
**Output:** approximate eigenbasis $X^* \in \mathbb{U}^{n,k}$ of the NEPv
1: Evaluate $\rho_0 = \rho(X_0)$
2: **for** $i = 0, 1, 2, \ldots$ **do**
3: Evaluate $H_i = \widehat{H}(\rho_i)$
4: Solve $H_iX_{i+1} = X_{i+1}\Lambda_{i+1}$ for the $k$ smallest eigenvalues in $\Lambda_{i+1}$
5: Evaluate $y_i = \rho(X_{i+1})$ and $r_i = y_i - \rho_i$
6: **if** $\lVert r_i\rVert \leq \tau$, **then** return $X^* = X_{i+1}$
7: Set $m_i = \min\{m,i\}$
8: **if** $m_i = 0$ **then**
9: Set $\rho_{i+1} = y_i$
10: **else**
11: Form $\Delta P_i = [\Delta\rho_{i-m_i},\ldots,\Delta\rho_{i-1}]$ and $\Delta R_i = [\Delta r_{i-m_i},\ldots,\Delta r_{i-1}]$, where $\Delta\rho_\ell = \rho_{\ell+1} - \rho_\ell$ and $\Delta r_\ell = r_{\ell+1} - r_\ell$
12: Compute $\beta^{(i)} \in \mathbb{R}^{m_i}$ by solving $\beta^{(i)} = \arg\min_{\beta\in\mathbb{R}^{m_i}}\lVert r_i - \Delta R_i\beta\rVert$
13: Set $\rho_{i+1} = \widetilde{\rho}_{i+1} + \widetilde{r}_{i+1}$, where $\widetilde{\rho}_{i+1} := \rho_i - \Delta P_i\beta^{(i)}$ and $\widetilde{r}_{i+1} := r_i - \Delta R_i\beta^{(i)}$
14: **end if**
15: **end for**
Alignment-based Anderson Acceleration
We next describe a direct approach to resolving basis non-uniqueness in SCF: at each step (3), we select a representative eigenbasis by aligning it with a fixed reference basis. This alignment can be viewed as a specialized ui-parameterization, but merits separate treatment because it is explicit, inexpensive to compute when k ≪ n k \ll n k ≪ n , and does not rely on any particular functional structure of H ( X ) H(X) H ( X ) .
Basis Alignment
We begin with a definition of an alignment operation.
Definition 2. Let M ∈ U n , k M \in\mathbb{U}^{n,k} M ∈ U n , k be a given reference basis matrix. The alignment of an orthogonal basis X ∈ U n , k X \in\mathbb{U}^{n,k} X ∈ U n , k with respect to M M M is defined as the orthogonal basis of range ( X ) \operatorname{range}(X) range ( X ) that is closest to M M M in the Frobenius norm, namely,
⟦ X ⟧ M : = arg min { ∥ Y − M ∥ F : Y ∈ U n , k , range ( Y ) = range ( X ) } , (18) \llbracket X \rrbracket_M := \arg\min\{\lVert Y-M\rVert_F : Y \in\mathbb{U}^{n,k},\ \operatorname{range}(Y)=\operatorname{range}(X)\}, \tag*{(18)} [ [ X ] ] M := arg min {∥ Y − M ∥ F : Y ∈ U n , k , range ( Y ) = range ( X )} , (18) where the minimizer is assumed to be unique; otherwise ⟦ X ⟧ M \llbracket X \rrbracket_M [ [ X ] ] M denotes any particular minimizer.
Basis alignment is a classical operation and is related to the orthogonal Procrustes problem; see, e.g., [32 ] . It is well known that the alignment ⟦ X ⟧ M \llbracket X \rrbracket_M [ [ X ] ] M can be obtained by a unitary rotation,
⟦ X ⟧ M = X Q , with Q = U V H , (19) \llbracket X \rrbracket_M = XQ,\qquad\text{with } Q = UV^H, \tag*{(19)} [ [ X ] ] M = X Q , with Q = U V H , (19)
where U , V ∈ U k , k U,V \in\mathbb{U}^{k,k} U , V ∈ U k , k are obtained from the singular value decomposition X H M = U Σ V H X^HM = U\Sigma V^H X H M = U Σ V H . The matrix Q Q Q may also be interpreted as the unitary polar factor of the matrix X H M X^HM X H M .
The alignment ⟦ X ⟧ M \llbracket X \rrbracket_M [ [ X ] ] M is uniquely defined, unitarily invariant, and locally differentiable in X X X , whenever X H M X^HM X H M is nonsingular. These properties follow from the explicit formula (17) and standard properties of the polar decomposition; see, e.g., [35 Thm. 8.6] and [52 Lem. A.1] . We summarize them in the following lemma and omit the proof.
Lemma 2. Let M ∈ U n , k M \in\mathbb{U}^{n,k} M ∈ U n , k be fixed. For all X ∈ U n , k X \in\mathbb{U}^{n,k} X ∈ U n , k such that X H M X^HM X H M is nonsingular, the alignment ⟦ X ⟧ M \llbracket X \rrbracket_M [ [ X ] ] M in (16) is uniquely defined and given by (17). It is invariant under right unitary transformations, i.e., ⟦ X Q ⟧ M = ⟦ X ⟧ M \llbracket XQ \rrbracket_M = \llbracket X \rrbracket_M [ [ X Q ] ] M = [ [ X ] ] M for all Q ∈ U k , k Q \in\mathbb{U}^{k,k} Q ∈ U k , k . Moreover, the map X ↦ ⟦ X ⟧ M X \mapsto\llbracket X \rrbracket_M X ↦ [ [ X ] ] M is well defined and differentiable in a neighborhood of X X X on U n , k \mathbb{U}^{n,k} U n , k , with respect to the real and imaginary parts of its entries.
Observe that basis alignment induces a particular ui-parameterization according to Definition 1. Indeed, by the unitary invariance of H ( X ) H(X) H ( X ) , we obtain the representation (12) using alignment as
H ( X ) ≡ H ( ⟦ X ⟧ M ) = H ^ ( ρ ( X ) ) , (20) H(X) \equiv H(\llbracket X\rrbracket_M) = \widehat{H}(\rho(X)), \tag*{(20)} H ( X ) ≡ H ( [ [ X ] ] M ) = H ( ρ ( X )) , (20)
where ρ ( X ) : = vec ( ⟦ X ⟧ M ) ∈ C n k \rho(X) := \operatorname{vec}(\llbracket X\rrbracket_M) \in\mathbb{C}^{nk} ρ ( X ) := vec ( [ [ X ] ] M ) ∈ C nk , and H ^ ( ρ ) \widehat{H}(\rho) H ( ρ ) is defined by applying H H H to the matricization of the vector ρ \rho ρ . By Lemma 2, the parameterization ρ ( X ) \rho(X) ρ ( X ) is well-defined and unitarily invariant whenever det ( X H M ) ≠ 0 \det(X^H M) \ne0 det ( X H M ) = 0 .
SCF with Alignment
Applying the alignment (16) at each SCF step selects a representative basis for the computed eigenspace and resolves the ambiguity in the basis choice. This gives the following aligned SCF iteration: starting from X ^ 0 = ⟦ X 0 ⟧ M \widehat{X}_0 = \llbracket X_0\rrbracket_M X 0 = [ [ X 0 ] ] M , compute
X ^ i + 1 = ⟦ X i + 1 ⟧ M with H ( X ^ i ) X i + 1 = X i + 1 Λ i + 1 , (21) \widehat{X}_{i+1} = \llbracket X_{i+1}\rrbracket_M \quad\text{with} \quad H(\widehat{X}_i)X_{i+1} = X_{i+1}\Lambda_{i+1}, \tag*{(21)} X i + 1 = [ [ X i + 1 ] ] M with H ( X i ) X i + 1 = X i + 1 Λ i + 1 , (21)
for i = 0 , 1 , … i = 0, 1, \ldots i = 0 , 1 , … , where X i + 1 ∈ U n , k X_{i+1} \in\mathbb{U}^{n,k} X i + 1 ∈ U n , k is an eigenbasis for the k k k smallest eigenvalues of H ( X ^ i ) H(\widehat{X}_i) H ( X i ) . In fixed-point form, this becomes
X ^ i + 1 = g ( X ^ i ) , (22) \widehat{X}_{i+1} = g(\widehat{X}_i), \tag*{(22)} X i + 1 = g ( X i ) , (22)
where
g ( X ) : = { ⟦ Y ⟧ M : Y ∈ U n , k is an eigenbasis of the k smallest eigenvalues of H ( X ) } . (23) g(X) := \left\{ \llbracket Y\rrbracket_M : Y \in\mathbb{U}^{n,k}\text{ is an eigenbasis of the }k\text{ smallest eigenvalues of }H(X) \right\}. \tag*{(23)} g ( X ) := { [ [ Y ] ] M : Y ∈ U n , k is an eigenbasis of the k smallest eigenvalues of H ( X ) } . (23)
The following lemma establishes the well-definedness and local differentiability of g g g under suitable conditions. The result essentially follows from Lemma 1 applied to the alignment-induced ui-parameterization (18), together with the regularity of the alignment map in Lemma 2.
Lemma 3. Let M ∈ U n , k M \in\mathbb{U}^{n,k} M ∈ U n , k be fixed. Suppose that, at X ∈ U n , k X \in\mathbb{U}^{n,k} X ∈ U n , k , the k k k smallest eigenvalues of H ( X ) H(X) H ( X ) are separated from the rest of the spectrum, i.e., λ k ( H ( X ) ) < λ k + 1 ( H ( X ) ) \lambda_k(H(X)) < \lambda_{k+1}(H(X)) λ k ( H ( X )) < λ k + 1 ( H ( X )) , and let Y ∈ U n , k Y \in\mathbb{U}^{n,k} Y ∈ U n , k be a corresponding eigenbasis. Assume further that Y H M Y^H M Y H M is nonsingular. Then,
(i) the fixed-point mapping g g g in (21) is single-valued at X X X (i.e., g ( X ) g(X) g ( X ) is uniquely defined);
(ii) the mapping g g g is continuous (and differentiable) at X X X if H H H is continuous (and differentiable) at X X X , in terms of the real and imaginary parts of its argument.
Proof. The proof follows the same argument as that of Lemma 1, with ρ \rho ρ and H ^ \widehat{H} H replaced by the alignment map ⟦ ⋅ ⟧ M \llbracket\cdot\rrbracket_M [ [ ⋅ ] ] M and H H H , respectively. The required unitary invariance and local regularity of the alignment map follow from Lemma 2, since Y H M Y^H M Y H M is nonsingular.
Anderson Acceleration with Aligned Bases
Applying AA(m m m ) to the aligned SCF mapping (21) gives Algorithm 3. This is essentially the parameterized scheme in Algorithm 2 with alignment as the parameterization ρ ( X ) = ⟦ X ⟧ M ∈ C n , k \rho(X) = \llbracket X\rrbracket_M \in\mathbb{C}^{n,k} ρ ( X ) = [ [ X ] ] M ∈ C n , k , and is presented directly with basis matrices ⟦ X ⟧ M \llbracket X\rrbracket_M [ [ X ] ] M rather than their vectorizations.
In Algorithm 3, the differences Δ X ^ i \Delta\widehat{X}_i Δ X i and Δ R i \Delta\mathcal{R}_i Δ R i are block matrices of the form Δ ≡ [ Δ 1 , … , Δ m ] \Delta\equiv[\Delta_1,\ldots,\Delta_m] Δ ≡ [ Δ 1 , … , Δ m ] with each block column Δ j ∈ C n , k \Delta_j \in\mathbb{C}^{n,k} Δ j ∈ C n , k , and the block linear combination is Δ ∘ β : = ∑ j = 1 m β j Δ j \Delta\circ\beta:= \sum_{j=1}^{m}\beta_j\Delta_j Δ ∘ β := ∑ j = 1 m β j Δ j . To solve the least-squares problem in line 12, one can reformulate it in the standard matrix form
min β ∈ R m ∥ [ Re ( vec ( R i ) ) Im ( vec ( R i ) ) ] − [ Re ( V i ) Im ( V i ) ] β ∥ 2 , (24) \min_{\beta\in\mathbb{R}^{m}} \left\| \begin{bmatrix} \operatorname{Re}(\operatorname{vec}(\mathcal{R}_i)) \\ \operatorname{Im}(\operatorname{vec}(\mathcal{R}_i)) \end{bmatrix} -
\begin{bmatrix} \operatorname{Re}(\mathcal{V}_i) \\ \operatorname{Im}(\mathcal{V}_i) \end{bmatrix}\beta\right\|_2, \tag*{(24)} β ∈ R m min [ Re ( vec ( R i )) Im ( vec ( R i )) ] − [ Re ( V i ) Im ( V i ) ] β 2 , (24)
where V i = [ vec ( Δ R i − m i ) , … , vec ( Δ R i − 1 ) ] ∈ C n k , m i \mathcal{V}_i = [\operatorname{vec}(\Delta\mathcal{R}_{i-m_i}),\ldots,\operatorname{vec}(\Delta\mathcal{R}_{i-1})] \in\mathbb{C}^{n k,m_i} V i = [ vec ( Δ R i − m i ) , … , vec ( Δ R i − 1 )] ∈ C nk , m i , and the real and imaginary parts of the complex variables have been separated. Alternatively, to avoid explicitly forming and operating on vectorized matrices, we can regard min β ∥ R i − ∑ j = 1 m Δ R j β j ∥ F \min_\beta\|\mathcal{R}_i-\sum_{j=1}^{m}\Delta\mathcal{R}_j\beta_j\|_F min β ∥ R i − ∑ j = 1 m Δ R j β j ∥ F directly as a least-squares problem in the vector space C n × k \mathbb{C}^{n\times k} C n × k , equipped with the Frobenius inner product ⟨ A , B ⟩ = Re ( tr ( A H B ) ) \langle A,B\rangle= \operatorname{Re}(\operatorname{tr}(A^H B)) ⟨ A , B ⟩ = Re ( tr ( A H B )) .
Algorithm 3 AA(m m m ) for aligned SCF in difference form
Input: Initial X 0 ∈ U n , k X_0 \in\mathbb{U}^{n,k} X 0 ∈ U n , k , matrix function H H H , reference matrix M ∈ U n , k M \in\mathbb{U}^{n,k} M ∈ U n , k , m ∈ N m \in\mathbb{N} m ∈ N , τ > 0 \tau> 0 τ > 0
Output: approximate eigenbasis X ∗ ∈ U n , k X^* \in\mathbb{U}^{n,k} X ∗ ∈ U n , k of the NEPv (1)
Compute the SVD X 0 H M = U 0 Σ 0 V 0 H X_0^H M = U_0 \Sigma_0 V_0^H X 0 H M = U 0 Σ 0 V 0 H and set X ^ 0 = X 0 U 0 V 0 H \widehat{X}_0 = X_0 U_0 V_0^H X 0 = X 0 U 0 V 0 H
for i = 0 , 1 , 2 , … i = 0, 1, 2, \ldots i = 0 , 1 , 2 , … do
Evaluate H i = H ( X ^ i ) H_i = H(\widehat{X}_i) H i = H ( X i )
Solve H i X i + 1 = X i + 1 Λ i + 1 H_i X_{i+1} = X_{i+1} \Lambda_{i+1} H i X i + 1 = X i + 1 Λ i + 1 for the k k k smallest eigenvalues in Λ i + 1 \Lambda_{i+1} Λ i + 1
Compute the SVD X i + 1 H M = U i + 1 Σ i + 1 V i + 1 H X_{i+1}^H M = U_{i+1} \Sigma_{i+1} V_{i+1}^H X i + 1 H M = U i + 1 Σ i + 1 V i + 1 H and set Y i = X i + 1 U i + 1 V i + 1 H Y_i = X_{i+1} U_{i+1} V_{i+1}^H Y i = X i + 1 U i + 1 V i + 1 H and R i = Y i − X ^ i R_i = Y_i - \widehat{X}_i R i = Y i − X i
if ∥ R i ∥ F ≤ τ \lVert R_i \rVert_F \le\tau ∥ R i ∥ F ≤ τ , then return X ∗ = Y i X^* = Y_i X ∗ = Y i
Set m i = min { m , i } m_i = \min\{m,i\} m i = min { m , i }
if m i = 0 m_i = 0 m i = 0 then
Set X ^ i + 1 = Y i \widehat{X}_{i+1} = Y_i X i + 1 = Y i
else
Form Δ X ^ i = [ Δ X ^ i − m i , … , Δ X ^ i − 1 ] \Delta\widehat{X}_i = [\Delta\widehat{X}_{i-m_i},\ldots,\Delta\widehat{X}_{i-1}] Δ X i = [ Δ X i − m i , … , Δ X i − 1 ] and Δ R i = [ Δ R i − m i , … , Δ R i − 1 ] \Delta R_i = [\Delta R_{i-m_i},\ldots,\Delta R_{i-1}] Δ R i = [ Δ R i − m i , … , Δ R i − 1 ] , where Δ X ^ ℓ = X ^ ℓ + 1 − X ^ ℓ \Delta\widehat{X}_{\ell} = \widehat{X}_{\ell+1} - \widehat{X}_{\ell} Δ X ℓ = X ℓ + 1 − X ℓ and Δ R ℓ = R ℓ + 1 − R ℓ \Delta R_{\ell} = R_{\ell+1} - R_{\ell} Δ R ℓ = R ℓ + 1 − R ℓ
Compute β ( i ) ∈ R m i \beta^{(i)} \in\mathbb{R}^{m_i} β ( i ) ∈ R m i by solving β ( i ) = arg min β ∈ R m i ∥ R i − Δ R i ⊙ β ∥ F \beta^{(i)} = \operatorname*{arg\,min}_{\beta\in\mathbb{R}^{m_i}} \lVert R_i - \Delta R_i \odot\beta\rVert_F β ( i ) = arg min β ∈ R m i ∥ R i − Δ R i ⊙ β ∥ F
Set X ^ i + 1 = X ~ i + 1 + R ~ i + 1 \widehat{X}_{i+1} = \widetilde{X}_{i+1} + \widetilde{R}_{i+1} X i + 1 = X i + 1 + R i + 1 , where X ~ i + 1 : = X ^ i − Δ X ^ i ⊙ β ( i ) \widetilde{X}_{i+1} := \widehat{X}_i - \Delta\widehat{X}_i \odot\beta^{(i)} X i + 1 := X i − Δ X i ⊙ β ( i ) and R ~ i + 1 : = R i − Δ R i ⊙ β ( i ) \widetilde{R}_{i+1} := R_i - \Delta R_i \odot\beta^{(i)} R i + 1 := R i − Δ R i ⊙ β ( i )
end if
end for
Riemannian Anderson Acceleration
We now consider another technique to address the unitary invariance of the SCF (3) by regarding it as a fixed-point iteration on the Grassmann manifold G ( n , k ) \mathcal{G}(n,k) G ( n , k ) . In this formulation, each SCF iterate is viewed as a k k k -dimensional subspace, so the ambiguity caused by the choice of orthogonal basis is removed at the level of the iteration. The Anderson mixing is then carried out, using the local coordinates of the iterates, in a tangent space of Grassmannian, which provides a local linearization of the manifold. This approach is intrinsic to unitary invariance of the NEPv and SCF, but also requires additional geometric tools and operations for its derivation and analysis. We describe the essential ingredients and a self-consistent treatment below; related operations and Anderson mixing on matrix manifold can also be found in [2 , 50 ] .
Grassmannian Notation and Basics
We briefly introduce the notation and concepts needed in our derivation; see [2 , 22 ] for details.
Tangent space and metric. The tangent space T X T_{\mathcal{X}} T X at X ∈ G ( n , k ) \mathcal{X} \in\mathcal{G}(n,k) X ∈ G ( n , k ) is the real vector space of velocities of smooth curves through X \mathcal{X} X . The canonical (Euclidean) inner products on these tangent spaces define the canonical Riemannian metric, and ∥ ⋅ ∥ F \lVert\cdot\rVert_F ∥ ⋅ ∥ F is the induced tangent norm, which agrees with the Frobenius norm in the matrix representations used below.
Geodesics and exponential/logarithmic maps. Geodesics generalize straight lines. The geodesic distance dist ( X , Y ) \operatorname{dist}(\mathcal{X},\mathcal{Y}) dist ( X , Y ) is the length of a shortest geodesic connecting X \mathcal{X} X and Y \mathcal{Y} Y . The smooth exponential map Exp X : T X → G ( n , k ) \operatorname{Exp}_{\mathcal{X}} : T_{\mathcal{X}} \to\mathcal{G}(n,k) Exp X : T X → G ( n , k ) maps ξ \xi ξ to the point reached at time 1 1 1 along the geodesic starting at X \mathcal{X} X with initial velocity ξ \xi ξ . Its smooth local inverse Log X : G ( n , k ) → T X \operatorname{Log}_{\mathcal{X}} : \mathcal{G}(n,k) \to T_{\mathcal{X}} Log X : G ( n , k ) → T X maps a nearby point Y \mathcal{Y} Y back to ξ ∈ T X \xi\in T_{\mathcal{X}} ξ ∈ T X . These maps serve as local analogues of addition (symbolically, X + ξ \mathcal{X}+\xi X + ξ ) and subtraction (symbolically, Y − X \mathcal{Y}-\mathcal{X} Y − X ), respectively. In particular, dist ( X , Y ) = ∥ Log X ( Y ) ∥ F \operatorname{dist}(\mathcal{X},\mathcal{Y}) = \lVert\operatorname{Log}_{\mathcal{X}}(\mathcal{Y}) \rVert_F dist ( X , Y ) = ∥ Log X ( Y ) ∥ F , whenever the logarithmic map is defined.
Parallel transport. For sufficiently close X \mathcal{X} X and Y \mathcal{Y} Y , parallel transport T X Y : T X → T Y \mathcal{T}_{\mathcal{X}}^{\mathcal{Y}} : T_{\mathcal{X}} \to T_{\mathcal{Y}} T X Y : T X → T Y moves tangent vectors along the unique shortest geodesic connecting them. This map is linear and preserves inner products, allowing vectors associated with different iterates to be combined in a common tangent space.
Fixed-Point Iteration on the Grassmannian
Due to the unitary invariance of the NEPv (1) , each SCF iterate X i X_i X i in (3) can be regarded as a k k k -dimensional subspace range ( X i ) \operatorname{range}(X_i) range ( X i ) , i.e., a point in the Grassmannian. Therefore, SCF iteration (3) can be interpreted as the fixed-point iteration
X i + 1 = g ( X i ) , (25) \mathcal{X}_{i+1}=g(\mathcal{X}_i), \tag*{(25)} X i + 1 = g ( X i ) , (25)
where X i ∈ G ( n , k ) \mathcal{X}_i\in\mathcal{G}(n,k) X i ∈ G ( n , k ) is a k k k -dimensional subspace of C n \mathbb{C}^n C n , and g : G ( n , k ) → G ( n , k ) g:\mathcal{G}(n,k)\to\mathcal{G}(n,k) g : G ( n , k ) → G ( n , k ) is given by
g ( X ) : = { Y : Y ∈ G ( n , k ) is an eigenspace for the k smallest eigenvalues of H ( X ) } , (26) g(\mathcal{X}):=\{\mathcal{Y}:\mathcal{Y}\in\mathcal{G}(n,k)\text{ is an eigenspace for the }k\text{ smallest eigenvalues of }H(\mathcal{X})\}, \tag*{(26)} g ( X ) := { Y : Y ∈ G ( n , k ) is an eigenspace for the k smallest eigenvalues of H ( X )} , (26)
and X ∈ U n , k X\in\mathbb{U}^{n,k} X ∈ U n , k denotes an orthogonal basis of X \mathcal{X} X . The fixed-point mapping g g g is well defined and regular under the eigengap assumption of H ( X ) H(X) H ( X ) , as precisely described in the following lemma.
Lemma 4. Let X ∈ G ( n , k ) \mathcal{X}\in\mathcal{G}(n,k) X ∈ G ( n , k ) , and let X ∈ U n , k X\in\mathbb{U}^{n,k} X ∈ U n , k be any orthonormal basis of X \mathcal{X} X . Suppose that the k k k smallest eigenvalues of H ( X ) H(X) H ( X ) are separated from the rest of the spectrum, i.e., λ k ( H ( X ) ) < λ k + 1 ( H ( X ) ) \lambda_k(H(X))<\lambda_{k+1}(H(X)) λ k ( H ( X )) < λ k + 1 ( H ( X )) . Then the fixed-point mapping g g g in (26) is single-valued at X \mathcal{X} X . If, in addition, H H H is continuous (and differentiable) in a neighborhood of X X X , then g g g is locally continuous (and differentiable) at X \mathcal{X} X . 1
Proof. By representing the Grassmannian as
G ( n , k ) = { P ∈ C n , n : P = P H , P 2 = P , rank ( P ) = k } , \mathcal{G}(n,k)=\{P\in\mathbb{C}^{n,n}:P=P^H,\ P^2=P,\ \operatorname{rank}(P)=k\}, G ( n , k ) = { P ∈ C n , n : P = P H , P 2 = P , rank ( P ) = k } ,
each X i ∈ G ( n , k ) \mathcal{X}_i\in\mathcal{G}(n,k) X i ∈ G ( n , k ) can be identified with P i = X i X i H P_i=X_iX_i^H P i = X i X i H ; see, e.g., [13 ] . Hence, the fixed-point mapping g g g in (26) is obtained from (16) by using the ui-parameterization ρ ( X ) : = X X H ∈ C n , n \rho(X):=XX^H\in\mathbb{C}^{n,n} ρ ( X ) := X X H ∈ C n , n (up to vectorization), with the associated map H ^ ( P ) : = H ( X ( P ) ) \widehat{H}(P):=H(X(P)) H ( P ) := H ( X ( P )) . Here, X ( P ) : = P M ( M H P M ) − 1 / 2 X(P):=PM(M^HPM)^{-1/2} X ( P ) := P M ( M H P M ) − 1/2 , where M ∈ C n , k M\in\mathbb{C}^{n,k} M ∈ C n , k is a fixed rank-k k k matrix such that M H P M M^HPM M H P M is nonsingular. The function X ( P ) X(P) X ( P ) selects an orthonormal basis of the range of P P P , and it is locally continuous and differentiable in P P P whenever M H P M M^HPM M H P M is nonsingular. Therefore, the result follows directly from Lemma 1.
Anderson Acceleration on the Grassmannian
We next describe the AA for the fixed-point iteration (25) on the Grassmannian. Since the iteration subspaces { X i } \{\mathcal{X}_i\} { X i } cannot be directly added or subtracted in the Euclidean sense, the Riemannian Anderson acceleration performs the mixing operations on { X i } \{\mathcal{X}_i\} { X i } using their local coordinates in a tangent space (a Euclidean vector space) of the manifold.
The basic idea is to represent nearby subspaces by tangent vectors at a reference point, allowing the linear combinations and residual evaluation required by Anderson acceleration to be defined in the usual Euclidean manner. Particularly, using X i \mathcal{X}_i X i as a reference point, we can formulate a mixing scheme analogous to the AA(m m m ) in (8) as
X i + 1 = Exp X i ( ∑ ℓ = 0 m − 1 α ℓ Log X i ( Y i − ℓ ) ) , (27) \mathcal{X}_{i+1}=\operatorname{Exp}_{\mathcal{X}_i}\left(\sum_{\ell=0}^{m-1}\alpha_\ell\operatorname{Log}_{\mathcal{X}_i}(\mathcal{Y}_{i-\ell})\right), \tag*{(27)} X i + 1 = Exp X i ( ℓ = 0 ∑ m − 1 α ℓ Log X i ( Y i − ℓ ) ) , (27)
where Y ℓ = g ( X ℓ ) \mathcal{Y}_\ell=g(\mathcal{X}_\ell) Y ℓ = g ( X ℓ ) , and the coefficients { α ℓ } \{\alpha_\ell\} { α ℓ } are obtained by solving
min ∑ ℓ = 0 m − 1 α ℓ = 1 ∥ ∑ ℓ = 0 m − 1 α ℓ ⋅ T X i − ℓ X i r ( X i − ℓ ) ∥ F with r ( X ) : = Log X ( g ( X ) ) . (28) \min_{\substack{\sum_{\ell=0}^{m-1}\alpha_\ell=1}}\left\|\sum_{\ell=0}^{m-1}\alpha_\ell\cdot\mathcal{T}_{\mathcal{X}_{i-\ell}}^{\mathcal{X}_i}r(\mathcal{X}_{i-\ell})\right\|_F
\quad\text{with}\quad r(\mathcal{X}):=\operatorname{Log}_{\mathcal{X}}(g(\mathcal{X})). \tag*{(28)} ∑ ℓ = 0 m − 1 α ℓ = 1 min ℓ = 0 ∑ m − 1 α ℓ ⋅ T X i − ℓ X i r ( X i − ℓ ) F with r ( X ) := Log X ( g ( X )) . (28)
Recall that the exponential map Exp X ( ξ ) ∈ G ( n , k ) \operatorname{Exp}_{\mathcal{X}}(\xi)\in\mathcal{G}(n,k) Exp X ( ξ ) ∈ G ( n , k ) , with X ∈ G ( n , k ) \mathcal{X}\in\mathcal{G}(n,k) X ∈ G ( n , k ) and ξ ∈ T X \xi\in T_{\mathcal{X}} ξ ∈ T X , is a Riemannian analogue of the addition (informally, X + ξ \mathcal{X}+\xi X + ξ ), the logarithm map Log X ( Y ) ∈ T X \operatorname{Log}_{\mathcal{X}}(\mathcal{Y})\in T_{\mathcal{X}} Log X ( Y ) ∈ T X , with X , Y ∈ G ( n , k ) \mathcal{X},\mathcal{Y}\in\mathcal{G}(n,k) X , Y ∈ G ( n , k ) , a Riemannian analogue of the difference (informally, Y − X \mathcal{Y}-\mathcal{X} Y − X ), and T X Y \mathcal{T}_{\mathcal{X}}^{\mathcal{Y}} T X Y denotes the parallel transport along the geodesic from X \mathcal{X} X to Y \mathcal{Y} Y . Consequently, the mixing step (27) is a direct Riemannian analogue of x i + 1 = g ( x i ) + ∑ ℓ = 0 m − 1 α ℓ ( g ( x i − ℓ ) − g ( x i ) ) x_{i+1}=g(x_i)+\sum_{\ell=0}^{m-1}\alpha_\ell(g(x_{i-\ell})-g(x_i)) x i + 1 = g ( x i ) + ∑ ℓ = 0 m − 1 α ℓ ( g ( x i − ℓ ) − g ( x i )) from (8) , while the mapping r ( X ) r(\mathcal{X}) r ( X ) in (28) , measuring the differences between g ( X ) g(\mathcal{X}) g ( X ) and X \mathcal{X} X on the tangent space T X T_{\mathcal{X}} T X , is a Riemannian analogue of the residual g ( x ) − x g(x)-x g ( x ) − x in (9) .
The following result establishes the Riemannian analogue of the expansion relation (10) for standard Anderson acceleration, and it partially justifies the coefficient choice in (28) . It shows that, after transporting residuals to the common tangent space T X i T_{\mathcal{X}_i} T X i , the residual of the mixed iterate is approximated by the same affine combination used in (28) .
Lemma 5. Let r ( X ) = Log X ( g ( X ) ) r(\mathcal{X}) = \operatorname{Log}_{\mathcal{X}}(g(\mathcal{X})) r ( X ) = Log X ( g ( X )) be locally differentiable in a neighborhood of X i ∈ G ( n , k ) \mathcal{X}_i \in\mathcal{G}(n,k) X i ∈ G ( n , k ) . Let X i − m + 1 , … , X i − 1 ∈ G ( n , k ) \mathcal{X}_{i-m+1},\ldots,\mathcal{X}_{i-1} \in\mathcal{G}(n,k) X i − m + 1 , … , X i − 1 ∈ G ( n , k ) be sufficiently close to X i \mathcal{X}_i X i , and let the coefficients { α ℓ } ℓ = 0 m − 1 \{\alpha_\ell\}_{\ell=0}^{m-1} { α ℓ } ℓ = 0 m − 1 satisfy ∑ ℓ = 0 m − 1 α ℓ = 1 \sum_{\ell=0}^{m-1}\alpha_\ell=1 ∑ ℓ = 0 m − 1 α ℓ = 1 and be uniformly bounded (independent of X ℓ \mathcal{X}_\ell X ℓ ). Then the mixed iterate
X ~ i + 1 = Exp X i ( ∑ ℓ = 0 m − 1 α ℓ Log X i ( X i − ℓ ) ) (29) \widetilde{\mathcal{X}}_{i+1}=\operatorname{Exp}_{\mathcal{X}_i}\left(\sum_{\ell=0}^{m-1}\alpha_\ell\operatorname{Log}_{\mathcal{X}_i}(\mathcal{X}_{i-\ell})\right) \tag*{(29)} X i + 1 = Exp X i ( ℓ = 0 ∑ m − 1 α ℓ Log X i ( X i − ℓ ) ) (29) satisfies
T X ~ i + 1 X i r ( X ~ i + 1 ) = ∑ ℓ = 0 m − 1 α ℓ T X i − ℓ X i r ( X i − ℓ ) + o ( max ℓ = 1 , … , m − 1 dist ( X i , X i − ℓ ) ) . (30) \mathcal{T}_{\widetilde{\mathcal{X}}_{i+1}}^{\mathcal{X}_i}r(\widetilde{\mathcal{X}}_{i+1})=\sum_{\ell=0}^{m-1}\alpha_\ell\mathcal{T}_{\mathcal{X}_{i-\ell}}^{\mathcal{X}_i}r(\mathcal{X}_{i-\ell})+o\left(\max_{\ell=1,\ldots,m-1}\operatorname{dist}(\mathcal{X}_i,\mathcal{X}_{i-\ell})\right). \tag*{(30)} T X i + 1 X i r ( X i + 1 ) = ℓ = 0 ∑ m − 1 α ℓ T X i − ℓ X i r ( X i − ℓ ) + o ( ℓ = 1 , … , m − 1 max dist ( X i , X i − ℓ ) ) . (30) Here, X ~ i + 1 \widetilde{\mathcal{X}}_{i+1} X i + 1 differs from the update X i + 1 \mathcal{X}_{i+1} X i + 1 in (27) by replacing Y ℓ = g ( X ℓ ) \mathcal{Y}_\ell=g(\mathcal{X}_\ell) Y ℓ = g ( X ℓ ) with X ℓ \mathcal{X}_\ell X ℓ .
Proof. Define the local representation of the residual vector field at X i \mathcal{X}_i X i by
r ^ i ( ξ ) : = T Exp X i ( ξ ) X i r ( Exp X i ( ξ ) ) , ξ ∈ T X i . \widehat{r}_i(\xi):=\mathcal{T}_{\operatorname{Exp}_{\mathcal{X}_i}(\xi)}^{\mathcal{X}_i}r(\operatorname{Exp}_{\mathcal{X}_i}(\xi)),\qquad\xi\in T_{\mathcal{X}_i}. r i ( ξ ) := T Exp X i ( ξ ) X i r ( Exp X i ( ξ )) , ξ ∈ T X i .
Since r r r is locally differentiable, so is r ^ i \widehat{r}_i r i , and hence r ^ i ( ξ ) = r ^ i ( 0 ) + D r ^ i ( 0 ) [ ξ ] + o ( ∥ ξ ∥ F ) \widehat{r}_i(\xi)=\widehat{r}_i(0)+D\widehat{r}_i(0)[\xi]+o(\lVert\xi\rVert_F) r i ( ξ ) = r i ( 0 ) + D r i ( 0 ) [ ξ ] + o (∥ ξ ∥ F ) , where D r ^ i ( 0 ) D\widehat{r}_i(0) D r i ( 0 ) denotes the differential of r ^ i \widehat{r}_i r i at the origin of T X i T_{\mathcal{X}_i} T X i . Applying this expansion to ξ α = ∑ ℓ = 0 m − 1 α ℓ ξ ℓ \xi_\alpha=\sum_{\ell=0}^{m-1}\alpha_\ell\xi_\ell ξ α = ∑ ℓ = 0 m − 1 α ℓ ξ ℓ and to each ξ ℓ = Log X i ( X i − ℓ ) \xi_\ell=\operatorname{Log}_{\mathcal{X}_i}(\mathcal{X}_{i-\ell}) ξ ℓ = Log X i ( X i − ℓ ) , and using ∑ ℓ = 0 m − 1 α ℓ = 1 \sum_{\ell=0}^{m-1}\alpha_\ell=1 ∑ ℓ = 0 m − 1 α ℓ = 1 together with the uniform boundedness of { α ℓ } \{\alpha_\ell\} { α ℓ } , gives
r ^ i ( ξ α ) = ∑ ℓ = 0 m − 1 α ℓ r ^ i ( ξ ℓ ) + o ( max ℓ = 1 , … , m − 1 ∥ ξ ℓ ∥ F ) . \widehat{r}_i(\xi_\alpha)=\sum_{\ell=0}^{m-1}\alpha_\ell\widehat{r}_i(\xi_\ell)+o\left(\max_{\ell=1,\ldots,m-1}\lVert\xi_\ell\rVert_F\right). r i ( ξ α ) = ℓ = 0 ∑ m − 1 α ℓ r i ( ξ ℓ ) + o ( ℓ = 1 , … , m − 1 max ∥ ξ ℓ ∥ F ) .
Hence, (30) follows from ∥ ξ ℓ ∥ F = dist ( X i , X i − ℓ ) \lVert\xi_\ell\rVert_F=\operatorname{dist}(\mathcal{X}_i,\mathcal{X}_{i-\ell}) ∥ ξ ℓ ∥ F = dist ( X i , X i − ℓ ) and r ^ i ( ξ ℓ ) = T X i − ℓ X i r ( X i − ℓ ) \widehat{r}_i(\xi_\ell)=\mathcal{T}_{\mathcal{X}_{i-\ell}}^{\mathcal{X}_i}r(\mathcal{X}_{i-\ell}) r i ( ξ ℓ ) = T X i − ℓ X i r ( X i − ℓ ) .
The extension of AA to the Grassmann manifold through tangent-space operations, as in (25), is conceptually straightforward, although technically involved. Similar ideas are explored in the general framework for Anderson mixing on the Riemannian manifold developed in [50 ] , primarily from a root-finding perspective. In contrast, our derivation of (25) and its justification in Lemma 5 are based directly on fixed-point iterations, following closely the rationale of classical Anderson acceleration using the local expansion (10) .
Difference Form and Implementation
For numerical implementation, it is more convenient to use a difference form of AA ( m ) \operatorname{AA}(m) AA ( m ) on the Grassmannian, in direct analogy with (10). Following the same derivation as for (25), we define the Riemannian analogues of the differences for the sequences { X ℓ } \{\mathcal{X}_\ell\} { X ℓ } and { r ( X ℓ ) } \{r(\mathcal{X}_\ell)\} { r ( X ℓ )} as
Δ X ℓ ( i ) : = T X ℓ + 1 X i ( Log X ℓ + 1 ( X ℓ ) ) and Δ r ℓ ( i ) : = T X ℓ + 1 X i ( T X ℓ X ℓ + 1 ( r ( X ℓ ) ) − r ( X ℓ + 1 ) ) , (31) \Delta\mathcal{X}_\ell^{(i)}:=\mathcal{T}_{\mathcal{X}_{\ell+1}}^{\mathcal{X}_i}\left(\operatorname{Log}_{\mathcal{X}_{\ell+1}}(\mathcal{X}_\ell)\right)\quad\text{and}\quad\Delta r_\ell^{(i)}:=\mathcal{T}_{\mathcal{X}_{\ell+1}}^{\mathcal{X}_i}\left(\mathcal{T}_{\mathcal{X}_\ell}^{\mathcal{X}_{\ell+1}}(r(\mathcal{X}_\ell))-r(\mathcal{X}_{\ell+1})\right), \tag*{(31)} Δ X ℓ ( i ) := T X ℓ + 1 X i ( Log X ℓ + 1 ( X ℓ ) ) and Δ r ℓ ( i ) := T X ℓ + 1 X i ( T X ℓ X ℓ + 1 ( r ( X ℓ )) − r ( X ℓ + 1 ) ) , (31)
where the parallel transports place all difference vectors in a common tangent space T X i T_{\mathcal{X}_i} T X i . We can then recast the difference form (10) of AA ( m ) \operatorname{AA}(m) AA ( m ) into the Riemannian version2
X i + 1 = Exp X i ( r ( X i ) + ∑ ℓ = i − m i − 1 β ℓ ⋅ ( Δ X ℓ ( i ) + Δ r ℓ ( i ) ) ) , (32) \mathcal{X}_{i+1}=\operatorname{Exp}_{\mathcal{X}_i}\left(r(\mathcal{X}_i)+\sum_{\ell=i-m}^{i-1}\beta_\ell\cdot\left(\Delta\mathcal{X}_\ell^{(i)}+\Delta r_\ell^{(i)}\right)\right), \tag*{(32)} X i + 1 = Exp X i ( r ( X i ) + ℓ = i − m ∑ i − 1 β ℓ ⋅ ( Δ X ℓ ( i ) + Δ r ℓ ( i ) ) ) , (32)
where the coefficients { β ℓ } \{\beta_\ell\} { β ℓ } are obtained from the least squares
min β ∥ r ( X i ) + ∑ ℓ = i − m i − 1 β ℓ Δ r ℓ ( i ) ∥ F . (33) \min_{\beta}\left\lVert r(\mathcal{X}_i)+\sum_{\ell=i-m}^{i-1}\beta_\ell\Delta r_\ell^{(i)}\right\rVert_F. \tag*{(33)} β min r ( X i ) + ℓ = i − m ∑ i − 1 β ℓ Δ r ℓ ( i ) F . (33)
We caution that, unlike the Euclidean difference form (10), which is equivalent to the basic form (8), the formulation (29) is not exactly equivalent to (25), since different transports are applied to the individual difference vectors. Nevertheless, when all iterates are sufficiently close, the two formulations agree up to
Algorithm 4 Riemannian AA(m m m ) for SCF on the Grassmannian in difference form
Input: Initial X 0 ∈ U n , k X_0 \in\mathbb{U}^{n,k} X 0 ∈ U n , k , matrix function H H H , m ∈ N m \in\mathbb{N} m ∈ N , τ > 0 \tau> 0 τ > 0
Output: approximate eigenbasis X ∗ ∈ U n , k X^* \in\mathbb{U}^{n,k} X ∗ ∈ U n , k of the NEPv (1)
for i = 0 , 1 , 2 , … i = 0, 1, 2, \ldots i = 0 , 1 , 2 , … do
Evaluate H i = H ( X i ) H_i = H(X_i) H i = H ( X i )
Solve H i Y i = Y i Λ i H_iY_i = Y_i\Lambda_i H i Y i = Y i Λ i for the k k k smallest eigenvalues in Λ i \Lambda_i Λ i
Compute the Riemannian residual r i = Log X i ( Y i ) ∈ C n , k r_i = \operatorname{Log}_{X_i}(Y_i) \in\mathbb{C}^{n,k} r i = Log X i ( Y i ) ∈ C n , k
if ∥ r i ∥ F ≤ τ \|r_i\|_F \le\tau ∥ r i ∥ F ≤ τ , then return X ∗ = Y i X^* = Y_i X ∗ = Y i
Set m i = min { m , i } m_i = \min\{m,i\} m i = min { m , i }
if m i = 0 m_i = 0 m i = 0 then
Set X i + 1 = Y i X_{i+1} = Y_i X i + 1 = Y i and compute T X i X i + 1 \mathcal{T}_{X_i}^{X_{i+1}} T X i X i + 1 by SVD r i = U i Θ i V i H r_i = U_i\Theta_iV_i^H r i = U i Θ i V i H (see (36) )
else
Compute Δ X i − 1 ( i ) = Log X i ( X i − 1 ) ∈ C n , k \Delta X_{i-1}^{(i)} = \operatorname{Log}_{X_i}(X_{i-1}) \in\mathbb{C}^{n,k} Δ X i − 1 ( i ) = Log X i ( X i − 1 ) ∈ C n , k and Δ r i − 1 ( i ) = T X i − 1 X i r i − 1 − r i ∈ C n , k \Delta r_{i-1}^{(i)} = \mathcal{T}_{X_{i-1}}^{X_i}r_{i-1} - r_i \in\mathbb{C}^{n,k} Δ r i − 1 ( i ) = T X i − 1 X i r i − 1 − r i ∈ C n , k
Transport Δ X i − ℓ ( i ) = T X i − 1 X i Δ X i − ℓ ( i − 1 ) ∈ C n , k \Delta X_{i-\ell}^{(i)} = \mathcal{T}_{X_{i-1}}^{X_i}\Delta X_{i-\ell}^{(i-1)} \in\mathbb{C}^{n,k} Δ X i − ℓ ( i ) = T X i − 1 X i Δ X i − ℓ ( i − 1 ) ∈ C n , k and Δ r i − ℓ ( i ) = T X i − 1 X i Δ r i − ℓ ( i − 1 ) ∈ C n , k \Delta r_{i-\ell}^{(i)} = \mathcal{T}_{X_{i-1}}^{X_i}\Delta r_{i-\ell}^{(i-1)} \in\mathbb{C}^{n,k} Δ r i − ℓ ( i ) = T X i − 1 X i Δ r i − ℓ ( i − 1 ) ∈ C n , k , for ℓ = 2 , … , m i \ell= 2,\ldots,m_i ℓ = 2 , … , m i
Form Δ X i = [ Δ X i − m i ( i ) , … , Δ X i − 1 ( i ) ] ∈ C n , k m i \Delta X_i = [\Delta X_{i-m_i}^{(i)},\ldots,\Delta X_{i-1}^{(i)}] \in\mathbb{C}^{n,km_i} Δ X i = [ Δ X i − m i ( i ) , … , Δ X i − 1 ( i ) ] ∈ C n , k m i and Δ R i = [ Δ r i − m i ( i ) , … , Δ r i − 1 ( i ) ] ∈ C n , k m i \Delta R_i = [\Delta r_{i-m_i}^{(i)},\ldots,\Delta r_{i-1}^{(i)}] \in\mathbb{C}^{n,km_i} Δ R i = [ Δ r i − m i ( i ) , … , Δ r i − 1 ( i ) ] ∈ C n , k m i
Compute β ( i ) ∈ R m i \beta^{(i)} \in\mathbb{R}^{m_i} β ( i ) ∈ R m i by solving β ( i ) = arg min β ∈ R m i ∥ r i + Δ R i ⊙ β ∥ F \beta^{(i)} = \arg\min_{\beta\in\mathbb{R}^{m_i}}\|r_i + \Delta R_i \odot\beta\|_F β ( i ) = arg min β ∈ R m i ∥ r i + Δ R i ⊙ β ∥ F
Set up r ~ i = r i + ( Δ R i + Δ X i ) ⊙ β ( i ) \widetilde r_i = r_i + (\Delta R_i + \Delta X_i)\odot\beta^{(i)} r i = r i + ( Δ R i + Δ X i ) ⊙ β ( i )
Compute X i + 1 = Exp X i ( r ~ i ) ∈ U n , k X_{i+1} = \operatorname{Exp}_{X_i}(\widetilde r_i) \in\mathbb{U}^{n,k} X i + 1 = Exp X i ( r i ) ∈ U n , k and T X i X i + 1 \mathcal{T}_{X_i}^{X_{i+1}} T X i X i + 1 , using SVD r ~ i = U i Θ i V i H \widetilde r_i = U_i\Theta_iV_i^H r i = U i Θ i V i H (see (34) , (36) )
end if
end for
higher-order terms in their distances, since the composition and direct parallel transports differ only by second-order terms due to manifold curvature; see also [50 ] .
Algorithm 4 outlines the Riemannian AA(m m m ). We highlight three implementation details.
(i) As is standard in computations on the Grassmannian (see, e.g., [1 , 2 , 13 ] ), we use Stiefel representatives X ∈ U n , k X \in\mathbb{U}^{n,k} X ∈ U n , k for X = range ( X ) ∈ G ( n , k ) \mathcal{X} = \operatorname{range}(X) \in\mathcal{G}(n,k) X = range ( X ) ∈ G ( n , k ) and represent tangent vectors by their unique horizontal lifts Δ ∈ C n , k \Delta\in\mathbb{C}^{n,k} Δ ∈ C n , k satisfying X H Δ = 0 X^H\Delta= 0 X H Δ = 0 . In particular, with these representations, the exponential map takes the closed-form
Exp X ( Δ ) = ( X V cos Θ + U sin Θ ) V H ∈ U n , k with SVD Δ = U Θ V H , (34) \operatorname{Exp}_X(\Delta) = (XV\cos\Theta+ U\sin\Theta)V^H \in\mathbb{U}^{n,k} \quad\text{with SVD } \Delta= U\Theta V^H, \tag*{(34)} Exp X ( Δ ) = ( X V cos Θ + U sin Θ ) V H ∈ U n , k with SVD Δ = U Θ V H , (34)
the logarithm map, for nonsingular X H Y X^HY X H Y , takes the form
Log X ( Y ) = U arctan ( Σ ) V H ∈ C n , k with SVD ( I − X X H ) Y ( X H Y ) − 1 = U Σ V H , (35) \operatorname{Log}_X(Y) = U\arctan(\Sigma)V^H \in\mathbb{C}^{n,k} \quad\text{with SVD } (I-XX^H)Y(X^HY)^{-1} = U\Sigma V^H, \tag*{(35)} Log X ( Y ) = U arctan ( Σ ) V H ∈ C n , k with SVD ( I − X X H ) Y ( X H Y ) − 1 = U Σ V H , (35)
and parallel transport takes the form
T X Y ( Δ ) = [ I + ( U ( cos Θ − I ) − X V sin Θ ) U H ] Δ ∈ C n , k with SVD Log X ( Y ) = U Θ V H . (36) \mathcal{T}_X^Y(\Delta) = \left[I + \left(U(\cos\Theta-I)-XV\sin\Theta\right)U^H\right]\Delta\in\mathbb{C}^{n,k} \quad\text{with SVD } \operatorname{Log}_X(Y) = U\Theta V^H. \tag*{(36)} T X Y ( Δ ) = [ I + ( U ( cos Θ − I ) − X V sin Θ ) U H ] Δ ∈ C n , k with SVD Log X ( Y ) = U Θ V H . (36)
We refer to [13 ] for details and the treatment of logarithms when X H Y X^HY X H Y is singular.
(ii) For computational efficiency, line 11 reuses the differences Δ X ℓ ( i − 1 ) , Δ r ℓ ( i − 1 ) ∈ T X i − 1 \Delta X_\ell^{(i-1)},\Delta r_\ell^{(i-1)} \in T_{X_{i-1}} Δ X ℓ ( i − 1 ) , Δ r ℓ ( i − 1 ) ∈ T X i − 1 from iteration i − 1 i-1 i − 1 by parallel transport to T X i T_{X_i} T X i . This amounts to approximating the direct transport in (31) by the composition T X ℓ X i ≈ T X i − 1 X i ∘ T X ℓ X i − 1 \mathcal{T}_{X_\ell}^{X_i} \approx\mathcal{T}_{X_{i-1}}^{X_i} \circ\mathcal{T}_{X_\ell}^{X_{i-1}} T X ℓ X i ≈ T X i − 1 X i ∘ T X ℓ X i − 1 . For nearby iterates, these transports agree to first order, and hence would not affect the local behavior of the algorithm. Since the same transport T X i − 1 X i \mathcal{T}_{X_{i-1}}^{X_i} T X i − 1 X i is applied to all stored differences, the computation via (36) requires only matrix multiplications after computing Log X i − 1 ( X i ) \operatorname{Log}_{X_{i-1}}(X_i) Log X i − 1 ( X i ) and its SVD once.
(iii) The least-squares problem in line 13 involves a potentially complex block matrix Δ R i \Delta R_i Δ R i but real coefficients β ( i ) \beta^{(i)} β ( i ) . It can be solved using the same techniques discussed for Algorithm 3, either by converting it to the real standard form (24) or by computing a block QR decomposition.
Basis-Aligned Newton Acceleration
In this section, we present a Newton-type acceleration scheme. Newton’s method for NEPv has been considered in [28 , 73 ] . One major issue is that the unitary invariance of NEPv leads to a singular derivative operator at a solution as noted in [73 ] . This singularity may cause numerical difficulties when solving the Newton correction equation. We address this issue through a correction scheme in which the updated basis aligns with the current basis X X X . This alignment is incorporated into the correction equation through the condition X H Δ X = 0 X^{H}\Delta X=0 X H Δ X = 0 to remove the ambiguity associated with basis rotations and yields a nonsingular correction equation under mild assumptions. We then combine the Newton correction with SCF to accelerate convergence towards desired eigenvalues and discuss its implementations. These developments complement previous work and provide further theoretical and algorithmic support for applying Newton’s method to NEPv.
Newton Correction for Aligned Basis of NEPv
Throughout this section, we assume that H H H is Fréchet differentiable with a locally Lipschitz continuous derivative in an open neighborhood of X ∈ U n , k X\in\mathbb{U}^{n,k} X ∈ U n , k , that is, there exists a linear derivative operator D H ( X ) [ ⋅ ] : C n , k → C n , n DH(X)[\cdot]:\mathbb{C}^{n,k}\to\mathbb{C}^{n,n} D H ( X ) [ ⋅ ] : C n , k → C n , n that is locally Lipschitz in X X X and satisfies
H ( X + E ) = H ( X ) + D H ( X ) [ E ] + O ( ∥ E ∥ 2 ) . (37) H(X+E)=H(X)+DH(X)[E]+O(\lVert E\rVert^{2}). \tag*{(37)} H ( X + E ) = H ( X ) + D H ( X ) [ E ] + O (∥ E ∥ 2 ) . (37)
Here, the complex matrix space C n , k \mathbb{C}^{n,k} C n , k is viewed as a vector space over R \mathbb{R} R (i.e., treat real and imaginary parts as individual variables), so the linearity really means R \mathbb{R} R -linearity:
D H ( X ) [ α 1 E 1 + α 2 E 2 ] = α 1 D H ( X ) [ E 1 ] + α 2 D H ( X ) [ E 2 ] , E 1 , E 2 ∈ C n , k , α 1 , α 2 ∈ R . (38) DH(X)[\alpha_{1}E_{1}+\alpha_{2}E_{2}]=\alpha_{1}DH(X)[E_{1}]+\alpha_{2}DH(X)[E_{2}],\qquad E_{1},E_{2}\in\mathbb{C}^{n,k},\quad\alpha_{1},\alpha_{2}\in\mathbb{R}. \tag*{(38)} D H ( X ) [ α 1 E 1 + α 2 E 2 ] = α 1 D H ( X ) [ E 1 ] + α 2 D H ( X ) [ E 2 ] , E 1 , E 2 ∈ C n , k , α 1 , α 2 ∈ R . (38)
We assume the derivative operator D H ( X ) [ ⋅ ] DH(X)[\cdot] D H ( X ) [ ⋅ ] is available in the sense that its action D H ( X ) [ E ] DH(X)[E] D H ( X ) [ E ] can be evaluated for any given direction E E E . Observe that this action coincides with the directional derivative
D H ( X ) [ E ] = d d t H ( X + t E ) ∣ t = 0 , t ∈ R , (39) DH(X)[E]=\left.\frac{d}{dt}H(X+tE)\right|_{t=0},\qquad t\in\mathbb{R}, \tag*{(39)} D H ( X ) [ E ] = d t d H ( X + tE ) t = 0 , t ∈ R , (39)
which provides a convenient expression for both derivation and computation.
Aligned Basis Correction
We consider the following correction scheme for the NEPv. Given a current approximate solution ( X , Λ ) ∈ U n , k × C k , k (X,\Lambda)\in\mathbb{U}^{n,k}\times\mathbb{C}^{k,k} ( X , Λ ) ∈ U n , k × C k , k of the NEPv (1), we seek the next approximation in the form
X n e x t = orth ( X + E ) , Λ n e x t = Λ + D , (40) X_{\mathrm{next}}=\operatorname{orth}(X+E),\qquad\Lambda_{\mathrm{next}}=\Lambda+D, \tag*{(40)} X next = orth ( X + E ) , Λ next = Λ + D , (40)
where the corrections ( E , D ) ∈ C n , k × C k , k (E,D)\in\mathbb{C}^{n,k}\times\mathbb{C}^{k,k} ( E , D ) ∈ C n , k × C k , k satisfy
X H E = 0 , (41) X^{H}E=0, \tag*{(41)} X H E = 0 , (41)
and orth ( ⋅ ) \operatorname{orth}(\cdot) orth ( ⋅ ) denotes the orthonormal polar factor of a full-column-rank matrix A A A , given by
orth ( A ) : = A ( A H A ) − 1 / 2 . (42) \operatorname{orth}(A):=A(A^{H}A)^{-1/2}. \tag*{(42)} orth ( A ) := A ( A H A ) − 1/2 . (42)
The motivation behind the update (36) is to seek an orthonormal basis X n e x t X_{\mathrm{next}} X next aligned with the current basis X X X , satisfying X H X n e x t ≻ 0 X^{H}X_{\mathrm{next}}\succ0 X H X next ≻ 0 ; see, e.g., § 3 . This removes the ambiguity in choosing a basis for the updated subspace. Moreover, each such aligned basis corresponds to a unique correction E E E satisfying X H E = 0 X^{H}E=0 X H E = 0 .
Lemma 6. Let X , Y ∈ U n , k X,Y\in\mathbb{U}^{n,k} X , Y ∈ U n , k . Then X H Y ≻ 0 X^{H}Y\succ0 X H Y ≻ 0 if and only if there exists a unique E ∈ C n , k E\in\mathbb{C}^{n,k} E ∈ C n , k satisfying X H E = 0 X^{H}E=0 X H E = 0 such that Y = orth ( X + E ) Y=\operatorname{orth}(X+E) Y = orth ( X + E ) .
Proof. If Y = orth ( X + E ) Y=\operatorname{orth}(X+E) Y = orth ( X + E ) with X H E = 0 X^{H}E=0 X H E = 0 , then
Y = ( X + E ) ( I + E H E ) − 1 / 2 and X H Y = ( I + E H E ) − 1 / 2 ≻ 0. (43) Y=(X+E)(I+E^{H}E)^{-1/2}\quad\text{and}\quad X^{H}Y=(I+E^{H}E)^{-1/2}\succ0. \tag*{(43)} Y = ( X + E ) ( I + E H E ) − 1/2 and X H Y = ( I + E H E ) − 1/2 ≻ 0. (43)
Conversely, let C : = X H Y ≻ 0 C:=X^{H}Y\succ0 C := X H Y ≻ 0 and E : = Y C − 1 − X E:=YC^{-1}-X E := Y C − 1 − X . Then, X H E = 0 X^{H}E=0 X H E = 0 and orth ( X + E ) = orth ( Y C − 1 ) = Y \operatorname{orth}(X+E)=\operatorname{orth}(YC^{-1})=Y orth ( X + E ) = orth ( Y C − 1 ) = Y . Uniqueness follows as any such E E E must satisfy (38), so Y = ( X + E ) X H Y Y=(X+E)X^{H}Y Y = ( X + E ) X H Y , i.e., E = Y ( X H Y ) − 1 − X E=Y(X^{H}Y)^{-1}-X E = Y ( X H Y ) − 1 − X . ▢
Newton Correction Equation
To solve the NEPv, an exact correction ( E , D ) (E,D) ( E , D ) in (36) would satisfy the nonlinear systems of equations
\begin{bmatrix}
H(X_{\mathrm{next}})X_{\mathrm{next}}-X_{\mathrm{next}}\Lambda_{\mathrm{next}}\\
-X^{H}E
\end{bmatrix}=0, \tag*{(44)}\end{bmatrix}
where the upper block represents the residual of the NEPv and the lower comes from the constraints (36b) (we negate the equation for convenience of later discussions). Rather than solving this equation exactly, we can obtain an approximate solution using a Newton correction by linearization. Since
X n e x t = ( X + E ) ( I + E H E ) − 1 / 2 = X + E + O ( ∥ E ∥ F 2 ) , X_{\mathrm{next}}=(X+E)(I+E^{H}E)^{-1/2}=X+E+\mathcal{O}(\lVert E\rVert_{F}^{2}), X next = ( X + E ) ( I + E H E ) − 1/2 = X + E + O (∥ E ∥ F 2 ) ,
it follows from the local expansion (33) of H ( X n e x t ) H(X_{\mathrm{next}}) H ( X next ) at X X X that
H ( X n e x t ) X n e x t − X n e x t Λ n e x t = H ( X ) X − X Λ + D H ( X ) [ E ] X + H ( X ) E − E Λ − X D + O ( ∥ E ∥ 2 + ∥ D ∥ 2 ) . H(X_{\mathrm{next}})X_{\mathrm{next}}-X_{\mathrm{next}}\Lambda_{\mathrm{next}}=H(X)X-X\Lambda+DH(X)[E]X+H(X)E-E\Lambda-XD+\mathcal{O}(\lVert E\rVert^{2}+\lVert D\rVert^{2}). H ( X next ) X next − X next Λ next = H ( X ) X − X Λ + D H ( X ) [ E ] X + H ( X ) E − E Λ − X D + O (∥ E ∥ 2 + ∥ D ∥ 2 ) .
Plugging into (39), and dropping the higher-order terms, yields the linear system in ( E , D ) (E,D) ( E , D ) :
L ( X , Λ ) [ E , D ] = − R ( X , Λ ) , (45) \mathcal{L}(X,\Lambda)[E,D]=-R(X,\Lambda), \tag*{(45)} L ( X , Λ ) [ E , D ] = − R ( X , Λ ) , (45)
where
L ( X , Λ ) [ E , D ] : = [ D H ( X ) [ E ] X + H ( X ) E − E Λ − X D − X H E ] , R ( X , Λ ) : = [ H ( X ) X − X Λ 0 ] . (46) \mathcal{L}(X,\Lambda)[E,D]:=
\begin{bmatrix}
DH(X)[E]X+H(X)E-E\Lambda-XD\\
-X^{H}E
\end{bmatrix},
\qquad
R(X,\Lambda):=
\begin{bmatrix}
H(X)X-X\Lambda\\
0
\end{bmatrix}. \tag*{(46)} L ( X , Λ ) [ E , D ] := [ D H ( X ) [ E ] X + H ( X ) E − E Λ − X D − X H E ] , R ( X , Λ ) := [ H ( X ) X − X Λ 0 ] . (46)
The correction operator L ( X , Λ ) [ ⋅ ] : C n , k × C k , k → C n , k × C k , k \mathcal{L}(X,\Lambda)[\cdot]:\mathbb{C}^{n,k}\times\mathbb{C}^{k,k}\to\mathbb{C}^{n,k}\times\mathbb{C}^{k,k} L ( X , Λ ) [ ⋅ ] : C n , k × C k , k → C n , k × C k , k is R \mathbb{R} R -linear and is nonsingular at a solution under mild assumptions, as discussed in § 4.2 .
Let us highlight three major benefits of the basis-aligned Newton correction equation (40) over the standard Newton approach in [28 , 73 ] (also described in Remark 1). First, basis alignment yields a correction operator that is nonsingular under suitable assumptions, as proved in § 4.2 , simplifying both the theoretical analysis and the numerical solution. Second, for NEPv arising from certain optimization problems, the correction operator is self-adjoint, allowing efficient iterative solvers with short recurrences (see Remark 2); This property generally does not hold for the standard Newton approach. Finally, the elementary derivation and subsequent analysis apply to both real and complex NEPv by treating derivatives and correction operators as R \mathbb{R} R -linear maps. This preserves the original matrix form of the correction equation, without explicitly separating complex variables into real and imaginary parts, as used in related works [39 , 40 ] .
Remark 1 (Standard Newton method). The correction equation (40) is intrinsically different from that obtained by applying the standard Newton method directly to the root-finding formulation of the NEPv:
F ( X , Λ ) = 0 with F ( X , Λ ) : = [ H ( X ) X − X Λ I k − X H X ] , (47) F(X,\Lambda)=0\quad\text{with}\quad F(X,\Lambda):=
\begin{bmatrix}
H(X)X-X\Lambda\\
I_k-X^{H}X
\end{bmatrix}, \tag*{(47)} F ( X , Λ ) = 0 with F ( X , Λ ) := [ H ( X ) X − X Λ I k − X H X ] , (47)
as considered in the real setting in [28 , 73 ] . Starting from X ∈ U n , k X\in\mathbb{U}^{n,k} X ∈ U n , k and Λ ∈ C k , k \Lambda\in\mathbb{C}^{k,k} Λ ∈ C k , k , a standard Newton step takes the form
[ X n e x t Λ n e x t ] = [ X Λ ] + [ E D ] , \begin{bmatrix}
X_{\mathrm{next}}\\
\Lambda_{\mathrm{next}}
\end{bmatrix}
=
\begin{bmatrix}
X\\
\Lambda
\end{bmatrix}
+
\begin{bmatrix}
E\\
D
\end{bmatrix}, [ X next Λ next ] = [ X Λ ] + [ E D ] ,
where the corrections E E E and D D D satisfy
L ^ ( X , Λ ) [ E , D ] = − R ( X , Λ ) , (48) \widehat{\mathcal{L}}(X,\Lambda)[E,D]=-R(X,\Lambda), \tag*{(48)} L ( X , Λ ) [ E , D ] = − R ( X , Λ ) , (48)
with the R \mathbb{R} R -linear operator L ^ ( X , Λ ) [ ⋅ ] : C n , k × C k , k → C n , k × C k , k \widehat{\mathcal{L}}(X,\Lambda)[\cdot]:\mathbb{C}^{n,k}\times\mathbb{C}^{k,k}\to\mathbb{C}^{n,k}\times\mathbb{C}^{k,k} L ( X , Λ ) [ ⋅ ] : C n , k × C k , k → C n , k × C k , k denoting the derivatives of F F F as given by
L ^ ( X , Λ ) [ E , D ] : = [ D H ( X ) [ E ] X + H ( X ) E − E Λ − X D − ( X H E + E H X ) ] . (49) \widehat{\mathcal{L}}(X,\Lambda)[E,D]:=
\begin{bmatrix}
DH(X)[E]X+H(X)E-E\Lambda-XD\\
-(X^{H}E+E^{H}X)
\end{bmatrix}. \tag*{(49)} L ( X , Λ ) [ E , D ] := [ D H ( X ) [ E ] X + H ( X ) E − E Λ − X D − ( X H E + E H X ) ] . (49)
Here we used F ( X , Λ ) = R ( X , Λ ) F(X,\Lambda)=R(X,\Lambda) F ( X , Λ ) = R ( X , Λ ) since X H X = I k X^{H}X=I_k X H X = I k . Compared with our correction equation (40), the standard Newton equation (42) uses X H E + E H X X^{H}E+E^{H}X X H E + E H X in the lower block instead of X H E X^{H}E X H E . This seemingly minor difference has an important consequence: the standard Newton operator L ^ ( X , Λ ) \widehat{\mathcal{L}}(X,\Lambda) L ( X , Λ ) is singular at a solution (see, e.g., [73 ] ), whereas our operator L ( X , Λ ) \mathcal{L}(X,\Lambda) L ( X , Λ ) is nonsingular under mild assumptions. The singularity of the standard Newton operator L ^ ( X , Λ ) \widehat{\mathcal{L}}(X,\Lambda) L ( X , Λ ) arises from unitary invariance of the NEPv: if ( X , Λ ) (X,\Lambda) ( X , Λ ) is a solution of (41), then ( X Q , Q H Λ Q ) (XQ,Q^{H}\Lambda Q) ( X Q , Q H Λ Q ) remains a solution for every unitary Q Q Q , so the solution is not locally unique and the derivative operator of F F F must be singular.
Local Convergence Analysis
In this section, we establish the local quadratic convergence of the update scheme (36) with corrections determined by (40). Following the framework for local NEPv analysis in [7 ] , consider a solution ( X ∗ , Λ ∗ ) ∈ U n , k × C k , k (X^{\ast},\Lambda^{\ast})\in\mathbb{U}^{n,k}\times\mathbb{C}^{k,k} ( X ∗ , Λ ∗ ) ∈ U n , k × C k , k of NEPv (1), with the eigenvalue decomposition
H ( X ∗ ) = [ X ∗ X ⊥ ∗ ] [ Λ ∗ Λ ⊥ ∗ ] [ X ∗ X ⊥ ∗ ] H , (51) H(X^{\ast})=[X^{\ast}\ \ X_{\perp}^{\ast}]
\begin{bmatrix}
\Lambda^{\ast} & \\
& \Lambda_{\perp}^{\ast}
\end{bmatrix}
[X^{\ast}\ \ X_{\perp}^{\ast}]^{H}, \tag*{(51)} H ( X ∗ ) = [ X ∗ X ⊥ ∗ ] [ Λ ∗ Λ ⊥ ∗ ] [ X ∗ X ⊥ ∗ ] H , (51)
where the columns of X ∗ X^{\ast} X ∗ are orthonormal eigenvectors associated with the k k k smallest eigenvalues of H ( X ∗ ) H(X^{\ast}) H ( X ∗ ) , and the columns of X ⊥ ∗ ∈ U n , n − k X_{\perp}^{\ast}\in\mathbb{U}^{n,n-k} X ⊥ ∗ ∈ U n , n − k form an orthonormal basis for the complementary invariant subspace. The diagonal matrices Λ ∗ ∈ C k , k \Lambda^{\ast}\in\mathbb{C}^{k,k} Λ ∗ ∈ C k , k and Λ ⊥ ∗ ∈ C n − k , n − k \Lambda_{\perp}^{\ast}\in\mathbb{C}^{n-k,n-k} Λ ⊥ ∗ ∈ C n − k , n − k contain the corresponding eigenvalues. We impose the following assumptions.
Assumption 1. (i) There is a positive eigengap: λ k ( H ( X ∗ ) ) < λ k + 1 ( H ( X ∗ ) ) \lambda_k(H(X^{\ast}))<\lambda_{k+1}(H(X^{\ast})) λ k ( H ( X ∗ )) < λ k + 1 ( H ( X ∗ )) .
(ii) H H H is Fréchet differentiable with a locally Lipschitz continuous derivative in a neighborhood of X ∗ X^{\ast} X ∗ .
(iii) The R \mathbb{R} R -linear operator Q ∗ : C n − k , k → C n − k , k Q^{\ast}:\mathbb{C}^{n-k,k}\to\mathbb{C}^{n-k,k} Q ∗ : C n − k , k → C n − k , k , defined by
Q ∗ ( Z ) = X ⊥ ∗ H D H ( X ∗ ) [ X ⊥ ∗ Z ] X ∗ + Λ ⊥ ∗ Z − Z Λ ∗ , (52) Q^{\ast}(Z)=X_{\perp}^{\ast H}DH(X^{\ast})[X_{\perp}^{\ast}Z]X^{\ast}+\Lambda_{\perp}^{\ast}Z-Z\Lambda^{\ast}, \tag*{(52)} Q ∗ ( Z ) = X ⊥ ∗ H D H ( X ∗ ) [ X ⊥ ∗ Z ] X ∗ + Λ ⊥ ∗ Z − Z Λ ∗ , (52) is self-adjoint and positive definite w.r.t. the Frobenius inner product ⟨ T , Z ⟩ = Re ( tr ( T H Z ) ) \langle T,Z\rangle=\operatorname{Re}(\operatorname{tr}(T^{H}Z)) ⟨ T , Z ⟩ = Re ( tr ( T H Z )) ; i.e.,
⟨ T , Q ∗ ( Z ) ⟩ = ⟨ Q ∗ ( T ) , Z ⟩ ⟨ Z , Q ∗ ( Z ) ⟩ > 0 , (53) \langle T,Q^{\ast}(Z)\rangle=\langle Q^{\ast}(T),Z\rangle\qquad\langle Z,Q^{\ast}(Z)\rangle>0, \tag*{(53)} ⟨ T , Q ∗ ( Z )⟩ = ⟨ Q ∗ ( T ) , Z ⟩ ⟨ Z , Q ∗ ( Z )⟩ > 0 , (53) for all T , Z ∈ C n − k , k T,Z\in\mathbb{C}^{n-k,k} T , Z ∈ C n − k , k , with Z ≠ 0 Z\ne0 Z = 0 in the second inequality.
Note that the eigengap and differentiability conditions in Assumption 1 (i) and (ii) are standard in the local analysis of NEPv and SCF iteration (e.g., [7 , 18 , 51 , 68 ] ). The positive-definiteness condition in Assumption 1 (iii) typically holds for practical NEPv arising in optimization on the Grassmann manifold, where it is related to second-order sufficient conditions for optimality and also implies that Q ∗ Q^{\ast} Q ∗ is invertible; see [7 ] for further discussion. Under these assumptions, we obtain the following result.
Theorem 1 (Local quadratic convergence). Let ( X ∗ , Λ ∗ ) ∈ U n , k × C k , k (X^*,\Lambda^*) \in\mathbb{U}^{n,k} \times\mathbb{C}^{k,k} ( X ∗ , Λ ∗ ) ∈ U n , k × C k , k be a solution of NEPv (1) satisfying Assumption 1. Then the following statements hold.
(a) The R \mathbb{R} R -linear operator L ( X ∗ , Λ ∗ ) [ ⋅ ] \mathcal{L}(X^*,\Lambda^*)[\cdot] L ( X ∗ , Λ ∗ ) [ ⋅ ] defined in (40b) is invertible on C n , k × C k , k \mathbb{C}^{n,k} \times\mathbb{C}^{k,k} C n , k × C k , k .
(b) Let X ∈ U n , k X \in\mathbb{U}^{n,k} X ∈ U n , k have a range space sufficiently close to range ( X ∗ ) \operatorname{range}(X^*) range ( X ∗ ) , and let Λ ∈ C k , k \Lambda\in\mathbb{C}^{k,k} Λ ∈ C k , k satisfy Λ = X H H ( X ) X + O ( ∥ Θ ( X , X ∗ ) ∥ ) \Lambda= X^H H(X)X + O(\lVert\Theta(X,X^*)\rVert) Λ = X H H ( X ) X + O (∥ Θ ( X , X ∗ )∥) . The update (36), with corrections determined by (40), satisfies
∥ Θ ( X n e x t , X ∗ ) ∥ = O ( ∥ Θ ( X , X ∗ ) ∥ 2 ) as ∥ Θ ( X , X ∗ ) ∥ → 0. (54) \lVert\Theta(X_{\mathrm{next}},X^*)\rVert= O(\lVert\Theta(X,X^*)\rVert^2) \quad\text{as} \quad\lVert\Theta(X,X^*)\rVert\to0. \tag*{(54)} ∥ Θ ( X next , X ∗ )∥ = O (∥ Θ ( X , X ∗ ) ∥ 2 ) as ∥ Θ ( X , X ∗ )∥ → 0. (54) Here, Θ ( X , Y ) \Theta(X,Y) Θ ( X , Y ) is the diagonal matrix of canonical angles between the subspaces range ( X ) \operatorname{range}(X) range ( X ) and range ( Y ) \operatorname{range}(Y) range ( Y ) , i.e., Θ ( X , Y ) = Diag ( arccos σ 1 , … , arccos σ k ) \Theta(X,Y) = \operatorname{Diag}(\arccos\sigma_1,\ldots,\arccos\sigma_k) Θ ( X , Y ) = Diag ( arccos σ 1 , … , arccos σ k ) with σ 1 ≥ ⋯ ≥ σ k \sigma_1 \ge\cdots\ge\sigma_k σ 1 ≥ ⋯ ≥ σ k being the singular values of X H Y X^H Y X H Y .
Proof. We first prove item (a). It suffices to show that L ( X ∗ , Λ ∗ ) \mathcal{L}(X^*,\Lambda^*) L ( X ∗ , Λ ∗ ) has a trivial null space. Let ( E , D ) (E,D) ( E , D ) be a null vector, that is, a solution of L ( X ∗ , Λ ∗ ) [ E , D ] = 0 \mathcal{L}(X^*,\Lambda^*)[E,D] = 0 L ( X ∗ , Λ ∗ ) [ E , D ] = 0 . By the definition of L \mathcal{L} L in (40b), this is equivalent to
\begin{bmatrix}
H(X^*)E + D H(X^*)[E]X^* - E\Lambda^* - X^*D \\
-X^{*H}E
\end{bmatrix}
= 0. \tag*{(55)}\end{bmatrix}
The lower block gives X ∗ H E = 0 X^{*H}E = 0 X ∗ H E = 0 , so E = X ⊥ ∗ Z E = X^*_\perp Z E = X ⊥ ∗ Z for some Z ∈ C n − k , k Z \in\mathbb{C}^{n-k,k} Z ∈ C n − k , k . Multiplying the upper block by X ⊥ ∗ H X^{*H}_\perp X ⊥ ∗ H from the left and substituting E = X ⊥ ∗ Z E = X^*_\perp Z E = X ⊥ ∗ Z , we obtain
0 = X ⊥ ∗ H H ( X ∗ ) X ⊥ ∗ Z + X ⊥ ∗ H D H ( X ∗ ) [ X ⊥ ∗ Z ] X ∗ − Z Λ ∗ = Q ∗ ( Z ) , (56) 0 = X^{*H}_\perp H(X^*)X^*_\perp Z + X^{*H}_\perp D H(X^*)[X^*_\perp Z]X^* - Z\Lambda^* = \mathcal{Q}^*(Z), \tag*{(56)} 0 = X ⊥ ∗ H H ( X ∗ ) X ⊥ ∗ Z + X ⊥ ∗ H D H ( X ∗ ) [ X ⊥ ∗ Z ] X ∗ − Z Λ ∗ = Q ∗ ( Z ) , (56)
where the last equality follows from X ⊥ ∗ H H ( X ∗ ) X ⊥ ∗ = Λ ⊥ ∗ X^{*H}_\perp H(X^*)X^*_\perp= \Lambda^*_\perp X ⊥ ∗ H H ( X ∗ ) X ⊥ ∗ = Λ ⊥ ∗ and the definition of Q ∗ \mathcal{Q}^* Q ∗ in (45). By Assumption 1 (iii), Q ∗ \mathcal{Q}^* Q ∗ is positive definite, so (49) implies Z = 0 Z = 0 Z = 0 . Substituting E = X ⊥ ∗ Z = 0 E = X^*_\perp Z = 0 E = X ⊥ ∗ Z = 0 into the upper block of (48) gives X ∗ D = 0 X^*D = 0 X ∗ D = 0 , hence D = 0 D = 0 D = 0 . Thus ( E , D ) = ( 0 , 0 ) (E,D) = (0,0) ( E , D ) = ( 0 , 0 ) , proving that L ( X ∗ , Λ ∗ ) \mathcal{L}(X^*,\Lambda^*) L ( X ∗ , Λ ∗ ) is invertible.
For item (b), we consider the exact corrections E ∗ ∈ C n , k E_* \in\mathbb{C}^{n,k} E ∗ ∈ C n , k and D ∗ ∈ C k , k D_* \in\mathbb{C}^{k,k} D ∗ ∈ C k , k that take ( X , Λ ) (X,\Lambda) ( X , Λ ) to the solution ( X ∗ , Λ ∗ ) (X^*,\Lambda^*) ( X ∗ , Λ ∗ ) through (36), that is,
X ∗ = orth ( X + E ∗ ) , Λ ∗ = Λ + D ∗ . (57) X^* = \operatorname{orth}(X + E_*), \qquad\Lambda^* = \Lambda+ D_*. \tag*{(57)} X ∗ = orth ( X + E ∗ ) , Λ ∗ = Λ + D ∗ . (57)
Here, we assume without loss of generality that the target solution X ∗ X^* X ∗ is aligned with the given basis X X X so that X H X ∗ ≻ 0 X^H X^* \succ0 X H X ∗ ≻ 0 ; see § 3 . Then a direct calculation gives
E ∗ ≡ X ∗ ( X H X ∗ ) − 1 − X = ( I − X X H ) X ∗ ( X H X ∗ ) − 1 = O ( ∥ Θ ( X , X ∗ ) ∥ ) , E_* \equiv X^*(X^H X^*)^{-1} - X = (I - XX^H)X^*(X^H X^*)^{-1} = O(\lVert\Theta(X,X^*)\rVert), E ∗ ≡ X ∗ ( X H X ∗ ) − 1 − X = ( I − X X H ) X ∗ ( X H X ∗ ) − 1 = O (∥ Θ ( X , X ∗ )∥) ,
where the bound follows from ∥ E ∗ ∥ = ∥ tan Θ ( X , X ∗ ) ∥ \lVert E_* \rVert= \lVert\tan\Theta(X,X^*) \rVert ∥ E ∗ ∥ = ∥ tan Θ ( X , X ∗ )∥ ; see, e.g., [79 ] . This also implies
D ∗ ≡ X ∗ H H ( X ∗ ) X ∗ − X H H ( X ) X + O ( ∥ Θ ( X , X ∗ ) ∥ ) = O ( ∥ Θ ( X , X ∗ ) ∥ ) , D_* \equiv X^{*H}H(X^*)X^* - X^H H(X)X + O(\lVert\Theta(X,X^*)\rVert) = O(\lVert\Theta(X,X^*)\rVert), D ∗ ≡ X ∗ H H ( X ∗ ) X ∗ − X H H ( X ) X + O (∥ Θ ( X , X ∗ )∥) = O (∥ Θ ( X , X ∗ )∥) ,
where the second equality is due to the smoothness of the Rayleigh quotient map X ↦ Λ : = X H H ( X ) X X \mapsto\Lambda:= X^H H(X)X X ↦ Λ := X H H ( X ) X , which implies the difference in Rayleigh quotient is O ( ∥ X ∗ − X ∥ ) = O ( ∥ E ∗ ∥ ) O(\lVert X^* - X\rVert) = O(\lVert E_* \rVert) O (∥ X ∗ − X ∥) = O (∥ E ∗ ∥) by (50). Now, following the derivation from (39) to (40), with ( X n e x t , Λ n e x t ) (X_{\mathrm{next}},\Lambda_{\mathrm{next}}) ( X next , Λ next ) replaced by ( X ∗ , Λ ∗ ) (X^*,\Lambda^*) ( X ∗ , Λ ∗ ) and retaining the higher-order terms, we obtain
L ( X , Λ ) [ E ∗ , D ∗ ] + R ( X , Λ ) = O ( ∥ E ∗ ∥ 2 + ∥ D ∗ ∥ 2 ) = O ( ∥ Θ ( X , X ∗ ) ∥ 2 ) . \mathcal{L}(X,\Lambda)[E_*,D_*] + R(X,\Lambda) = O(\lVert E_* \rVert^2 + \lVert D_* \rVert^2) = O(\lVert\Theta(X,X^*)\rVert^2). L ( X , Λ ) [ E ∗ , D ∗ ] + R ( X , Λ ) = O (∥ E ∗ ∥ 2 + ∥ D ∗ ∥ 2 ) = O (∥ Θ ( X , X ∗ ) ∥ 2 ) .
Recalling R ( X , Λ ) = − L ( X , Λ ) [ E , D ] R(X,\Lambda) = -\mathcal{L}(X,\Lambda)[E,D] R ( X , Λ ) = − L ( X , Λ ) [ E , D ] from the equation (40a) for the correction ( E , D ) (E,D) ( E , D ) , we obtain
L ( X , Λ ) [ E ∗ , D ∗ ] − L ( X , Λ ) [ E , D ] = O ( ∥ Θ ( X , X ∗ ) ∥ 2 ) . (58) \mathcal{L}(X,\Lambda)[E_*,D_*] - \mathcal{L}(X,\Lambda)[E,D] = O(\lVert\Theta(X,X^*)\rVert^2). \tag*{(58)} L ( X , Λ ) [ E ∗ , D ∗ ] − L ( X , Λ ) [ E , D ] = O (∥ Θ ( X , X ∗ ) ∥ 2 ) . (58)
Observe that the linear operator L ( X , Λ ) \mathcal{L}(X,\Lambda) L ( X , Λ ) is Lipschitz continuous in a neighborhood of ( X ∗ , Λ ∗ ) (X^*,\Lambda^*) ( X ∗ , Λ ∗ ) . Its invertibility at ( X ∗ , Λ ∗ ) (X^*,\Lambda^*) ( X ∗ , Λ ∗ ) in item (a) therefore implies that it remains invertible, with a uniformly bounded inverse, in a sufficiently small neighborhood of the solution. Applying this inverse to (51) gives
( E ∗ , D ∗ ) − ( E , D ) = O ( ∥ Θ ( X , X ∗ ) ∥ 2 ) . (E_*,D_*) - (E,D) = O(\lVert\Theta(X,X^*)\rVert^2). ( E ∗ , D ∗ ) − ( E , D ) = O (∥ Θ ( X , X ∗ ) ∥ 2 ) .
Hence, it follows from the update formulas (36) and (50)
X n e x t − X ∗ = orth ( X + E ) − orth ( X + E ∗ ) = O ( E − E ∗ ) = O ( ∥ Θ ( X , X ∗ ) ∥ 2 ) , X_{\mathrm{next}} - X^* = \operatorname{orth}(X + E) - \operatorname{orth}(X + E_*) = O(E - E_*) = O(\lVert\Theta(X,X^*)\rVert^2), X next − X ∗ = orth ( X + E ) − orth ( X + E ∗ ) = O ( E − E ∗ ) = O (∥ Θ ( X , X ∗ ) ∥ 2 ) ,
where the second equality is due to the continuity of the polar-factor orth ( ⋅ ) \operatorname{orth}(\cdot) orth ( ⋅ ) . Consequently, we must also have the geodesic distance ∥ Θ ( X n e x t , X ∗ ) ∥ = O ( ∥ Θ ( X , X ∗ ) ∥ 2 ) \lVert\Theta(X_{\mathrm{next}},X^*)\rVert= O(\lVert\Theta(X,X^*)\rVert^2) ∥ Θ ( X next , X ∗ )∥ = O (∥ Θ ( X , X ∗ ) ∥ 2 ) , which completes the proof. ∎
SCF Iteration with Basis-Aligned Newton Acceleration
Algorithm 5 outlines an SCF iteration combined with the Newton acceleration developed in Section 3.1. Each iteration first computes an SCF iterate and then refines it by a Newton correction. The SCF step serves to target the desired eigenvalues: the governing equation (44) does not distinguish the k k k smallest eigenvalues from other sets of k k k eigenvalues, so Newton’s method alone may converge to an undesired solution. By selecting the k k k smallest eigenvalues at each iteration, the SCF step helps direct the iteration toward the desired invariant subspace. For simplicity, the algorithm applies a Newton correction at every iteration; in practice, one may activate Newton acceleration only after the residual norm falls below a prescribed threshold, since its convergence guarantee is local.
Algorithm 5 SCF with basis-aligned Newton acceleration
Input: Initial X 0 ∈ U n , k X_0 \in\mathbb{U}^{n,k} X 0 ∈ U n , k , matrix function H H H and its derivative D H \mathbf{D}H D H , residual tolerance τ > 0 \tau> 0 τ > 0 .
Output: approximate eigenbasis X ∗ ∈ U n , k X^* \in\mathbb{U}^{n,k} X ∗ ∈ U n , k of the NEPv (1)
for i = 0 , 1 , 2 , … i = 0, 1, 2, \ldots i = 0 , 1 , 2 , … do
Evaluate H i = H ( X i ) H_i = H(X_i) H i = H ( X i )
Solve H i Y i = Y i Λ i H_iY_i = Y_i\Lambda_i H i Y i = Y i Λ i for the k k k smallest eigenvalues in Λ i \Lambda_i Λ i
Evaluate H ^ i = H ( Y i ) \widehat{H}_i = H(Y_i) H i = H ( Y i ) and the residual R i = H ^ i Y i − Y i Λ i R_i = \widehat{H}_iY_i - Y_i\Lambda_i R i = H i Y i − Y i Λ i
if ∥ R i ∥ F ≤ τ \lVert R_i\rVert_F \le\tau ∥ R i ∥ F ≤ τ , then return X ∗ = Y i X^* = Y_i X ∗ = Y i
Compute ( E i , D i ) (E_i, D_i) ( E i , D i ) by solving L ( Y i , Λ i ) [ E i , D i ] = − [ R i 0 ] \mathcal{L}(Y_i,\Lambda_i)[E_i,D_i] = -\begin{bmatrix} R_i \\ 0 \end{bmatrix} L ( Y i , Λ i ) [ E i , D i ] = − [ R i 0 ]
Compute X i + 1 = orth ( Y i + E i ) X_{i+1} = \operatorname{orth}(Y_i + E_i) X i + 1 = orth ( Y i + E i )
end for
Remark 3. The linear system in line 6 of Algorithm 5 can be solved inexactly by an R \mathbb{R} R -linear global GMRES method with the Frobenius inner product ⟨ A , B ⟩ = Re ( tr ( A H B ) ) \langle A,B\rangle= \operatorname{Re}(\operatorname{tr}(A^H B)) ⟨ A , B ⟩ = Re ( tr ( A H B )) [23 , 37 , 41 ] . This is essentially the GMRES method, but with the solution ( E , D ) (E,D) ( E , D ) represented as a block matrix [ E H D H ] H ∈ C n + k , k \begin{bmatrix} E^H & D^H \end{bmatrix}^H \in\mathbb{C}^{n+k,k} [ E H D H ] H ∈ C n + k , k instead of its vectorization as a long column vector. In particular, starting with the initial basis matrix V 1 = − [ R i H , 0 k , k H ] H / ∥ R i ∥ F V_1 = -[R_i^H,0_{k,k}^H]^H/\lVert R_i\rVert_F V 1 = − [ R i H , 0 k , k H ] H / ∥ R i ∥ F , the Arnoldi process generates V j = [ V 1 , … , V j ] V_j = [V_1,\ldots,V_j] V j = [ V 1 , … , V j ] , whose column blocks V ℓ ∈ C n + k , k V_\ell\in\mathbb{C}^{n+k,k} V ℓ ∈ C n + k , k are orthonormal with respect to ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ and satisfy
L ( Y i , Λ i ) [ V j ] = V j + 1 ( H j ⊗ I k ) , (59) \mathcal{L}(Y_i,\Lambda_i)[V_j] = V_{j+1}(H_j \otimes I_k), \tag*{(59)} L ( Y i , Λ i ) [ V j ] = V j + 1 ( H j ⊗ I k ) , (59)
where the operator on the left acts on each column block and H j ∈ R j + 1 , j H_j \in\mathbb{R}^{j+1,j} H j ∈ R j + 1 , j is an upper Hessenberg matrix. The approximate solution is given by V j ( y j ⊗ I k ) V_j(y_j \otimes I_k) V j ( y j ⊗ I k ) , with y j ∈ R j y_j \in\mathbb{R}^j y j ∈ R j solving min y j ∥ R i ∥ F e 1 − H j y j ∥ 2 \min_{y_j}\lVert R_i\rVert_F e_1 - H_j y_j\rVert_2 min y j ∥ R i ∥ F e 1 − H j y j ∥ 2 . Restarting may be applied to limit storage and orthogonalization costs, and the iteration stops once the residual of the R \mathbb{R} R -linear system is below a tolerance chosen according to standard techniques for inexact Newton methods, such as the Eisenstat-Walker adaptive forcing strategy; see, e.g., [24 , 25 , 62 ] . Note that GMRES requires only operator actions, so there is no need to construct a matrix representation of L ( Y i , Λ i ) \mathcal{L}(Y_i,\Lambda_i) L ( Y i , Λ i ) explicitly. When these operator actions are expensive due to the derivative D H \mathbf{D}H D H , preconditioning may reduce the number of derivative evaluations. Using the splitting
L ( X , Λ ) [ E , D ] = [ H ( X ) − X − X H 0 ] [ E D ] − [ E D ] Λ + [ D H ( X ) [ E ] X D Λ ] , (60) \mathcal{L}(X,\Lambda)[E,D] =
\begin{bmatrix}
H(X) & -X \\
-X^H & 0
\end{bmatrix}
\begin{bmatrix}
E \\
D
\end{bmatrix}
-
\begin{bmatrix}
E \\
D
\end{bmatrix}
\Lambda
+
\begin{bmatrix}
\mathbf{D}H(X)[E]X \\
D\Lambda
\end{bmatrix}, \tag*{(60)} L ( X , Λ ) [ E , D ] = [ H ( X ) − X H − X 0 ] [ E D ] − [ E D ] Λ + [ D H ( X ) [ E ] X D Λ ] , (60)
we approximate
L ( Y i , Λ i ) [ E , D ] ≈ S i [ Z ] : = [ H ^ i − Y i − Y i H 0 ] Z − Z Λ i , Z = [ E D ] ∈ C n + k , k . (61) \mathcal{L}(Y_i,\Lambda_i)[E,D] \approx\mathcal{S}_i[Z] := \begin{bmatrix}
\widehat{H}_i & -Y_i \\
-Y_i^H & 0
\end{bmatrix} Z - Z\Lambda_i,\qquad
Z = \begin{bmatrix}
E \\
D
\end{bmatrix} \in\mathbb{C}^{n+k,k}. \tag*{(61)} L ( Y i , Λ i ) [ E , D ] ≈ S i [ Z ] := [ H i − Y i H − Y i 0 ] Z − Z Λ i , Z = [ E D ] ∈ C n + k , k . (61)
Since S i \mathcal{S}_i S i is a Hermitian Sylvester operator, a few steps of global MINRES applied to S i [ Z ] = V \mathcal{S}_i[Z] = V S i [ Z ] = V provide an approximate inverse preconditioner without D H \mathbf{D}H D H . In this case, the preconditioner is implicit and may change between iterations, making flexible right-preconditioned GMRES a suitable choice; see, e.g., [61 , 62 ] . Note that even when L ( X , Λ ) \mathcal{L}(X,\Lambda) L ( X , Λ ) is self-adjoint and MINRES can be applied directly, preconditioned GMRES may still be beneficial by reducing the number of expensive D H ( X ) \mathbf{D}H(X) D H ( X ) evaluations, since applying the preconditioner S i − 1 \mathcal{S}_i^{-1} S i − 1 does not require this derivative.
Numerical Experiments
We demonstrate the convergence behavior and the effectiveness of the acceleration techniques proposed in previous sections. For a set of NEPv, we compare the plain SCF (3) with its accelerated variants. These include several versions of AA(m m m ), with a fixed window size m ∈ N m \in\mathbb{N} m ∈ N , as well as the basis-aligned Newton acceleration:
AA(m m m )–X: AA(m m m ) applied directly to { X i } \{X_i\} { X i } by SCF, i.e., Algorithm 1 with g g g given by (5) ;
AA(m m m )–ρ \rho ρ : AA(m m m ) for a problem-specific ui-parameterization ρ ( X ) \rho(X) ρ ( X ) in Algorithm 2;
AA(m m m )–[ [ X ] ] [\![X]\!] [ [ X ] ] : AA(m m m ) for aligned basis { [ [ X i ] ] M } \{[\![X_i]\!]_M\} {[ [ X i ] ] M } with a common M ∈ U n , k M \in\mathbb{U}^{n,k} M ∈ U n , k in Algorithm 3.3
AA(m m m )-Gr: the Riemannian version of AA(m m m ) in Algorithm 4;
AlignNT: the basis-aligned Newton acceleration in Algorithm 5, with the adaptive forcing [25 ] .
For the SCF step in each algorithm, we use MATLAB’s built-in function eig or eigs to compute the desired eigenpairs of the Hermitian matrix H ( X i ) H(X_i) H ( X i ) . We measure the accuracy of an approximate solution X ^ ∈ U n , k \widehat{X} \in\mathbb{U}^{n,k} X ∈ U n , k using the residual norm
Res d ( X ^ ) : = ∥ H ( X ^ ) X ^ − X ^ Λ ^ ∥ F with Λ ^ = X ^ H H ( X ^ ) X ^ . (62) \operatorname{Res}_d(\widehat{X}) := \lVert H(\widehat{X})\widehat{X} - \widehat{X}\widehat{\Lambda}\rVert_F \quad\text{with} \quad\widehat{\Lambda} = \widehat{X}^{H}H(\widehat{X})\widehat{X}. \tag*{(62)} Res d ( X ) := ∥ H ( X ) X − X Λ ∥ F with Λ = X H H ( X ) X . (62)
All methods use the common stopping criterion Res d ( X i ) ≤ 10 − 14 \operatorname{Res}_d(X_i) \le10^{-14} Res d ( X i ) ≤ 1 0 − 14 , unless otherwise specified.
All experiments are performed using MATLAB 2024b on a laptop with AMD Ryzen 7 PRO 4750U CPU and 32GB RAM. The code used to reproduce the numerical experiments in this paper is available at https://github.com/towerner/Local-acceleration-for-uiNEPv.
Model Kohn-Sham Problem
We consider a model Kohn–Sham NEPv
H ( X ) X = X Λ with H ( X ) : = L + γ Diag ( L − 1 ρ ( X ) ) , ρ ( X ) : = diag ( X X T ) , (63) H(X)X = X\Lambda\quad\text{with} \quad H(X) := L + \gamma\operatorname{Diag}(L^{-1}\rho(X)), \quad\rho(X) := \operatorname{diag}(XX^{T}), \tag*{(63)} H ( X ) X = X Λ with H ( X ) := L + γ Diag ( L − 1 ρ ( X )) , ρ ( X ) := diag ( X X T ) , (63)
where L = tridiag ( − 1 , 2 , − 1 ) ∈ R n , n L = \operatorname{tridiag}(-1,2,-1) \in\mathbb{R}^{n,n} L = tridiag ( − 1 , 2 , − 1 ) ∈ R n , n is a discrete 1D Laplacian, γ ≥ 0 \gamma\ge0 γ ≥ 0 is a given parameter, and the eigenvalues of Λ ∈ R k , k \Lambda\in\mathbb{R}^{k,k} Λ ∈ R k , k are the k k k smallest eigenvalues of H ( X ) H(X) H ( X ) . This simplified Kohn–Sham model omits the external potential in the Hamiltonian H ( X ) H(X) H ( X ) (see Example 1) while retaining its nonlinear dependence on the charge-density ρ ( X ) \rho(X) ρ ( X ) . The parameter γ \gamma γ controls the strength of the nonlinearity of H ( X ) H(X) H ( X ) . By varying γ \gamma γ , the NEPv (63) provides a convenient test problem for studying SCF convergence and has been widely used as a benchmark in previous work; see, e.g., [7 , 17 , 51 , 74 ] .
The NEPv (63) admits a natural ui-parameterization through the density ρ ( X ) = diag ( X X T ) ∈ R n \rho(X) = \operatorname{diag}(XX^{T}) \in\mathbb{R}^{n} ρ ( X ) = diag ( X X T ) ∈ R n . Moreover, the Hamiltonian H H H is Fréchet differentiable with the derivative operator given by
D H [ X ] ( E ) = 2 γ Diag ( L − 1 diag ( E X T ) ) , (64) DH[X](E) = 2\gamma\operatorname{Diag}\left(L^{-1}\operatorname{diag}(EX^{T})\right), \tag*{(64)} D H [ X ] ( E ) = 2 γ Diag ( L − 1 diag ( E X T ) ) , (64)
which allows convenient application of the basis-aligned Newton acceleration in Algorithm 5.
Effectiveness of Acceleration
We first demonstrate the effectiveness of the proposed acceleration techniques. For experiments, we consider test NEPv (63) of size n = 200 n = 200 n = 200 , k = 2 k = 2 k = 2 , and parameters γ = γ 0 n 2 \gamma= \frac{\gamma_0}{n^2} γ = n 2 γ 0 for γ 0 ∈ { 2 , 4 , 7 } \gamma_0 \in\{2,4,7\} γ 0 ∈ { 2 , 4 , 7 } . We apply SCF iteration and the accelerated variants with a common initial guess X 0 ∈ R n , k X_0 \in\mathbb{R}^{n,k} X 0 ∈ R n , k , chosen as the eigenbasis for the k k k smallest eigenvalues of L L L . For AA, we use a fixed window size m = 2 m = 2 m = 2 . Because the NEPv is relatively small, we solve the eigenvalue problem in each SCF step using the dense solver eig. We also solve the Newton equation in line 6 of Algorithm 5 to numerical precision using unprestarted GMRES with a maximum of ( n + k ) k (n+k)k ( n + k ) k iterations. Convergence histories of the algorithms are reported in Figure 1 .
Figure 1. Convergence histories of the algorithms for the 1D Kohn–Sham NEPv (56) with n = 200 n=200 n = 200 , k = 2 k=2 k = 2 , and γ 0 = 2 , 4 , 7 \gamma_0=2,4,7 γ 0 = 2 , 4 , 7 (left, middle, and right).
We observe that the convergence of SCF becomes increasingly slow as γ \gamma γ increases, highlighting the need for acceleration. Direct application of AA(m m m ) to the iterates { X i } \{X_i\} { X i } fails to converge in all three cases, illustrating the difficulty caused by the non-uniqueness of the basis under rotations. In contrast, the three proposed variants of AA(m m m ), based on the ui-parameterization ρ ( X ) \rho(X) ρ ( X ) , the aligned basis [ X ] M [X]_{\mathcal{M}} [ X ] M , and the Grassmannian formulation, all address this ambiguity and significantly accelerate SCF. These variants exhibit comparable convergence behavior, requiring similar numbers of iterations. Basis-aligned Newton acceleration exhibits quadratic convergence in all three cases, reaching the prescribed accuracy in at most seven iterations.
Nonsingularity and Preconditioning of the Basis-Aligned Newton Equation
Next we consider the nonsingularity of the correction operator in the basis-aligned Newton equation (40), with its advantages over the standard Newton formulation for NEPv [28 , 73 ] and the effectiveness of the preconditioning strategy described in Remark 3. We use the model problem (56) with γ 0 = 7 \gamma_0=7 γ 0 = 7 . Let X ^ ∈ R n , k \widehat{X}\in\mathbb{R}^{n,k} X ∈ R n , k be a computed solution (∥ X ^ T X ^ − I k ∥ ≤ 10 − 15 \lVert\widehat{X}^{T}\widehat{X}-I_k\rVert\leq10^{-15} ∥ X T X − I k ∥ ≤ 1 0 − 15 , residual normal satisfying Resd ( X ^ ) ≤ 10 − 14 \operatorname{Resd}(\widehat{X})\leq10^{-14} Resd ( X ) ≤ 1 0 − 14 ) and set Λ ^ = X ^ T H ( X ^ ) X ^ \widehat{\Lambda}=\widehat{X}^{T}H(\widehat{X})\widehat{X} Λ = X T H ( X ) X . The condition numbers of the correction operators L ( X , Λ ^ ) \mathcal{L}(X,\widehat{\Lambda}) L ( X , Λ ) and L ^ ( X , Λ ^ ) \widehat{\mathcal{L}}(X,\widehat{\Lambda}) L ( X , Λ ) , corresponding to the basis-aligned Newton (40) and standard Newton (42), respectively, are4 ^{4} 4
κ ( L ( X ^ , Λ ^ ) ) = 2.25 × 10 3 and κ ( L ^ ( X ^ , Λ ^ ) ) = 1.68 × 10 16 . (65) \kappa(\mathcal{L}(\widehat{X},\widehat{\Lambda}))=2.25\times10^{3}\qquad\text{and}\qquad\kappa(\widehat{\mathcal{L}}(\widehat{X},\widehat{\Lambda}))=1.68\times10^{16}. \tag*{(65)} κ ( L ( X , Λ )) = 2.25 × 1 0 3 and κ ( L ( X , Λ )) = 1.68 × 1 0 16 . (65)
These values indicate that L ( X ^ , Λ ^ ) \mathcal{L}(\widehat{X},\widehat{\Lambda}) L ( X , Λ ) is numerically nonsingular, consistent with the analysis in Theorem 1, while L ^ ( X ^ , Λ ^ ) \widehat{\mathcal{L}}(\widehat{X},\widehat{\Lambda}) L ( X , Λ ) is numerically singular, as previously observed in [73 ] .
To demonstrate how this singularity affects the solution of the Newton correction equations near convergence, we consider the perturbed solutions of a perturbation size ϵ \epsilon ϵ :
X ϵ : = orth ( X ^ + ϵ P ) , ϵ ∈ { 10 − 8 , 10 − 10 , 10 − 12 , 10 − 14 } , (66) X_{\epsilon}:=\operatorname{orth}(\widehat{X}+\epsilon P),\qquad\epsilon\in\{10^{-8},10^{-10},10^{-12},10^{-14}\}, \tag*{(66)} X ϵ := orth ( X + ϵ P ) , ϵ ∈ { 1 0 − 8 , 1 0 − 10 , 1 0 − 12 , 1 0 − 14 } , (66)
where P ∈ R n , k P\in\mathbb{R}^{n,k} P ∈ R n , k is a Gaussian random matrix (generated using MATLAB’s randn(n,k)). For each X ϵ X_{\epsilon} X ϵ , we set Λ ϵ = X ϵ T H ( X ϵ ) X ϵ \Lambda_{\epsilon}=X_{\epsilon}^{T}H(X_{\epsilon})X_{\epsilon} Λ ϵ = X ϵ T H ( X ϵ ) X ϵ and apply non-restarted GMRES to the corresponding correction equations (40) and (42), respectively, where the relative convergence tolerance is set to τ = 10 − 14 \tau=10^{-14} τ = 1 0 − 14 . The convergence histories are shown in the left and middle panels of Figure 2 . Note that, in theory, an exact solution should be contained in the Krylov subspace of size ( n + k ) k = 404 (n+k)k=404 ( n + k ) k = 404 . For the standard Newton equation (42), GMRES stagnates, consistent with the ill-conditioning of the correction operator near a solution. In particular, the condition numbers of the systems are between 1.7 × 10 16 1.7\times10^{16} 1.7 × 1 0 16 to 2.1 × 10 17 2.1\times10^{17} 2.1 × 1 0 17 across all tests. In contrast, GMRES converges without stagnation for the basis-aligned Newton equation (40), with little variation in convergence behavior across the four perturbation sizes. The condition numbers are almost constant at around 2.25 × 10 3 2.25\times10^{3} 2.25 × 1 0 3 across all different perturbations.
Figure 2. Residual histories for the Newton correction equations near a solution: GMRES for standard Newton (42) (left), GMRES for basis-aligned Newton (40) (middle), and flexible GMRES for basis-aligned Newton with MINRES preconditioning (right). The curves correspond to different perturbation sizes ε \varepsilon ε .
Finally, the right panel of Figure 2 shows the convergence histories of flexible GMRES for the basis-aligned Newton equation (40), using the preconditioning strategy described in Remark 3. Each application of the preconditioner approximately solves S i − 1 S_i^{-1} S i − 1 by performing 40 steps of MINRES on the Sylvester equation (54). Compared with the unpreconditioned solves as shown in the middle panel, preconditioning reduces the number of outer iterations by approximately a factor of ten across all four values of ε \varepsilon ε . The corresponding computation time decreases from approximately 0.22 to 0.045 seconds. These results suggest that the proposed preconditioner can substantially improve the efficiency of solving the basis-aligned Newton equation.
Gross-Pitaevskii NEPv
Consider a discrete Gross–Pitaevskii NEPv in the form of
H ( x ) x = λ x with H ( x ) : = A f + γ Diag ( ∣ x ∣ 2 ) , (67) H(x)x = \lambda x \quad\text{with} \quad H(x) := A_f + \gamma\operatorname{Diag}(|x|^2), \tag*{(67)} H ( x ) x = λ x with H ( x ) := A f + γ Diag ( ∣ x ∣ 2 ) , (67)
where x ∈ C n x \in\mathbb{C}^n x ∈ C n satisfies ∥ x ∥ 2 = 1 \lVert x\rVert_2 = 1 ∥ x ∥ 2 = 1 , ∣ x ∣ |x| ∣ x ∣ denotes entry-wise absolute value, γ ≥ 0 \gamma\ge0 γ ≥ 0 is a given parameter, and λ \lambda λ is the smallest eigenvalue of H ( x ) H(x) H ( x ) . The constant Hermitian matrix A f ∈ C n , n A_f \in\mathbb{C}^{n,n} A f ∈ C n , n is given by
A f : = − 1 2 L 2 D − i ω L C + Diag ( v f ) , (68) A_f := -\frac{1}{2}L_{2D} - \mathrm{i}\omega L_C + \operatorname{Diag}(v_f), \tag*{(68)} A f := − 2 1 L 2 D − i ω L C + Diag ( v f ) , (68)
where L 2 D , L C ∈ R n , n L_{2D}, L_C \in\mathbb{R}^{n,n} L 2 D , L C ∈ R n , n are central-difference discretizations of the two-dimensional Laplacian and the angular derivative, respectively, on Ω = [ − 1 , 1 ] 2 \Omega= [-1,1]^2 Ω = [ − 1 , 1 ] 2 , using N = n N = \sqrt{n} N = n interior grid points in each coordinate direction, i \mathrm{i} i denotes the imaginary unit, ω ≥ 0 \omega\ge0 ω ≥ 0 is the rotation parameter, and v f ∈ R n v_f \in\mathbb{R}^n v f ∈ R n contains the values of an external potential f : R 2 → R f : \mathbb{R}^2 \to\mathbb{R} f : R 2 → R at the grid points. The Gross–Pitaevskii NEPv arises in the study of rotating Bose–Einstein condensates; see, e.g., [10 , 11 , 34 ] . The parameters γ \gamma γ and ω \omega ω control the strength of the nonlinear interaction and the rotation, respectively. For details of the discretization (61), we refer to [7 , 39 ] .
The solution of the NEPv (60) is a single eigenvector x x x , which is generally complex, x ∈ C n x \in\mathbb{C}^n x ∈ C n , since H ( x ) H(x) H ( x ) is Hermitian. Nevertheless, the non-uniqueness issue for the iterates { x i } \{x_i\} { x i } of the SCF iteration (3) persists, as each eigenvector x i x_i x i is only determined up to a phase rotation x i α x_i\alpha x i α with α ∈ C \alpha\in\mathbb{C} α ∈ C and ∣ α ∣ = 1 |\alpha| = 1 ∣ α ∣ = 1 . Hence, the techniques introduced in Sections 2 and 3 are still needed to effectively accelerate the SCF iteration. By the definition (60), the Hamiltonian H ( x ) H(x) H ( x ) admits a straightforward ui-parameterization
ρ ( x ) = ∣ x ∣ 2 ∈ R n . (69) \rho(x) = |x|^2 \in\mathbb{R}^n. \tag*{(69)} ρ ( x ) = ∣ x ∣ 2 ∈ R n . (69)
Moreover, H H H is Fréchet differentiable over the underlying real vector space, with derivative
D H ( x ) [ e ] = 2 γ Diag ( Re ( x ‾ ∘ e ) ) , (70) DH(x)[e] = 2\gamma\operatorname{Diag}\left(\operatorname{Re}(\overline{x} \circ e)\right), \tag*{(70)} D H ( x ) [ e ] = 2 γ Diag ( Re ( x ∘ e ) ) , (70)
where ∘ \circ ∘ denotes the Hadamard product (entry-wise product) and x ‾ \overline{x} x is the conjugate vector.
For the experiments, we consider a relatively large-size NEPv (60) with n = 10,000 n = 10{,}000 n = 10 , 000 , ω = 0.85 \omega= 0.85 ω = 0.85 , and the harmonic potential f ( ξ , η ) = ( ξ 2 + η 2 ) / 2 f(\xi,\eta) = (\xi^2 + \eta^2)/2 f ( ξ , η ) = ( ξ 2 + η 2 ) /2 , following a setup in [7 , 39 ] . Since n n n is relatively large, we use MATLAB’s iterative solver eigs to solve the Hermitian eigenvalue problem H ( x i ) x = λ x H(x_i)x = \lambda x H ( x i ) x = λ x in each SCF step. For computational efficiency, we warm-start eigs with the current iterate x i x_i x i . For the Newton-type acceleration in Algorithm 5, we use an inexact Newton implementation: the correction equation is solved approximately by flexible GMRES with a maximum Krylov subspace dimension of 100, using 100 MINRES steps for each preconditioner application; see Remark 3.
Figure 3. Convergence histories of the algorithms for the Gross–Pitaevskii NEPv (67) with n = 10 , 000 n = 10,000 n = 10 , 000 and γ = 4 , 5.5 , 7.2 \gamma= 4,5.5,7.2 γ = 4 , 5.5 , 7.2 (left, middle, and right). We use window size m = 4 m = 4 m = 4 for A A ( m ) \mathrm{AA}(m) AA ( m ) . For AA-x i x_i x i , results are shown with both warm-started (labeled w w w ) and randomly initialized (labeled r r r ) eigs runs for SCF steps.
Table 1 (PDF p. 22). Computation times (seconds) for the Gross–Pitaevskii NEPv (67) with sizes n ∈ { 10 , 000 , 40 , 000 } n \in\{10,000,40,000\} n ∈ { 10 , 000 , 40 , 000 } and parameters γ ∈ { 4 , 5.5 , 7.2 } \gamma\in\{4,5.5,7.2\} γ ∈ { 4 , 5.5 , 7.2 } . All methods use warm-started eigs for the SCF steps. A dash indicates failure to converge within the prescribed iteration limit.
Figure 3 reports the convergence histories for the NEPv (67) with γ ∈ { 4 , 5.5 , 7.2 } \gamma\in\{4,5.5,7.2\} γ ∈ { 4 , 5.5 , 7.2 } , where all methods start from the common initial vector x 0 = ( 1 n + ı 1 n ) / 2 n x_0 = (1_n + \imath1_n)/\sqrt{2n} x 0 = ( 1 n + 1 n ) / 2 n . The corresponding computation times are listed in Table 1, along with timings for a larger scale problem of size n = 200 2 = 40 , 000 n = 200^2 = 40,000 n = 20 0 2 = 40 , 000 using the same setup. We observe that the plain SCF converges in all three cases, with slower convergence as γ \gamma γ increases, similarly to the preceding Kohn–Sham example. Direct application of A A ( m ) \mathrm{AA}(m) AA ( m ) to the SCF iterates x i x_i x i (A A ( m ) \mathrm{AA}(m) AA ( m ) -x i x_i x i ) does not effectively accelerate convergence, due to the phase rotation x i α x_i\alpha x i α of computed eigenvectors. Indeed, its acceleration is substantially delayed in the first two cases of γ \gamma γ , with convergence requiring 24 and 62 iterations, respectively;5 in the last case, convergence is not achieved within the prescribed limit of 80 iteration. We note that the behavior of A A ( m ) \mathrm{AA}(m) AA ( m ) -x i x_i x i also depends on the eigensolver used in the SCF step, which can lead to different phase choices for the computed eigenvectors. For comparison, we also report the convergence histories of A A ( m ) \mathrm{AA}(m) AA ( m ) -x i x_i x i when eigs uses a random starting vector.6 In this case, convergence is not achieved within the prescribed iteration limit in all three tests.
In comparison, all four proposed acceleration techniques significantly reduce the number of SCF iterations in all three test cases. The three variants of AA exhibit comparable performance in terms of both iteration counts and computation times. The Newton acceleration exhibits superlinear convergence, reaching the prescribed accuracy in six iterations. It also achieves the least computation times in all three cases. This efficiency can be attributed to the inexpensive evaluation of the derivative (70) , together with effective preconditioning of the Newton equation.
Sparse PCA
In this example, we consider NEPv arising from sparse PCA (principal component analysis) [42 , 80 ] . The optimization problem of interest takes the form
min X ∈ R n , k , X T X = I k − tr ( X T A X ) + α ⋅ ∥ X ∥ 2 , 1 , (71) \min_{X\in\mathbb{R}^{n,k},\,X^{T}X=I_k} -\operatorname{tr}(X^{T}AX)+\alpha\cdot\lVert X\rVert_{2,1}, \tag*{(71)} X ∈ R n , k , X T X = I k min − tr ( X T A X ) + α ⋅ ∥ X ∥ 2 , 1 , (71)
where A ∈ R n , n A\in\mathbb{R}^{n,n} A ∈ R n , n is symmetric positive semidefinite, α ≥ 0 \alpha\ge0 α ≥ 0 is a penalty parameter, and ∥ X ∥ 2 , 1 : = ∑ j = 1 n ∥ e j T X ∥ 2 \lVert X\rVert_{2,1}:=\sum_{j=1}^{n}\lVert e_j^{T}X\rVert_2 ∥ X ∥ 2 , 1 := ∑ j = 1 n ∥ e j T X ∥ 2 denotes the ( 2 , 1 ) (2,1) ( 2 , 1 ) -norm (i.e., the sum of 2-norms of the rows of X X X ). Without the penalty, i.e., when α = 0 \alpha=0 α = 0 , the problem reduces to standard PCA and can be solved by computing the eigenvectors of the k k k smallest eigenvalues of − A -A − A (equivalently, the k k k largest of A A A ). The penalty term promotes row sparsity and thus favors a sparse solution X X X . With a smooth approximation of the penalty, the first-order optimality condition of (71) leads to the NEPv
H ε ( X ) X = X Λ with H ε ( X ) : = − 2 A + α ⋅ Diag ( ( diag ( X X T ) + ε 2 1 n ) − 1 / 2 ) , (72) H_{\varepsilon}(X)X=X\Lambda\quad\text{with}\quad H_{\varepsilon}(X):=-2A+\alpha\cdot\operatorname{Diag}\left(\left(\operatorname{diag}(XX^{T})+\varepsilon^{2}1_n\right)^{-1/2}\right), \tag*{(72)} H ε ( X ) X = X Λ with H ε ( X ) := − 2 A + α ⋅ Diag ( ( diag ( X X T ) + ε 2 1 n ) − 1/2 ) , (72)
where Λ \Lambda Λ corresponds to the k k k smallest eigenvalues of H ε ( X ) H_{\varepsilon}(X) H ε ( X ) for the purpose of minimization, the power − 1 / 2 -1/2 − 1/2 is taken entrywise, and ε > 0 \varepsilon>0 ε > 0 (e.g., ε = 10 − 3 k / n 3 \varepsilon=10^{-3}\sqrt[3]{k/n} ε = 1 0 − 3 3 k / n ) is a smoothing parameter introduced to improve numerical stability when entries of diag ( X X T ) \operatorname{diag}(XX^{T}) diag ( X X T ) are small – Specifically, each row norm ∥ e j T X ∥ 2 \lVert e_j^{T}X\rVert_2 ∥ e j T X ∥ 2 in the penalty ∥ X ∥ 2 , 1 \lVert X\rVert_{2,1} ∥ X ∥ 2 , 1 (71) is replaced by ( ∥ e j T X ∥ 2 2 + ε 2 ) 1 / 2 \left(\lVert e_j^{T}X\rVert_2^2+\varepsilon^2\right)^{1/2} ( ∥ e j T X ∥ 2 2 + ε 2 ) 1/2 . We refer to [49 , 70 ] for further details on the derivation of (72) .
The NEPv (72) admits a natural ui-parameterization
ρ ( X ) : = ( diag ( X X T ) + ε 2 1 n ) 1 / 2 ∈ R n . (73) \rho(X):=\left(\operatorname{diag}(XX^{T})+\varepsilon^2 1_n\right)^{1/2}\in\mathbb{R}^n. \tag*{(73)} ρ ( X ) := ( diag ( X X T ) + ε 2 1 n ) 1/2 ∈ R n . (73)
Moreover, H ε H_{\varepsilon} H ε is Fréchet differentiable, with derivative
D H ε ( X ) [ E ] = − α Diag ( ( diag ( X ) + ε 2 1 n ) − 3 / 2 ) ⊛ diag ( E X T ) , (74) DH_{\varepsilon}(X)[E]=-\alpha\operatorname{Diag}\left(\left(\operatorname{diag}(X)+\varepsilon^2 1_n\right)^{-3/2}\right)\circledast\operatorname{diag}(EX^{T}), \tag*{(74)} D H ε ( X ) [ E ] = − α Diag ( ( diag ( X ) + ε 2 1 n ) − 3/2 ) ⊛ diag ( E X T ) , (74)
where the power − 3 / 2 -3/2 − 3/2 is taken entrywise and ⊛ \circledast ⊛ denotes the Hadamard product (entrywise product).
For the experiments, we consider two real-world data sets, USPS and COIL20 [38 , 57 ] , also used in [70 ] , with preprocessed data available from [47 ] . The USPS data set contains p = 9 , 298 p=9,298 p = 9 , 298 samples of handwritten digits with n = 256 n=256 n = 256 features, and COIL20 contains p = 1 , 440 p=1,440 p = 1 , 440 grayscale images with n = 1 , 024 n=1,024 n = 1 , 024 features. We collect each dataset into a matrix Y ∈ R p × n Y\in\mathbb{R}^{p\times n} Y ∈ R p × n , with each row containing the feature vector of one sample. The sample covariance matrix is constructed as A = 1 p − 1 Y ^ T Y ^ A=\frac{1}{p-1}\widehat{Y}^{T}\widehat{Y} A = p − 1 1 Y T Y , with Y ^ = Y − 1 p μ T \widehat{Y}=Y-1_p\mu^{T} Y = Y − 1 p μ T and the sample mean μ = 1 p Y T 1 p \mu=\frac{1}{p}Y^{T}1_p μ = p 1 Y T 1 p . We then extract the sparse principal components by solving the NEPv (72) using SCF iteration. We aim to find k = 50 k=50 k = 50 eigenpairs for the USPS dataset and k = 30 k=30 k = 30 eigenpairs for the COIL20 dataset. The regularization parameters in both NEPv are set to ε = 10 − 3 k / n 3 \varepsilon=10^{-3}\sqrt[3]{k/n} ε = 1 0 − 3 3 k / n and α = 0.1 \alpha=0.1 α = 0.1 .
Figure 4 shows the convergence histories for the two test NEPv, and Table 2 summarizes the parameters and computation times. The SCF iteration starts from the standard PCA solution X 0 ∈ R n , k X_0\in\mathbb{R}^{n,k} X 0 ∈ R n , k , consisting of orthonormal eigenvectors associated with the k k k largest eigenvalues of A A A . To approach the local convergence regime, we perform 10 preliminary SCF steps for USPS and 25 steps for COIL20 before enabling acceleration. Since the problem sizes are moderate, the symmetric eigenvalue problem in each SCF step is solved using the dense solver eig. For basis-aligned Newton acceleration, the correction equations are solved using MINRES, which exploits the self-adjointness of L \mathcal{L} L ; see Remark 2. All algorithms stop when the NEPv residual norm falls below τ = 10 − 11 \tau=10^{-11} τ = 1 0 − 11 , and AA( m ) (m) ( m ) variants use a fixed window size m = 4 m=4 m = 4 .
Figure 4. Convergence histories of the algorithms for NEPv (65) on the data sets USPS (left, n = 256 n = 256 n = 256 , k = 50 k = 50 k = 50 , 10 preliminary SCF steps) and COIL20 (right, n = 1,024 n = 1{,}024 n = 1 , 024 , k = 30 k = 30 k = 30 , 25 preliminary SCF steps).
Table 2. Computation times (seconds) for the sparse PCA NEPv (65) on the data sets USPS and COIL20 as shown in Figure 4. A dash indicates failure to converge within the given iteration limit.
We observe that the convergence behaviors of the algorithms are largely consistent with the previous experiments. Direct application of AA( m ) (m) ( m ) to the SCF basis iterates again leads to divergence. All other AA( m ) (m) ( m ) variants converge and accelerate SCF, with similar convergence behavior and comparable computational costs. In comparison, Newton acceleration exhibits superlinear convergence and requires the least outer iterations. However, its computation time shown in Table 2 is even higher than that of the plain SCF. This is mainly due to the high cost of iterative solver for the Newton correction equation due to large condition number partly attributed to the small row norms of the sparse PCA solution that leads to large variations in diagonals of H ε H_{\varepsilon} H ε and its derivative (74) . The preconditioner in Remark 3 cannot effectively accelerate the solution of these equations.
Uniform Multidimensional Scaling
As our final example, we consider the uniform multidimensional scaling (UMDS) problem from multi-view learning introduced in [77 ] . Consider observations of the same n n n objects from s s s different views, collected in matrices Y j ∈ R d j , n Y_j \in\mathbb{R}^{d_j,n} Y j ∈ R d j , n , j = 1 , … , s j = 1,\ldots,s j = 1 , … , s , where each column of Y j Y_j Y j contains the d j d_j d j -dimensional observation of one object in the j j j th view. UMDS seeks a common orthogonal projection X ∈ R n , k X \in\mathbb{R}^{n,k} X ∈ R n , k that represents the n n n objects in a latent space while preserving information from the different views. After relaxing the constraints, the projection can be obtained from the optimization problem7
min X ∈ R n , k , X T X = I k − ∑ j = 1 s ∥ X T A j X ∥ F 2 , (75) \min_{\substack{X \in\mathbb{R}^{n,k},\ X^{T}X=I_k}}-\sum_{j=1}^{s}\left\lVert X^{T}A_jX\right\rVert_{F}^{2}, \tag*{(75)} X ∈ R n , k , X T X = I k min − j = 1 ∑ s X T A j X F 2 , (75)
where A j ∈ R n , n A_j \in\mathbb{R}^{n,n} A j ∈ R n , n is the symmetric centered squared distance matrix for the j j j th view Y j Y_j Y j ; see [77 ] for details. The first-order optimality condition for (75) leads directly to the NEPv
H ( X ) X = X Λ with H ( X ) : = − ∑ j = 1 s A j X X T A j , (76) H(X)X = X\Lambda\quad\text{with} \quad H(X) := -\sum_{j=1}^{s} A_jXX^{T}A_j, \tag*{(76)} H ( X ) X = X Λ with H ( X ) := − j = 1 ∑ s A j X X T A j , (76)
where we target the k k k smallest eigenvalues of H ( X ) H(X) H ( X ) for minimization; see, e.g., [48 ] . The matrix valued function H ( X ) H(X) H ( X ) in (76) is unitarily invariant. However unlike the previous examples, a compact ui-parameterization is not readily available for the NEPv (76) , so we skip the AA-ρ \rho ρ scheme for this test. The function H ( X ) H(X) H ( X ) is differentiable, with a Fréchet derivative
D H ( X ) [ E ] = − ∑ j = 1 s ( A j E X T A j + A j X E T A j ) . (77) DH(X)[E] = -\sum_{j=1}^{s}\left(A_jEX^{T}A_j + A_jXE^{T}A_j\right). \tag*{(77)} D H ( X ) [ E ] = − j = 1 ∑ s ( A j E X T A j + A j X E T A j ) . (77)
Iterative solvers used in the SCF and Newton steps require only products involving H ( X ) z H(X)z H ( X ) z and D H ( X ) [ E ] X DH(X)[E]X D H ( X ) [ E ] X , and they can be evaluated using the factored expressions in (76) and (77) , without explicitly forming H ( X ) H(X) H ( X ) or the derivative operator. With the factors A j X A_jX A j X precomputed at each outer iteration, the computational complexity for H ( X ) z H(X)z H ( X ) z is about O ( n s k ) O(nsk) O ( n s k ) , while for D H ( X ) [ E ] X DH(X)[E]X D H ( X ) [ E ] X it is about O ( n 2 s k ) O(n^2sk) O ( n 2 s k ) . Thus, derivative applications are substantially more expensive for large n n n .
For the experiments, we consider three benchmark data sets: CiteSeer [31 , 65 ] , Cora [56 , 65 ] , and Reuters1500 [4 , 72 ] , with problem sizes listed in Table 3 . We compare the plain SCF, the AA variants AA(m m m )-X X X , AA(m m m )-[ [ X ] ] [[X]] [[ X ]] , and AA(m m m )-Gr with a fixed window size m = 4 m = 4 m = 4 , and basis-aligned Newton acceleration. Given the relatively large problem sizes, we use a setup similar to that in § 5.3 : warm-started eigs for the SCF steps and an inexact implementation of basis-aligned Newton, with the correction equations solved by flexible GMRES with a maximum Krylov subspace dimension of 25, using 40 MINRES steps for each preconditioner application. Since applying D H ( X ) [ E ] X DH(X)[E]X D H ( X ) [ E ] X is substantially more expensive than H ( X ) z H(X)z H ( X ) z , each MINRES step is much cheaper than a GMRES step because it avoids derivative evaluations. All methods use a common initial guess X 0 ∈ R n , k X_0 \in\mathbb{R}^{n,k} X 0 ∈ R n , k , formed from the k k k eigenvectors corresponding to the smallest eigenvalues of − ∑ j = 1 s A j -\sum_{j=1}^{s} A_j − ∑ j = 1 s A j . The convergence histories and computation times are reported in Figure 5 and table 3, respectively.
Figure 5. Convergence histories of the algorithms for the UMDS NEPv (76) on the data sets CiteSeer (left, n = 3 , 312 n = 3,312 n = 3 , 312 , k = 6 k = 6 k = 6 ), Cora (middle, n = 2 , 708 n = 2,708 n = 2 , 708 , k = 7 k = 7 k = 7 ), and Reuters1500 (right, n = 1 , 500 n = 1,500 n = 1 , 500 , k = 6 k = 6 k = 6 ).
Table 3. Problem sizes and computation times (seconds) for the UMDS NEPv (76) on the data sets CiteSeer, Cora, and Reuters1500 as shown in Figure 5 . Here, n n n , s s s , and k k k denote the numbers of samples, views, and clusters, respectively. A dash indicates failure to converge within the given iteration limit.
In all three experiments, SCF converges slowly, and AA applied directly to X i X_i X i stagnates at the initial residual. Both AA-[ [ X i ] ] [[X_i]] [[ X i ]] and Grassmannian AA substantially accelerate convergence, and AA-[ [ X i ] ] [[X_i]] [[ X i ]] slightly outperforms Grassmannian. Newton acceleration also improves the slow convergence of SCF in all of our tests. It requires the least number of iterations among the algorithms, converged within nine iterations as compared with 55–105 for the two convergent AA variants. In terms of computation time, it is not the fastest, but it is still competitive due to the efficient preconditioner for solving the correction equation. We observed that without preconditioning, the plain MINRES can require up to four times as much computation time as the preconditioned solver to solve a Newton equation to the same residual tolerance.
Concluding Remarks
We studied acceleration techniques of the SCF iteration for unitarily invariant NEPv based on the AA and Newton methods. To address the non-uniqueness of the eigenvector bases, we presented three AA variants based on invariant parameterization, basis alignment, and Grassmannian geometry. We also developed a basis-aligned Newton correction that removes the singularity caused by unitary invariance and established its local quadratic convergence under suitable assumptions. Numerical experiments demonstrated the effectiveness of these approaches in accelerating the convergence of SCF.
In our experiments, the three AA variants exhibited a similar convergence behavior and comparable computational costs. The choice among them can therefore be guided by ease of implementation. Parameterization-based AA is convenient when a suitable invariant parameterization is readily available. Otherwise, aligned AA can be implemented using basis alignment, while Grassmannian AA is a natural choice when the required manifold operations are already available. Newton acceleration is attractive when high accuracy is required and derivative actions can be evaluated efficiently. Its local quadratic convergence can reduce the number of outer iterations, although the additional cost of solving the correction equation must also be considered.
This work provides a starting point for several directions for further research. A systematic convergence study of the proposed AA variants remains open, particularly concerning the influence of different choices of ui-parameterization. The basis-aligned Newton formulation also provides a theoretical foundation for developing more efficient solvers through inexact correction and preconditioning. One could also explore the implementation and benefits of combining accelerations with stabilization techniques, such as the level-shifted SCF, whose global convergence may come at the cost of slow local convergence. Finally, beyond NEPv, we expect the ideas and methods developed in this work to extend naturally to other iterative methods that operate on subspaces, offering new ways to accelerate these methods.
Acknowledgments
The work of Ding Lu was supported in part by NSF under grant DMS-2110731.
Tom Werner acknowledges the hospitality of the Department of Mathematics at University of Kentucky during his visits in Spring 2024 and Fall 2025.
CRediT Author Statement
The authors have contributed to this work in the following way. Ding Lu: Conceptualization, Investigation, Methodology, Software, Supervision, Writing - Original Draft; Tom Werner: Conceptualization, Investigation, Methodology, Software, Writing - Original Draft; Zhaojun Bai Conceptualization, Supervision, Writing - Review & Editing.