Introduction
In this paper, we consider a matrix decomposition problem that we call diagonal tight frame decomposition [27 ] with data-aware adaptation for sparse representation. The decomposition is related to the singular value decomposition, with the difference that the corresponding singular vectors form a tight frame (for a precise definition, see § 2.1 ) instead of an orthonormal basis. The problem is formulated as follows:
Problem 1. Given a matrix A ∈ R N × M \mathbf{A} \in\mathbb{R}^{N \times M} A ∈ R N × M and a data set X = [ x 1 , x 2 , … , x S ] ∈ R M × S \mathbf{X} = [\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_S] \in\mathbb{R}^{M \times S} X = [ x 1 , x 2 , … , x S ] ∈ R M × S , find matrices U \mathbf{U} U , D \mathbf{D} D , and V \mathbf{V} V satisfying the following properties:
Tightness: U \mathbf{U} U and V \mathbf{V} V are tight frames,
Scalability: D \mathbf{D} D is diagonal,
Decomposition: A T V = U D \mathbf{A}^{\mathsf{T}}\mathbf{V} = \mathbf{U}\mathbf{D} A T V = UD ,
Sparsity: the representations U T X \mathbf{U}^{\mathsf{T}}\mathbf{X} U T X are sparse.
The motivation for this problem comes from the use of frame decompositions for the representation and inversion of linear operators in Hilbert spaces. This diagonalized structure allows the evaluation and inversion of the operator to be analysed and implemented in terms of frame operators and scalar multiplication. The sparsity property incorporates prior information about the underlying signal class and can help stabilize the representation. Such decompositions have been used, for example, in the regularization of inverse problems [9 , 20 , 21 , 22 , 26 , 27 ] .
If U and V are orthonormal bases for R M \mathbb{R}^{M} R M and R N \mathbb{R}^{N} R N , respectively, then A = V D U T \mathbf{A} = \mathbf{V}\mathbf{D}\mathbf{U}^{\mathsf{T}} A = VD U T is a singular value decomposition. However, the singular vectors generally do not provide sparse representations for a given signal class. They are determined solely by the matrix A \mathbf{A} A and therefore cannot be adapted to different signal distributions. In contrast, tight frames provide stable and redundant representations that are well suited for sparse signal representations. Moreover, their dual frames are particularly easy to compute, since the canonical dual of a tight frame differs only by a multiplicative constant. The diagonal matrix D \mathbf{D} D plays a role analogous to the singular values and is therefore often referred to as the matrix of quasi-singular values. It represents the scaling action of the operator in the corresponding frame coordinates. Replacing orthonormal bases by tight frames therefore provides greater flexibility in the construction of such decompositions, allowing additional properties to be imposed. In particular, our sparsity condition introduces a data-dependent criterion: rather than constructing a decomposition solely from the algebraic properties of A \mathbf{A} A , we seek a frame U \mathbf{U} U whose coefficients provide sparse representations given the data X \mathbf{X} X . This is motivated by the observation that suitable representations can capture the structure of signals and images more efficiently and incorporate prior information that is relevant for inverse problems [12 , 35 ] . We note in passing that the diagonal matrix decomposition problems has applications far beyond imaging. In fact, frames are widely used for this purpose in applied mathematics, computer science, and engineering, with applications including sampling theory [23 ] , data quantization [5 , 6 ] , image processing [10 , 29 ] , and coding theory [40 ] .
Applications
Application 1: Inverse problems. In inverse problems, one seeks to recover an unknown parameter x ∈ X x \in X x ∈ X from noisy measurements
K x + n = y δ . (1) \mathbf{K}x+n=y^{\delta}. \tag*{(1)} K x + n = y δ . (1)
K : X → Y \mathbf{K}: X \to Y K : X → Y is a linear operator between Hilbert spaces X X X and Y Y Y , n n n denotes a bounded noise term, and y δ ∈ Y y^{\delta} \in Y y δ ∈ Y is the observed data. The goal is to recover the unknown x x x from the noisy measurements y δ y^{\delta} y δ .
The operator K \mathbf{K} K is typically not continuously invertible, making the reconstruction problem ill-posed and necessitating regularization. Given a discretization A ∈ R N × M \mathbf{A} \in\mathbb{R}^{N \times M} A ∈ R N × M of K \mathbf{K} K , we follow the discretize-then-optimize methodology from numerical analysis. Since A \mathbf{A} A is typically ill-conditioned, direct inversion is highly sensitive to measurement noise and therefore does not provide a stable reconstruction.
Given the decomposition ( U , V , D ) (\mathbf{U},\mathbf{V},\mathbf{D}) ( U , V , D ) searched for in Problem 1 , we have A T V = U D \mathbf{A}^{\mathsf{T}}\mathbf{V}=\mathbf{U}\mathbf{D} A T V = UD for tight frames U \mathbf{U} U and V \mathbf{V} V and diagonal matrix D \mathbf{D} D . Let x + ∈ ker ( A ) ⊥ x^{+} \in\operatorname{ker}(\mathbf{A})^{\perp} x + ∈ ker ( A ) ⊥ be the least-squares solution of A x = y \mathbf{A}x=y A x = y for noiseless observations y ∈ ran ( A ) y \in\operatorname{ran}(\mathbf{A}) y ∈ ran ( A ) . By the sparsity constraint, the frame coefficients of x + x^{+} x + are assumed to be sparse with respect to U \mathbf{U} U . In particular, given a dual frame U ˉ \bar{\mathbf{U}} U ˉ of U \mathbf{U} U , the duality relation for frames gives
x + = U ˉ U ˉ T x + = ∑ i = 1 K ⟨ x + , u i ⟩ u ˉ i , x^{+}=\bar{\mathbf{U}}\bar{\mathbf{U}}^{\mathsf{T}}x^{+}=\sum_{i=1}^{K}\langle x^{+},u_i\rangle\bar{u}_i, x + = U ˉ U ˉ T x + = i = 1 ∑ K ⟨ x + , u i ⟩ u ˉ i ,
where u i u_i u i and u ˉ i \bar{u}_i u ˉ i denote the columns of U \mathbf{U} U and U ˉ \bar{\mathbf{U}} U ˉ , respectively. Thus, if the frame coefficients ⟨ x + , u i ⟩ \langle x^+,u_i\rangle ⟨ x + , u i ⟩ are sparse, the signal can be represented accurately using only a small number of frame elements. The decomposition further yields the relation D † V T A = U T \mathbf{D}^{\dagger}\mathbf{V}^{\mathsf{T}}\mathbf{A}=\mathbf{U}^{\mathsf{T}} D † V T A = U T , where D † \mathbf{D}^{\dagger} D † denotes the Moore–Penrose inverse of D \mathbf{D} D . Consequently,
U T x + = D † V T A x + = D † V T y , \mathbf{U}^{\mathsf{T}}x^+=\mathbf{D}^{\dagger}\mathbf{V}^{\mathsf{T}}\mathbf{A}x^+=\mathbf{D}^{\dagger}\mathbf{V}^{\mathsf{T}}y, U T x + = D † V T A x + = D † V T y ,
and hence D † V T y \mathbf{D}^{\dagger}\mathbf{V}^{\mathsf{T}}y D † V T y is sparse as well. The Moore–Penrose inverse of A \mathbf{A} A is given by A + = U ˉ D † V T \mathbf{A}^{+}=\bar{\mathbf{U}}\mathbf{D}^{\dagger}\mathbf{V}^{\mathsf{T}} A + = U ˉ D † V T . For noisy data y δ = A x + + n y^\delta=\mathbf{A}x^++n y δ = A x + + n , the corresponding reconstruction is
A + y δ = U ˉ D † V T y δ = U ˉ ( D † V T y + D † V T n ) . \mathbf{A}^{+}y^\delta=\bar{\mathbf{U}}\mathbf{D}^{\dagger}\mathbf{V}^{\mathsf{T}}y^\delta=\bar{\mathbf{U}}\left(\mathbf{D}^{\dagger}\mathbf{V}^{\mathsf{T}}y+\mathbf{D}^{\dagger}\mathbf{V}^{\mathsf{T}}n\right). A + y δ = U ˉ D † V T y δ = U ˉ ( D † V T y + D † V T n ) .
This representation separates the reconstruction into the frame coefficients of the underlying signal and a noise term amplified by D † \mathbf{D}^{\dagger} D † . Small entries of D \mathbf{D} D reflect the ill-conditioning of A \mathbf{A} A and can lead to strong amplification of the noise. The sparsity of the signal representation therefore provides a natural basis for regularization: rather than applying the inverse directly, the coefficients can be filtered to suppress noise while preserving the significant components of the signal. Such regularized reconstructions take the form
R α ( y δ ) = U ˉ f α ( D † , V T y δ ) , (2) \mathcal{R}_{\alpha}(y^\delta)=\bar{\mathbf{U}}f_{\alpha}\left(\mathbf{D}^{\dagger},\mathbf{V}^{\mathsf{T}}y^\delta\right), \tag*{(2)} R α ( y δ ) = U ˉ f α ( D † , V T y δ ) , (2)
where the filter is applied component-wise. An example is the soft-thresholding filter
f α ( d , c ) = sign ( c ) max { ∣ c ∣ − α / d , 0 } . (3) f_{\alpha}(d,c)=\operatorname{sign}(c)\max\{|c|-\alpha/d,0\}. \tag*{(3)} f α ( d , c ) = sign ( c ) max { ∣ c ∣ − α / d , 0 } . (3)
Under suitable assumptions on the filter and the parameter choice α = α ( δ ) \alpha=\alpha(\delta) α = α ( δ ) , such filtered reconstructions can yield a convergent regularization method in the sense of [24 ] as the noise level δ \delta δ tends to zero, see [22 , 27 ] .
Note that, although frame decompositions with non-tight frames are also used for inverse problems, non-tight frames in finite dimensions have the disadvantage that the frame bounds must be controlled and the corresponding dual frame must be computed.
Application 2: Sparse representation of observations. The matrix decomposition also provides a sparse representation of the observations. Indeed, from A T V = U D \mathbf{A}^{\mathsf{T}}\mathbf{V}=\mathbf{U}\mathbf{D} A T V = UD we obtain A = V ˉ D U T \mathbf{A}=\bar{\mathbf{V}}\mathbf{D}\mathbf{U}^{\mathsf{T}} A = V ˉ D U T , and hence
y = A x = V ˉ D U T x . y=\mathbf{A}x=\bar{\mathbf{V}}\mathbf{D}\mathbf{U}^{\mathsf{T}}x. y = A x = V ˉ D U T x .
If the frame coefficients U T x \mathbf{U}^{\mathsf{T}}x U T x are sparse, then the coefficient vector D U T x = V T y \mathbf{D}\mathbf{U}^{\mathsf{T}}x=\mathbf{V}^{\mathsf{T}}y D U T x = V T y is sparse as well. Thus, the observations y y y admit a sparse representation with respect to the dual frame V ˉ \bar{\mathbf{V}} V ˉ ,
y = ∑ i = 1 K d i ⟨ x , u i ⟩ v ˉ i , y=\sum_{i=1}^{K}d_i\langle x,u_i\rangle\bar{v}_i, y = i = 1 ∑ K d i ⟨ x , u i ⟩ v ˉ i ,
where v ˉ i \bar{v}_i v ˉ i denotes the i i i th element of the dual frame V ˉ \bar{\mathbf{V}} V ˉ . Consequently, the observations can be represented and stored using only a small number of nonzero frame coefficients. In particular, instead of storing the full observation vector y y y , one may store its sparse frame representation V T y = D U T x \mathbf{V}^{\mathsf{T}}y=\mathbf{D}\mathbf{U}^{\mathsf{T}}x V T y = D U T x together with the corresponding indices.
Main contributions
In this paper, we develop a numerical methodology for solving the structured matrix decomposition (Problem 1 ). Our approach combines an algebraic reduction of the decomposition problem with a new non-smooth and non-convex hierarchical (bilevel) optimization formulation of the original matrix decomposition problem. In particular, we develop from scratch a new bilevel optimization formulation on the Stiefel manifold containing the desired frame matrices.
We first show that Problem 1 can be reduced to an equivalent problem involving only positive diagonal matrices for A. This reduction allows us to characterize necessary and sufficient conditions on the diagonal matrix D for the existence of a decomposition satisfying the prescribed tightness and decomposition constraints. Once D is fixed, the remaining problem can be formulated entirely in terms of the frame U, since the second frame V is uniquely determined by U and D. The tightness constraint on U naturally leads to an optimization problem on the Stiefel manifold.
To incorporate the sparsity requirement, we formulate the resulting problem as a simple bilevel optimization problem on the Stiefel manifold (11) . The lower-level problem is a smooth but non-convex optimization problem whose solution guarantees the tightness of V and the decomposition property, while the upper-level objective is convex and lower semi-continuous, incorporating the sparsity requirement. The tightness of U follows directly from the definition of the Stiefel manifold. Although the lower-level problem is convex when considered in the ambient Euclidean space, this convexity is generally lost after restricting the problem to the Stiefel manifold. We address the resulting nonconvex bilevel problem using a penalized subgradient method formulated in a general setting, which therefore applies beyond the specific matrix decomposition considered here.
We provide a rigorous convergence analysis of both levels of the resulting bilevel scheme. In particular, we establish convergence of the lower-level optimization procedure and analyze the convergence of the iterates to stationary points of the bilevel problem under the stated assumptions. The theoretical results are complemented by numerical experiments that demonstrate the practical behavior of the proposed method and its ability to identify sparse frame representations adapted to the given data.
Related work
Optimization-based approaches to frame computation have been studied, for example, by [41 ] , who develop convex optimization methods for constructing frames with prescribed structural properties. Our setting differs in that the frame is not designed independently of an operator; instead, the frame and a diagonal scaling are jointly required to represent a given matrix while promoting sparsity of its action on a data set. A related line of work concerns scalable frames, where one seeks diagonal scalings that transform a given frame into a Parseval frame; see, e.g., [30 ] . Scalable-frame theory typically considers a fixed frame and asks whether a positive diagonal scaling yields a Parseval frame. In contrast, we optimize the frame itself together with the diagonal scaling, with the additional requirement that their product represent a prescribed operator and with a data-dependent sparsity objective.
Optimization subject to orthogonality constraints is naturally formulated on matrix manifolds. Structural optimization on embedded submanifolds was studied, for example, in [8 ] . For optimization on the Stiefel manifold, proximal gradient methods have been developed in [13 ] ; see [14 ] for a broader treatment of proximal and related methods for nonsmooth optimization on matrix manifolds. Weakly convex optimization, which is relevant to the nonsmooth structure arising in our analysis, has been studied extensively in [18 , 31 ] .
Penalty methods are classical approaches to solve constrained optimization problems via a sequence of unconstrained problems. In convex optimization in Euclidean spaces, prox-penalization and related diagonal-gradient approaches have been studied extensively [1 , 2 , 3 , 4 , 34 , 38 ] . In contrast, penalty formulations specifically tailored to optimization on the Stiefel manifold are comparatively less developed. For example, a Lagrangian relaxation approach for optimization with Stiefel constraints is considered in [43 ] . Our work combines these ideas by employing a penalty formulation together with a subgradient method on the Stiefel manifold to solve the bilevel frame decomposition problem.
Preliminaries
Throughout, we work in real finite-dimensional vector spaces equipped with an inner product ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ and the associated norm ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ . Unless stated otherwise, we use the Frobenius norm for matrices and the ℓ 2 \ell^2 ℓ 2 -norm for vectors, i.e.,
∥ A ∥ F : = ( ∑ i , j ∣ A i j ∣ 2 ) 1 / 2 , ∥ x ∥ 2 : = ( ∑ i ∣ x i ∣ 2 ) 1 / 2 , \|A\|_{\mathrm{F}} := \left(\sum_{i,j}|A_{ij}|^2\right)^{1/2}, \qquad\|x\|_2 := \left(\sum_i |x_i|^2\right)^{1/2}, ∥ A ∥ F := ( i , j ∑ ∣ A ij ∣ 2 ) 1/2 , ∥ x ∥ 2 := ( i ∑ ∣ x i ∣ 2 ) 1/2 ,
where we omit the subscript when it is clear from the context.
Frames
We briefly recall some basic facts about finite-dimensional frame theory. More background on frame theory in Hilbert spaces can be found in [15 ] , while [42 ] provides an introduction to finite tight frames. Let R , K ∈ N R,K\in\mathbb{N} R , K ∈ N with K ≥ R K\ge R K ≥ R . A family ( u i ) i = 1 K ⊂ R R (u_i)_{i=1}^{K}\subset\mathbb{R}^{R} ( u i ) i = 1 K ⊂ R R is called a frame for R R \mathbb{R}^{R} R R if there exist constants A , B > 0 A,B>0 A , B > 0 such that
A ∥ x ∥ 2 ≤ ∑ i = 1 K ∣ ⟨ u i , x ⟩ ∣ 2 ≤ B ∥ x ∥ 2 for all x ∈ R R . (4) A\|x\|^2 \le\sum_{i=1}^{K}|\langle u_i,x\rangle|^2 \le B\|x\|^2 \qquad\text{for all }x\in\mathbb{R}^{R}. \tag*{(4)} A ∥ x ∥ 2 ≤ i = 1 ∑ K ∣ ⟨ u i , x ⟩ ∣ 2 ≤ B ∥ x ∥ 2 for all x ∈ R R . (4)
In finite dimensions, we identify the frame with the matrix U ∈ R R × K U\in\mathbb{R}^{R\times K} U ∈ R R × K whose columns are the frame elements ( u i ) i = 1 K (u_i)_{i=1}^{K} ( u i ) i = 1 K . The constants A A A and B B B are called the lower and upper frame bounds of U U U , respectively. The frame is called tight if A = B A=B A = B . A simple example of a tight frame is the union of p p p orthonormal bases, in which case the frame bounds are A = B = p A=B=p A = B = p . Other prominent examples include finite-dimensional versions of wavelet, curvelet, and Gabor frames, which arise, for example, from suitable discretizations of these constructions in imaging applications [9 , 10 , 17 ] . A tight frame with A = B = 1 A=B=1 A = B = 1 is called a Parseval frame . Furthermore, a frame is called exact if deleting any single frame element results in a family that is no longer a frame. A frame that is not a basis is called overcomplete .
For a frame represented by U ∈ R R × K U\in\mathbb{R}^{R\times K} U ∈ R R × K , the corresponding analysis and synthesis operations are given by the matrix products
U T x ∈ R K and U c ∈ R R , U^{\mathsf{T}}x\in\mathbb{R}^{K} \qquad\text{and}\qquad Uc\in\mathbb{R}^{R}, U T x ∈ R K and U c ∈ R R ,
respectively. Thus, U T U^{\mathsf{T}} U T maps a vector to its frame coefficients, while U U U synthesizes a vector from a given coefficient vector. The associated frame operator is therefore
S = U U T , S=UU^{\mathsf{T}}, S = U U T ,
which is symmetric positive definite, and hence invertible. In particular, the frame condition can equivalently be written as A I d R R ⪯ U U T ⪯ B I d R R A\mathrm{Id}_{\mathbb{R}^{R}} \preceq UU^{\mathsf{T}} \preceq B\mathrm{Id}_{\mathbb{R}^{R}} A Id R R ⪯ U U T ⪯ B Id R R . For a tight frame with frame constant A A A , the frame condition is equivalent to U U T = A I d R R UU^{\mathsf{T}} = A\mathrm{Id}_{\mathbb{R}^{R}} U U T = A Id R R , while for a Parseval frame it is U U T = I d R R UU^{\mathsf{T}} = \mathrm{Id}_{\mathbb{R}^{R}} U U T = Id R R . Notably, every tight frame can be scaled to a Parseval frame: if U U U is a tight frame with frame constant A A A , then U / A U/\sqrt{A} U / A is a Parseval frame.
The redundancy of a frame generally leads to multiple possible coefficient representations of a given vector. In particular, there are different frames U ‾ ∈ R R × K \overline{U} \in\mathbb{R}^{R \times K} U ∈ R R × K that can serve as dual frames and satisfy the reconstruction identity
x = U ‾ U T x for all x ∈ R R , x = \overline{U}U^{\mathsf{T}}x \quad\text{for all } x \in\mathbb{R}^{R}, x = U U T x for all x ∈ R R ,
or, equivalently, U ‾ U T = I d R R \overline{U}U^{\mathsf{T}} = \mathrm{Id}_{\mathbb{R}^{R}} U U T = Id R R . A distinguished choice is the canonical dual frame, whose matrix is given by U ‾ c a n = ( U U T ) − 1 U \overline{U}_{\mathrm{can}} = (UU^{\mathsf{T}})^{-1}U U can = ( U U T ) − 1 U . For a tight frame with frame constant A A A , this reduces to U ‾ c a n = 1 A U \overline{U}_{\mathrm{can}} = \frac{1}{A}U U can = A 1 U and for a Parseval frame, we simply have U ‾ c a n = U \overline{U}_{\mathrm{can}} = U U can = U . Although the canonical dual is a natural choice, overcomplete frames generally admit multiple dual frames, and this freedom can be beneficial in applications.
Stiefel manifold
In the following sections, we formulate Problem 1 as an optimization problem over the Stiefel manifold. We therefore introduce the necessary notation here, while more details are collected the Appendix.
The Stiefel manifold for parameters K , R K,R K , R is
St ( K , R ) : = { B ∈ R K × R ∣ B T B = I d R R } \operatorname{St}(K,R) := \{B \in\mathbb{R}^{K \times R} \mid B^{\mathsf{T}}B = \mathrm{Id}_{\mathbb{R}^{R}}\} St ( K , R ) := { B ∈ R K × R ∣ B T B = Id R R }
which is an embedded submanifold of the Euclidean space R K × R \mathbb{R}^{K \times R} R K × R . We use this convention for the Stiefel manifold, which is standard in the literature, naturally represents Parseval frames through their transpose: If U ∈ R R × K U \in\mathbb{R}^{R \times K} U ∈ R R × K is a Parseval frame for R R \mathbb{R}^{R} R R , then U T ∈ St ( K , R ) U^{\mathsf{T}} \in\operatorname{St}(K,R) U T ∈ St ( K , R ) , and conversely, for every B ∈ St ( K , R ) B \in\operatorname{St}(K,R) B ∈ St ( K , R ) , the matrix B T B^{\mathsf{T}} B T is a Parseval frame for R R \mathbb{R}^{R} R R . The condition B T B = I d R R B^{\mathsf{T}}B = \mathrm{Id}_{\mathbb{R}^{R}} B T B = Id R R implies that the columns of B B B are orthonormal, which yields
∥ B ∥ 2 = 1 , ∥ B ∥ F = R , ∥ b i ∥ 2 = 1 , \lVert B\rVert_{2} = 1,\qquad\lVert B\rVert_{F} = \sqrt{R},\qquad\lVert b_i\rVert_{2} = 1, ∥ B ∥ 2 = 1 , ∥ B ∥ F = R , ∥ b i ∥ 2 = 1 ,
where b i b_i b i are the columns of B B B . Moreover, St ( K , R ) \operatorname{St}(K,R) St ( K , R ) is compact, being a closed and bounded subset of R K × R \mathbb{R}^{K \times R} R K × R . If the dimensions are clear from the context, we simply write St \operatorname{St} St for the Stiefel manifold.
Computing data-aware tight frame decompositions
Let us recall the notion of diagonal frame decomposition (DFD) in the finite-dimensional setting. For a matrix A ∈ R N × M A \in\mathbb{R}^{N \times M} A ∈ R N × M , a DFD consists of a triplet ( U , V , D ) (U,V,D) ( U , V , D ) such that, for some K ≥ rank ( A ) K \geq\operatorname{rank}(A) K ≥ rank ( A ) ,
U ∈ R M × K U \in\mathbb{R}^{M \times K} U ∈ R M × K is a frame for ker ( A ) ⊥ \operatorname{ker}(A)^{\perp} ker ( A ) ⊥ ,
V ∈ R N × K V \in\mathbb{R}^{N \times K} V ∈ R N × K is a frame for ran ( A ) \operatorname{ran}(A) ran ( A ) ,
D = diag ( d 1 , … , d K ) > 0 D = \operatorname{diag}(d_1,\ldots,d_K) > 0 D = diag ( d 1 , … , d K ) > 0 is diagonal and satisfies the quasi singular relation
A T V = U D . A^{\mathsf{T}}V = UD. A T V = U D .
We refer to a DFD as a tight DFD if both U \mathbf{U} U and V \mathbf{V} V are tight frames, that is,
U U T = A U Id ker ( A ) ⊥ and V V T = A V Id ran ( A ) \mathbf{U}\mathbf{U}^{\mathsf{T}} = A_U \operatorname{Id}_{\ker(\mathbf{A})^\perp}
\qquad\text{and}\qquad
\mathbf{V}\mathbf{V}^{\mathsf{T}} = A_V \operatorname{Id}_{\operatorname{ran}(\mathbf{A})} U U T = A U Id k e r ( A ) ⊥ and V V T = A V Id ran ( A )
where A U A_U A U and A V A_V A V denote the corresponding frame bounds. Depending on the choice of K K K , the set of all tight DFDs can be large. To select a decomposition that is adapted to a given data set and promotes sparse representations, assume that we have collected data from the population of possible parameters x \mathbf{x} x stored in the data set
X = [ x 1 , … , x S ] ∈ R M × S . \mathbf{X} = [\mathbf{x}_1,\ldots,\mathbf{x}_S] \in\mathbb{R}^{M \times S}. X = [ x 1 , … , x S ] ∈ R M × S .
To respect the problem structure captured in these sampled data points and to obtain an expressive dictionary for representing the ground truth parameter, a popular formulation of Problem 1 is the ℓ 1 \ell^1 ℓ 1 -minimization problem
min U ∑ s = 1 S ∥ U T x s ∥ ℓ 1 ( R K ) (5) \min_{\mathbf{U}} \sum_{s=1}^{S} \left\|\mathbf{U}^{\mathsf{T}}\mathbf{x}_s\right\|_{\ell^1(\mathbb{R}^K)} \tag*{(5)} U min s = 1 ∑ S U T x s ℓ 1 ( R K ) (5)
subject to: ( U , V , D ) (\mathbf{U},\mathbf{V},\mathbf{D}) ( U , V , D ) is a tight DFD for A \mathbf{A} A .
Here, A \mathbf{A} A and the data set X \mathbf{X} X are given, while U \mathbf{U} U , V \mathbf{V} V , and D \mathbf{D} D are to be determined. Note that the objective function of the optimization problem is convex, but the constraints are not. Hence, in its current form, the optimization problem is challenging and it is not clear whether the above variational formulation can be exploited computationally for data-aware frame design. We address this question through a sequence of transformations that reduce the original problem to a more tractable formulation. In particular, we show that the problem can be recast as a nonconvex bilevel optimization problem over a Stiefel manifold. This reformulation enables the application of a first-order optimization method for which we establish convergence guarantees.
Reduction to Parseval tight DFDs for positive diagonal matrices
First, we note that the frames in a tight DFD can be rescaled arbitrarily, as the scaling can be absorbed into the quasi-singular values D \mathbf{D} D . Indeed, if ( U , V , D ) (\mathbf{U},\mathbf{V},\mathbf{D}) ( U , V , D ) is a tight DFD of A \mathbf{A} A , then ( a U , b V , b a D ) (a\mathbf{U},b\mathbf{V},\frac{b}{a}\mathbf{D}) ( a U , b V , a b D ) is also a tight DFD of A \mathbf{A} A for any a , b > 0 a,b>0 a , b > 0 . Since the ℓ 1 \ell^1 ℓ 1 sparsity term ∥ U T x s ∥ ℓ 1 \|\mathbf{U}^{\mathsf{T}}\mathbf{x}_s\|_{\ell^1} ∥ U T x s ∥ ℓ 1 is not invariant under such rescaling, whereas the ideal ℓ 0 \ell^0 ℓ 0 sparsity measure is, we fix the scaling of the frames throughout. In particular, we w.l.o.g normalize the frames to be Parseval frames.
Our second reduction assumes that a reduced singular value decomposition (SVD) of the matrix A ∈ R N × M \mathbf{A} \in\mathbb{R}^{N \times M} A ∈ R N × M is available. Let R = rank ( A ) R=\operatorname{rank}(\mathbf{A}) R = rank ( A ) and consider A = Q Σ W T \mathbf{A}=\mathbf{Q}\boldsymbol{\Sigma}\mathbf{W}^{\mathsf{T}} A = Q Σ W T , where Q ∈ R N × R \mathbf{Q}\in\mathbb{R}^{N\times R} Q ∈ R N × R and W ∈ R M × R \mathbf{W}\in\mathbb{R}^{M\times R} W ∈ R M × R have orthonormal columns, and Σ = diag ( σ 1 , … , σ R ) \boldsymbol{\Sigma}=\operatorname{diag}(\sigma_1,\ldots,\sigma_R) Σ = diag ( σ 1 , … , σ R ) with σ 1 ≥ ⋯ ≥ σ R > 0 \sigma_1\ge\cdots\ge\sigma_R>0 σ 1 ≥ ⋯ ≥ σ R > 0 . Such a reduced SVD can be computed routinely using standard numerical linear algebra packages. The following lemma shows that, for a prescribed sequence of positive weights ( d k ) (d_k) ( d k ) , the construction of a DFD can be reduced to a problem involving only the positive diagonal matrix Σ \boldsymbol{\Sigma} Σ .
Lemma 3.1. Let A = Q Σ W T \mathbf{A}=\mathbf{Q}\boldsymbol{\Sigma}\mathbf{W}^{\mathsf{T}} A = Q Σ W T be the reduced SVD of A ∈ R N × M \mathbf{A}\in\mathbb{R}^{N\times M} A ∈ R N × M , where Q ∈ R N × R \mathbf{Q}\in\mathbb{R}^{N\times R} Q ∈ R N × R , W ∈ R M × R \mathbf{W}\in\mathbb{R}^{M\times R} W ∈ R M × R have orthonormal columns and Σ = diag ( σ 1 , … , σ R ) ∈ R + R × R \boldsymbol{\Sigma}=\operatorname{diag}(\sigma_1,\ldots,\sigma_R)\in\mathbb{R}^{R\times R}_+ Σ = diag ( σ 1 , … , σ R ) ∈ R + R × R with σ 1 ≥ ⋯ ≥ σ R > 0 \sigma_1\ge\cdots\ge\sigma_R>0 σ 1 ≥ ⋯ ≥ σ R > 0 (R = rank ( A ) R=\operatorname{rank}(\mathbf{A}) R = rank ( A ) ). Let D = diag ( d 1 , … , d K ) \mathbf{D}=\operatorname{diag}(d_1,\ldots,d_K) D = diag ( d 1 , … , d K ) with d 1 ≥ ⋯ ≥ d K > 0 d_1\ge\cdots\ge d_K>0 d 1 ≥ ⋯ ≥ d K > 0 for some K ≥ R K\ge R K ≥ R .
(i) If ( U , V , D ) (\mathbf{U},\mathbf{V},\mathbf{D}) ( U , V , D ) is a DFD for A \mathbf{A} A , then ( U ~ , V ~ , D ) (\widetilde{\mathbf{U}},\widetilde{\mathbf{V}},\mathbf{D}) ( U , V , D ) , defined by
U ~ : = W T U , \widetilde{\mathbf{U}}:=\mathbf{W}^{\mathsf{T}}\mathbf{U}, U := W T U , V ~ : = Q T V , \widetilde{\mathbf{V}}:=\mathbf{Q}^{\mathsf{T}}\mathbf{V}, V := Q T V , is a DFD for Σ \boldsymbol{\Sigma} Σ .
(ii) Conversely, if ( U ~ , V ~ , D ) (\widetilde{U}, \widetilde{V}, D) ( U , V , D ) is a DFD for Σ \Sigma Σ , then ( U , V , D ) (U, V, D) ( U , V , D ) , defined by
U : = W U ~ , U := W\widetilde{U}, U := W U ,
V : = Q V ~ , V := Q\widetilde{V}, V := Q V ,
is a DFD for A A A .
In particular, U U U and U ~ \widetilde{U} U , as well as V V V and V ~ \widetilde{V} V , have the same frame bounds, respectively.
Proof. To prove (i), let ( U , V , D ) (U, V, D) ( U , V , D ) be a DFD for A A A . Since Q Q Q and W W W have orthonormal columns spanning ran ( A ) \operatorname{ran}(A) ran ( A ) and ker ( A ) ⊥ \ker(A)^\perp ker ( A ) ⊥ , respectively, U ~ \widetilde{U} U and V ~ \widetilde{V} V are again frames, and by Parseval’s identity the frame bounds of U U U and V V V are preserved.
It remains to show that ( U ~ , V ~ , D ) (\widetilde{U}, \widetilde{V}, D) ( U , V , D ) satisfies the quasi-singular relations for Σ \Sigma Σ . By the quasi-singular relation for A A A , we have A T V = U D T A^{\mathsf{T}}V = UD^{\mathsf{T}} A T V = U D T , and by the SVD, Σ T Q T = W T A T \Sigma^{\mathsf{T}}Q^{\mathsf{T}} = W^{\mathsf{T}}A^{\mathsf{T}} Σ T Q T = W T A T . Hence,
Σ T V ~ = Σ T Q T V = W T A T V = W T U D T = U ~ D . \Sigma^{\mathsf{T}}\widetilde{V} = \Sigma^{\mathsf{T}}Q^{\mathsf{T}}V = W^{\mathsf{T}}A^{\mathsf{T}}V = W^{\mathsf{T}}UD^{\mathsf{T}} = \widetilde{U}D. Σ T V = Σ T Q T V = W T A T V = W T U D T = U D .
Similarly, to prove (ii) the same argument for the frame bounds holds and using A T Q = W Σ T A^{\mathsf{T}}Q = W\Sigma^{\mathsf{T}} A T Q = W Σ T and Σ T V ~ = U ~ D T \Sigma^{\mathsf{T}}\widetilde{V} = \widetilde{U}D^{\mathsf{T}} Σ T V = U D T , we obtain
A T V = A T Q V ~ = W Σ T V ~ = W U ~ D T = U D T . A^{\mathsf{T}}V = A^{\mathsf{T}}Q\widetilde{V} = W\Sigma^{\mathsf{T}}\widetilde{V} = W\widetilde{U}D^{\mathsf{T}} = UD^{\mathsf{T}}. A T V = A T Q V = W Σ T V = W U D T = U D T .
Lemma 3.1 allows us to reduce the construction of tight DFDs for a general matrix to the corresponding problem for a positive diagonal matrix Σ ∈ R R × R \Sigma\in\mathbb{R}^{R \times R} Σ ∈ R R × R , where the characterization of a tight DFD is particularly simple. Since Σ \Sigma Σ has full rank, we have ker ( Σ ) ⊥ = ran ( Σ ) = R R \ker(\Sigma)^\perp= \operatorname{ran}(\Sigma) = \mathbb{R}^{R} ker ( Σ ) ⊥ = ran ( Σ ) = R R . Together with the normalization to Parseval frames, the frame conditions therefore reduce to U ~ U ~ T = I d R \widetilde{U}\widetilde{U}^{\mathsf{T}} = I_{d_R} U U T = I d R and V ~ V ~ T = I d R \widetilde{V}\widetilde{V}^{\mathsf{T}} = I_{d_R} V V T = I d R . In summary, solving (5) reduces to
min U ~ ∑ s = 1 S ∥ U ~ T W T x s ∥ ℓ 1 ( R K ) \min_{\widetilde{U}} \sum_{s=1}^{S} \left\lVert\widetilde{U}^{\mathsf{T}}W^{\mathsf{T}}x_s \right\rVert_{\ell_1(\mathbb{R}^{K})} U min s = 1 ∑ S U T W T x s ℓ 1 ( R K )
subject to: U ~ U ~ T = V ~ V ~ T = I d R \widetilde{U}\widetilde{U}^{\mathsf{T}} = \widetilde{V}\widetilde{V}^{\mathsf{T}} = I_{d_R} U U T = V V T = I d R and Σ V ~ = U ~ D \Sigma\widetilde{V} = \widetilde{U}D Σ V = U D , (3.2)
where Σ \Sigma Σ , W W W , Q Q Q , and X X X are given, while U ~ \widetilde{U} U , V ~ \widetilde{V} V , and D D D are to be determined. Then ( W U ~ , Q V ~ , D ) (W\widetilde{U}, Q\widetilde{V}, D) ( W U , Q V , D ) yields the desired DFD for A A A .
Predetermined quasi-singular values
The next simplification is that we can eliminate the variable V V V , since any DFD ( U , V , D ) (U, V, D) ( U , V , D ) of Σ \Sigma Σ satisfies V = Σ − 1 U D V = \Sigma^{-1}UD V = Σ − 1 U D . Hence, we can determine V V V once we have computed U ~ \widetilde{U} U (for a given D D D ). Exploiting this linear coupling between the frames, we arrive at the simpler form
min U ∑ s = 1 S ∥ U T W T x s ∥ ℓ 1 ( R K ) s.t. U ∈ C D : = { U ∈ R R × K | U U T = I d R , Σ − 1 U D 2 U T Σ − 1 = I d R } . (6) \min_{U} \sum_{s=1}^{S} \left\lVert U^{\mathsf{T}}W^{\mathsf{T}}x_s \right\rVert_{\ell_1(\mathbb{R}^{K})}
\qquad\text{s.t. } U \in\mathcal{C}_{D} := \left\{U \in\mathbb{R}^{R \times K} \,\middle|\, UU^{\mathsf{T}} = I_{d_R},\ \Sigma^{-1}UD^{2}U^{\mathsf{T}}\Sigma^{-1} = I_{d_R}\right\}. \tag*{(6)} U min s = 1 ∑ S U T W T x s ℓ 1 ( R K ) s.t. U ∈ C D := { U ∈ R R × K U U T = I d R , Σ − 1 U D 2 U T Σ − 1 = I d R } . (6)
If we fix the quasi-singular values D D D , the optimization reduces to a problem in the single variable U U U . It then remains to find a suitable strategy for choosing the quasi-singular values so that the objective in (6) is as small as possible. This is a challenging problem for which no general purpose answer can be given. However, we can characterize the choices of D D D for which a Parseval tight DFD exists, which gives us a numerical range of values to design potential candidates for the entries in the diagonal matrix D D D . The following proposition provides a necessary and sufficient feasibility condition and thus a potential criterion for selecting D D D . The result follows directly from the Fan–Pall theorem, stated in its original form for the real case in [25 Theorem 1] .
Theorem 3.2 (Fan–Pall). Let A ∈ R K × K \mathbf{A} \in\mathbb{R}^{K\times K} A ∈ R K × K and B ∈ R R × R \mathbf{B} \in\mathbb{R}^{R\times R} B ∈ R R × R be two symmetric matrices with K ≥ R K \ge R K ≥ R . Let α 1 ≥ ⋯ ≥ α K \alpha_1 \ge\cdots\ge\alpha_K α 1 ≥ ⋯ ≥ α K and β 1 ≥ ⋯ ≥ β R \beta_1 \ge\cdots\ge\beta_R β 1 ≥ ⋯ ≥ β R denote the eigenvalues of A \mathbf{A} A and B \mathbf{B} B , respectively. Then there exists a matrix C ∈ R K × R \mathbf{C} \in\mathbb{R}^{K\times R} C ∈ R K × R with C T C = I R \mathbf{C}^{\mathsf{T}}\mathbf{C} = \mathbf{I}_R C T C = I R such that C T A C = B \mathbf{C}^{\mathsf{T}}\mathbf{A}\mathbf{C} = \mathbf{B} C T AC = B if and only if
α i ≥ β i ≥ α i + K − R , i = 1 , … , R . \alpha_i \ge\beta_i \ge\alpha_{i+K-R}, \qquad i=1,\ldots,R. α i ≥ β i ≥ α i + K − R , i = 1 , … , R .
Proposition 3.3 (Characteristic of the feasible set). Let Σ = diag ( σ 1 , … , σ R ) ∈ R R × R \boldsymbol{\Sigma} = \operatorname{diag}(\sigma_1,\ldots,\sigma_R) \in\mathbb{R}^{R\times R} Σ = diag ( σ 1 , … , σ R ) ∈ R R × R with σ 1 ≥ ⋯ ≥ σ R > 0 \sigma_1 \ge\cdots\ge\sigma_R > 0 σ 1 ≥ ⋯ ≥ σ R > 0 and D = diag ( d 1 , … , d K ) \mathbf{D} = \operatorname{diag}(d_1,\ldots,d_K) D = diag ( d 1 , … , d K ) with d 1 ≥ ⋯ ≥ d K > 0 d_1 \ge\cdots\ge d_K > 0 d 1 ≥ ⋯ ≥ d K > 0 for some K ≥ R K \ge R K ≥ R . A necessary and sufficient condition for the set C D \mathcal{C}_{\mathbf{D}} C D to be non-empty is the inequality
d i ≥ σ i ≥ d i + K − R for i = 1 , … , R . (7) d_i \ge\sigma_i \ge d_{i+K-R} \qquad\text{for } i=1,\ldots,R. \tag*{(7)} d i ≥ σ i ≥ d i + K − R for i = 1 , … , R . (7)
Proof. In our setting, D 2 \mathbf{D}^2 D 2 and Σ 2 \boldsymbol{\Sigma}^2 Σ 2 are not only symmetric but also diagonal and positive definite, with their eigenvalues given by the diagonal entries. Therefore, condition (7) is necessary and sufficient for the existence of a matrix U ∈ R R × K \mathbf{U} \in\mathbb{R}^{R\times K} U ∈ R R × K satisfying U U T = I R \mathbf{U}\mathbf{U}^{\mathsf{T}} = \mathbf{I}_R U U T = I R and U D 2 U T = Σ 2 \mathbf{U}\mathbf{D}^2\mathbf{U}^{\mathsf{T}} = \boldsymbol{\Sigma}^2 U D 2 U T = Σ 2 . ■
Proposition 3.3 provides a necessary and sufficient condition for C D ≠ ∅ \mathcal{C}_{\mathbf{D}} \ne\varnothing C D = ∅ . In particular, if K > R K > R K > R , the construction of the scaling weights ( d i ) i = 1 K (d_i)_{i=1}^K ( d i ) i = 1 K only requires checking 2 R 2R 2 R inequalities. Since R R R is fixed for the problem under consideration, this verification has constant computational cost.
The choice of the number of scaling coefficients K K K has a direct impact on the flexibility of the resulting frame decomposition. In the limiting case K = R K = R K = R , the Parseval constraint leaves essentially no redundancy in the frame U \mathbf{U} U . A Parseval DFD only exists if ( d i ) i = 1 K = ( σ i ) (d_i)_{i=1}^K = (\sigma_i) ( d i ) i = 1 K = ( σ i ) , in which case U \mathbf{U} U can only be a signed permutation matrix and hence, can not be adapted to the data.
For K > R K > R K > R , the additional rows of U \mathbf{U} U provide additional degrees of freedom. This flexibility can be made precise by considering two choices D ~ ∈ R K ~ × K ~ \widetilde{\mathbf{D}} \in\mathbb{R}^{\widetilde{K}\times\widetilde{K}} D ∈ R K × K and D ∈ R K × K \mathbf{D} \in\mathbb{R}^{K\times K} D ∈ R K × K , with K ~ < K \widetilde{K} < K K < K , such that the diagonal entries of D ~ \widetilde{\mathbf{D}} D form a subset of those of D \mathbf{D} D . If U ~ ∈ C D ~ \widetilde{\mathbf{U}} \in\mathcal{C}_{\widetilde{\mathbf{D}}} U ∈ C D , then U \mathbf{U} U can be embedded into R K × R \mathbb{R}^{K\times R} R K × R by adding K − K ~ K-\widetilde{K} K − K zero rows (see Example 3.1 below). The resulting matrix belongs to C D \mathcal{C}_{\mathbf{D}} C D . Consequently, the feasible set for the larger value of K K K contains an embedded copy of the feasible set for the smaller one. Thus, increasing K K K can only improve the sparsity objective when additional scaling coefficients are added to D \mathbf{D} D . In practice, however, increasing K K K beyond a certain point may provide little additional benefit, as the additional rows of U \mathbf{U} U may simply converge to zero rather than contributing meaningful additional structure to the representation.
Example 3.1. We illustrate the flexibility of the frame decomposition. Let
Σ = ( 2 0 0 3 ) and D = ( 1 0 0 0 0 2 0 0 0 0 3 0 0 0 0 4 ) . \boldsymbol{\Sigma} =
\begin{pmatrix}
2 & 0\\
0 & 3
\end{pmatrix}
\quad\text{and}\quad
\mathbf{D} =
\begin{pmatrix}
1 & 0 & 0 & 0\\
0 & 2 & 0 & 0\\
0 & 0 & 3 & 0\\
0 & 0 & 0 & 4
\end{pmatrix}. Σ = ( 2 0 0 3 ) and D = 1 0 0 0 0 2 0 0 0 0 3 0 0 0 0 4 .
Then one can verify that the matrix
U 1 = ( 1 / 2 1 / 4 + 10 / 8 3 / 4 − 3 10 / 14 − 1 / 4 + 5 10 / 56 10 / 4 − 1 / 2 − 7 / 6 − 10 / 3 − 1 / 14 + 10 / 28 11 / 42 + 10 / 21 ) \mathbf{U}_1 =
\begin{pmatrix}
1/2 & \sqrt{1/4+\sqrt{10}/8} & \sqrt{3/4-3\sqrt{10}/14} & \sqrt{-1/4+5\sqrt{10}/56}\\
\sqrt{\sqrt{10}/4-1/2} & -\sqrt{7/6-\sqrt{10}/3} & -\sqrt{1/14+\sqrt{10}/28} & \sqrt{11/42+\sqrt{10}/21}
\end{pmatrix} U 1 = 1/2 10 /4 − 1/2 1/4 + 10 /8 − 7/6 − 10 /3 3/4 − 3 10 /14 − 1/14 + 10 /28 − 1/4 + 5 10 /56 11/42 + 10 /21
defines a Parseval frame as well as
V 1 = Σ − 1 U 1 D = ( 1 / 4 1 / 4 + 10 / 8 27 / 16 − 27 10 / 56 − 1 + 5 10 / 14 10 / 36 − 1 / 18 − 14 / 27 − 4 10 / 27 − 1 / 14 + 10 / 28 88 / 189 + 16 10 / 189 ) . \mathbf{V}_1 = \boldsymbol{\Sigma}^{-1}\mathbf{U}_1\mathbf{D} =
\begin{pmatrix}
1/4 & \sqrt{1/4+\sqrt{10}/8} & \sqrt{27/16-27\sqrt{10}/56} & \sqrt{-1+5\sqrt{10}/14}\\
\sqrt{\sqrt{10}/36-1/18} & -\sqrt{14/27-4\sqrt{10}/27} & -\sqrt{1/14+\sqrt{10}/28} & \sqrt{88/189+16\sqrt{10}/189}
\end{pmatrix}. V 1 = Σ − 1 U 1 D = 1/4 10 /36 − 1/18 1/4 + 10 /8 − 14/27 − 4 10 /27 27/16 − 27 10 /56 − 1/14 + 10 /28 − 1 + 5 10 /14 88/189 + 16 10 /189 .
On the other hand, consider
U 2 = ( 0 1 0 0 0 0 1 0 ) and V 2 = Σ − 1 U 2 D = ( 0 1 0 0 0 0 1 0 ) . U_2=\begin{pmatrix}0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0\end{pmatrix}
\quad\text{and}\quad
V_2=\Sigma^{-1}U_2\mathbf{D}=\begin{pmatrix}0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0\end{pmatrix}. U 2 = ( 0 0 1 0 0 1 0 0 ) and V 2 = Σ − 1 U 2 D = ( 0 0 1 0 0 1 0 0 ) .
These also define a Parseval DFD. Thus, for the same Σ \Sigma Σ and D \mathbf{D} D , there are multiple Parseval DFDs. In particular, the second choice selects the scaling coefficients 2 and 3, which exactly match the singular values of Σ \Sigma Σ , whereas the first choice distributes the contributions across all four scaling coefficients. This illustrates the additional flexibility provided by K > R K>R K > R .
The preceding observations show that the feasibility condition alone does not determine a suitable choice of D \mathbf{D} D . In particular, while D \mathbf{D} D must capture the spectral variation of Σ \Sigma Σ sufficiently well to ensure a small value of the lower-level objective, it should at the same time provide sufficient freedom for U \mathbf{U} U to adapt to the data. This leads to a trade-off between spectral compatibility and the sparsity-promoting objective in (6) . Moreover, the constrained problem over C D \mathcal{C}_{\mathbf{D}} C D remains potentially infeasible and computationally challenging. In the next subsection, we therefore relax the exact Parseval constraint for V \mathbf{V} V . This relaxation makes every choice of D \mathbf{D} D admissible and, at the same time, allows for a more flexible optimization over U \mathbf{U} U . We then introduce a data-driven heuristic for selecting the diagonal entries of D \mathbf{D} D .
Bilevel Optimization on the Stiefel Manifold
To obtain a numerically viable solution strategy, we adopt a relaxation approach in which the potentially inconsistent constraint U ∈ C D \mathbf{U}\in\mathcal{C}_{\mathbf{D}} U ∈ C D is replaced by the best approximation
{ U | U T ∈ arg min U ∈ St ( K , R ) ∥ Σ − 1 U T D 2 U Σ − 1 − I d R ∥ F 2 } . \left\{\mathbf{U}\,\middle|\,\mathbf{U}^{\mathsf T}\in\underset{\mathbf{U}\in\operatorname{St}(K,R)}{\arg\min}\left\|\Sigma^{-1}\mathbf{U}^{\mathsf T}\mathbf{D}^{2}\mathbf{U}\Sigma^{-1}-\mathbf{I}_{d_R}\right\|_{\mathrm{F}}^{2}\right\}. { U U T ∈ U ∈ St ( K , R ) arg min Σ − 1 U T D 2 U Σ − 1 − I d R F 2 } .
Recall from § 2.2 that the set of all transposed Parseval frames can be identified with the Stiefel manifold St ( K , R ) \operatorname{St}(K,R) St ( K , R ) . In the following, we use U ∈ St ( K , R ) \mathbf{U}\in\operatorname{St}(K,R) U ∈ St ( K , R ) as the optimization variable, with the corresponding Parseval frame given by U T \mathbf{U}^{\mathsf T} U T . With this notational convention, we formulate the problem using an outer approximation of the feasibility constraint. This leads to the following simple bilevel optimization problem [19 ] over the Stiefel manifold:
min U ∈ S ϕ ( U ) : = ∥ U W T X ∥ 1 , S : = arg min U ∈ St ( K , R ) Ψ ( U ) : = ∥ Σ − 1 U T D 2 U Σ − 1 − I d R ∥ F 2 . (8) \underset{\mathbf{U}\in\mathcal{S}}{\min}\ \phi(\mathbf{U}):=\|\mathbf{U}\mathbf{W}^{\mathsf T}\mathbf{X}\|_1,
\qquad
\mathcal{S}:=\underset{\mathbf{U}\in\operatorname{St}(K,R)}{\arg\min}\ \Psi(\mathbf{U}):=\left\|\Sigma^{-1}\mathbf{U}^{\mathsf T}\mathbf{D}^{2}\mathbf{U}\Sigma^{-1}-\mathbf{I}_{d_R}\right\|_{\mathrm{F}}^{2}. \tag*{(8)} U ∈ S min ϕ ( U ) := ∥ U W T X ∥ 1 , S := U ∈ St ( K , R ) arg min Ψ ( U ) := Σ − 1 U T D 2 U Σ − 1 − I d R F 2 . (8)
The upper level problem is the data-driven sparsity term in order to inject into the learned frames the structure of the data underlying. Our bilevel formulation of the frame learning problem allows us to perform our optimization even if the scaling factors D \mathbf{D} D are badly chosen, so that C D = ∅ \mathcal{C}_{\mathbf{D}}=\varnothing C D = ∅ . Indeed, if D \mathbf{D} D is chosen so that C D ≠ ∅ \mathcal{C}_{\mathbf{D}}\ne\varnothing C D = ∅ , then Ψ ( S ) = 0 \Psi(\mathcal{S})=0 Ψ ( S ) = 0 and the original problem is solved exactly. If C D ≠ ∅ \mathcal{C}_{\mathbf{D}}\ne\varnothing C D = ∅ , we still obtain a DFD in which U \mathbf{U} U is a Parseval frame, and the frame bounds of V \mathbf{V} V can be controlled in terms of the value of the lower-level objective function on the solution set.
Proposition 3.4. Let U ∈ St ( K , R ) \mathbf{U}\in\operatorname{St}(K,R) U ∈ St ( K , R ) and define V = Σ − 1 U T D \mathbf{V}=\Sigma^{-1}\mathbf{U}^{\mathsf T}\mathbf{D} V = Σ − 1 U T D . Suppose Ψ ( U ) = ϵ < 1 \Psi(\mathbf{U})=\epsilon<1 Ψ ( U ) = ϵ < 1 . Then ( U T , V , D ) (\mathbf{U}^{\mathsf T},\mathbf{V},\mathbf{D}) ( U T , V , D ) is a DFD for Σ \Sigma Σ , where U T \mathbf{U}^{\mathsf T} U T is a Parseval frame and V \mathbf{V} V has lower and upper frame bounds 1 − ϵ 1-\epsilon 1 − ϵ and 1 + ϵ 1+\epsilon 1 + ϵ , respectively.
Proof. U T \mathbf{U}^{\mathsf T} U T is a Parseval tight frame. By the fact that the spectral norm is bounded above by the Frobenius norm and the definition of V \mathbf{V} V , we have
∥ I d R − V V T ∥ 2 ≤ ∥ I d R − V V T ∥ F = Ψ ( U ) = ϵ \left\|\mathbf{I}_{d_R}-\mathbf{V}\mathbf{V}^{\mathsf T}\right\|_2\le\left\|\mathbf{I}_{d_R}-\mathbf{V}\mathbf{V}^{\mathsf T}\right\|_{\mathrm{F}}=\Psi(\mathbf{U})=\epsilon I d R − V V T 2 ≤ I d R − V V T F = Ψ ( U ) = ϵ
hence, the eigenvalues of V V T \mathbf{V}\mathbf{V}^{\mathsf T} V V T are in the interval [ 1 − ϵ , 1 + ϵ ] [1-\epsilon,1+\epsilon] [ 1 − ϵ , 1 + ϵ ] . ▪
For the application to filtered reconstruction of inverse problems, it is not essential that V V V be a Parseval or tight frame. Although computing its canonical dual would be more involved, this is not required in our reconstruction method, where only the dual of U U U is needed. Nevertheless, the stability of the reconstruction depends, among other factors, on the frame bounds, or equivalently the condition number, of V V V . These need not be equal to one, but should remain reasonably well-conditioned. A key requirement for a DFD is that the ill-conditioning of Σ \Sigma Σ , and hence of A A A , is captured by D D D , since the corresponding components are subsequently filtered. To illustrate this, consider the extreme choice D = I d K D = \mathrm{Id}_{K} D = Id K . For any Parseval frame U U U , the corresponding frame V = Σ − 1 U V = \Sigma^{-1}U V = Σ − 1 U inherits the ill-conditioning of Σ \Sigma Σ ; in particular, its condition number can be as large as that of Σ \Sigma Σ . Thus, the primary objective in choosing D D D is to ensure that min Ψ \min\Psi min Ψ is zero or sufficiently small, which generally requires D D D to capture the dominant spectral variation of Σ \Sigma Σ . Among such choices, D D D should then be selected to promote sparsity in U U U .
A heuristic way to compute the diagonal entries of D D D that incorporates the structure of the data is as follows. Let X X T = Q X Λ Q X T XX^{\mathsf{T}} = Q_X\Lambda Q_X^{\mathsf{T}} X X T = Q X Λ Q X T be the eigendecomposition of X X T XX^{\mathsf{T}} X X T . We define
d ^ = ( d ^ i ) i = 1 K = argmin d ∥ Σ − 1 W T Q X diag ( d ) 2 Q X T W Σ − 1 − I d R ∥ F 2 \widehat{\mathbf{d}} = (\widehat{d}_i)_{i=1}^{K} = \underset{\mathbf{d}}{\operatorname{argmin}}\left\lVert\Sigma^{-1}W^{\mathsf{T}}Q_X\operatorname{diag}(\mathbf{d})^2Q_X^{\mathsf{T}}W\Sigma^{-1} - \mathrm{Id}_{R}\right\rVert_F^2 d = ( d i ) i = 1 K = d argmin Σ − 1 W T Q X diag ( d ) 2 Q X T W Σ − 1 − Id R F 2
and choose D = diag ( d 1 , … , d K ) D = \operatorname{diag}(d_1,\ldots,d_K) D = diag ( d 1 , … , d K ) with
d i = { d ^ i where d ^ i > ϵ , ∥ Σ ∥ F 2 / R otherwise. (9) d_i =
\begin{cases}
\widehat{d}_i & \text{where } \widehat{d}_i > \epsilon,\\
\lVert\Sigma\rVert_F^2/R & \text{otherwise.}
\end{cases} \tag*{(9)} d i = { d i ∥ Σ ∥ F 2 / R where d i > ϵ , otherwise. (9)
Thus, the resulting scaling coefficients are adapted to the dominant directions of the data while simultaneously taking the spectral scaling induced by Σ \Sigma Σ into account. In particular, this choice aims to align the frame U U U with directions that are relevant to the data while keeping the lower-level objective Ψ \Psi Ψ small, but not necessarily zero. In practice, some of the coefficients d ^ i \widehat{d}_i d i may become very small or vanish. Such coefficients provide little additional freedom for the frame and may lead to degenerate frame elements. We therefore replace coefficients below a prescribed threshold ϵ \epsilon ϵ with a neutral scaling value.
Although (9) favors sparsity in the frame U U U , it may still lead to large values of the lower-level objective Ψ \Psi Ψ and, consequently, a high condition number of the resulting frame V V V . This can potentially cause instability when the frame is used for regularization in inverse problems. As an alternative, the diagonal entries can be chosen independently of the data using the following construction, which is designed to satisfy the conditions of the Fan–Pall theorem. The practical implications of this choice depend on the application and will be investigated numerically in § 5 .
d i 2 = { 1 i ∑ j = 1 i σ j 2 , 1 ≤ i ≤ K − R + 1 ∧ i ≤ R , 1 K − R + 1 ∑ j = i − K + R i σ j 2 , K − R + 2 ≤ i ≤ R , 1 K − i + 1 ∑ j = i − K + R R σ j 2 , R + 1 ≤ i ≤ K . (10) d_i^2 =
\begin{cases}
\frac{1}{i}\sum_{j=1}^{i}\sigma_j^2, & 1 \le i \le K-R+1 \land i \le R,\\
\frac{1}{K-R+1}\sum_{j=i-K+R}^{i}\sigma_j^2, & K-R+2 \le i \le R,\\
\frac{1}{K-i+1}\sum_{j=i-K+R}^{R}\sigma_j^2, & R+1 \le i \le K.
\end{cases} \tag*{(10)} d i 2 = ⎩ ⎨ ⎧ i 1 ∑ j = 1 i σ j 2 , K − R + 1 1 ∑ j = i − K + R i σ j 2 , K − i + 1 1 ∑ j = i − K + R R σ j 2 , 1 ≤ i ≤ K − R + 1 ∧ i ≤ R , K − R + 2 ≤ i ≤ R , R + 1 ≤ i ≤ K . (10)
The Numerical Scheme
In this section, we describe a general numerical scheme for computing data-aware DFDs. Since our complexity statements apply to a rather broad class of optimal design problems, we keep the presentation at an abstract level. Throughout this section, we use both Euclidean and Riemannian derivatives. To distinguish between the two, we denote Riemannian quantities by the subscript St. The relevant tools for optimization on the Stiefel manifold are summarized in Appendix § 10 .
Let U ⊂ R K × R \mathcal{U} \subset\mathbb{R}^{K \times R} U ⊂ R K × R be an open, convex, and bounded neighborhood of St ( K , R ) \operatorname{St}(K,R) St ( K , R ) . We consider the simple bilevel optimization problem
min U ∈ S ϕ ( U ) , S : = argmin U ∈ St ( K , R ) Ψ ( U ) , (11) \min_{U \in\mathcal{S}} \phi(U), \qquad\mathcal{S} := \underset{U \in\operatorname{St}(K,R)}{\operatorname{argmin}} \Psi(U), \tag*{(11)} U ∈ S min ϕ ( U ) , S := U ∈ St ( K , R ) argmin Ψ ( U ) , (11)
where the functions ϕ : U → R \phi: \mathcal{U} \to\mathbb{R} ϕ : U → R and Ψ : U → R \Psi: \mathcal{U} \to\mathbb{R} Ψ : U → R satisfy the following assumptions:
ϕ \phi ϕ is convex and lower semicontinuous;
Ψ \Psi Ψ is continuously differentiable with a Lipschitz continuous Euclidean gradient:
∥ ∇ Ψ ( U 1 ) − ∇ Ψ ( U 2 ) ∥ ≤ L ∇ Ψ ∥ U 1 − U 2 ∥ for all U 1 , U 2 ∈ U . \lVert\nabla\Psi(U_1) - \nabla\Psi(U_2) \rVert\le L_{\nabla\Psi}\lVert U_1 - U_2 \rVert\qquad\text{for all } U_1,U_2 \in\mathcal{U}. ∥ ∇Ψ ( U 1 ) − ∇Ψ ( U 2 )∥ ≤ L ∇Ψ ∥ U 1 − U 2 ∥ for all U 1 , U 2 ∈ U .
The lower-level problem determines the feasible set S \mathcal{S} S through the minimizers of the smooth function Ψ \Psi Ψ on the Stiefel manifold, while the upper-level objective ϕ \phi ϕ selects a preferred solution among these minimizers. This model formulation allows us to approach a solution of Problem 1 by identifying the data as in (8) .
Note that, since the Stiefel manifold is not convex, the restriction of ϕ \phi ϕ to St \operatorname{St} St is generally not convex. However, by compactness of St \operatorname{St} St and convexity of ϕ \phi ϕ on U \mathcal{U} U , ϕ ∣ St \phi|_{\operatorname{St}} ϕ ∣ St is Lipschitz continuous with some constant L ϕ L_\phi L ϕ . The same holds for the restriction Ψ ∣ St \Psi|_{\operatorname{St}} Ψ ∣ St , which is Lipschitz continuous with some constant L Ψ L_\Psi L Ψ . Moreover, since Ψ \Psi Ψ has a L ∇ Ψ L_{\nabla\Psi} L ∇Ψ -Lipschitz continuous Euclidean gradient on U \mathcal{U} U , it is L ∇ Ψ L_{\nabla\Psi} L ∇Ψ -weakly convex on U \mathcal{U} U . We recall that a function f : U → R f : \mathcal{U} \to\mathbb{R} f : U → R is called τ \tau τ -weakly convex if f + τ ∥ ⋅ ∥ 2 / 2 f + \tau\lVert\cdot\rVert^2/2 f + τ ∥ ⋅ ∥ 2 /2 is convex for some τ ≥ 0 \tau\ge0 τ ≥ 0 . Furthermore, since the Stiefel manifold St \operatorname{St} St is compact and ϕ \phi ϕ is convex on the open set U \mathcal{U} U , the restriction ϕ ∣ St \phi|_{\operatorname{St}} ϕ ∣ St is continuous and hence attains both its minimum and maximum on St \operatorname{St} St . Likewise, since Ψ \Psi Ψ is continuously differentiable on U \mathcal{U} U , both Ψ ∣ St \Psi|_{\operatorname{St}} Ψ ∣ St and ∥ ∇ Ψ ∥ St \lVert\nabla\Psi\rVert_{\operatorname{St}} ∥ ∇Ψ ∥ St attain their respective minimum and maximum on St \operatorname{St} St . In particular, also the Riemannian gradient ∇ St Ψ \nabla_{\operatorname{St}}\Psi ∇ St Ψ is Lipschitz continuous on St \operatorname{St} St with the constant
L ∇ St Ψ = L ∇ Ψ + 2 max U ∈ St ∥ ∇ Ψ ( U ) ∥ F . L_{\nabla_{\operatorname{St}}\Psi} = L_{\nabla\Psi} + 2 \max_{U \in\operatorname{St}} \lVert\nabla\Psi(U)\rVert_F. L ∇ St Ψ = L ∇Ψ + 2 U ∈ St max ∥ ∇Ψ ( U ) ∥ F .
Remark 4.1. Note that the Ψ \Psi Ψ defined in (8) can be extended to the Euclidean space R K × R \mathbb{R}^{K \times R} R K × R but fails to be Lipschitz smooth on the full domain. However, the claimed Lipschitz smoothness holds on any bounded neighborhood of the Stiefel manifold St \operatorname{St} St .
Penalty Subgradient Method on the Stiefel Manifold
To approximate a solution of problem (11) , we extend recent algorithmic advances for weakly convex minimization over the Stiefel manifold [31 ] to simultaneously address both levels of the problem. To this end, we adopt the generalized Tikhonov regularization approach of [37 ] and consider the time-varying auxiliary objective function
Ω k ( U ) : = ϕ ( U ) + β k Ψ ( U ) : U → R (12) \Omega_k(U) := \phi(U) + \beta_k \Psi(U) : \mathcal{U} \to\mathbb{R} \tag*{(12)} Ω k ( U ) := ϕ ( U ) + β k Ψ ( U ) : U → R (12)
Algorithm 1 Riemannian Penalty Subgradient Method
Require: U 0 ∈ St ( K , R ) U^0 \in\operatorname{St}(K,R) U 0 ∈ St ( K , R ) , step sizes ( γ k ) k (\gamma_k)_k ( γ k ) k , penalty parameters ( β k ) k (\beta_k)_k ( β k ) k
for k = 0 , 1 , … k = 0,1,\ldots k = 0 , 1 , … do
Evaluate the Euclidean gradient ∇ Ψ ( U k ) \nabla\Psi(U^k) ∇Ψ ( U k ) and select g ~ k ∈ ∂ ϕ ( U k ) \tilde{g}^k \in\partial\phi(U^k) g ~ k ∈ ∂ ϕ ( U k ) .
Compute the Riemannian gradient and subgradient:
∇ St Ψ ( U k ) = Proj T U k St ( ∇ Ψ ( U k ) ) \nabla_{\operatorname{St}}\Psi(U^k) = \operatorname{Proj}_{T_{U^k}\operatorname{St}}\left(\nabla\Psi(U^k)\right) ∇ St Ψ ( U k ) = Proj T U k St ( ∇Ψ ( U k ) )
g k = Proj T U k St ( g ~ k ) ∈ ∂ St ϕ ( U k ) , Proj T A St ( V ) = V − A A T V + V T A 2 g^k = \operatorname{Proj}_{T_{U^k}\operatorname{St}}(\tilde{g}^k) \in\partial_{\operatorname{St}}\phi(U^k), \qquad\operatorname{Proj}_{T_A\operatorname{St}}(V) = V - A\frac{A^\mathsf{T}V + V^\mathsf{T}A}{2} g k = Proj T U k St ( g ~ k ) ∈ ∂ St ϕ ( U k ) , Proj T A St ( V ) = V − A 2 A T V + V T A
Take a tangent-space step:
U + k = U k − γ k ( g k + β k ∇ St Ψ ( U k ) ) U^k_+ = U^k - \gamma_k\left(g^k + \beta_k\nabla_{\operatorname{St}}\Psi(U^k)\right) U + k = U k − γ k ( g k + β k ∇ St Ψ ( U k ) )
Retract onto the Stiefel manifold:
U k + 1 = Proj St ( U + k ) , Proj St ( V ) = Q W T with SVD V = Q Λ W T U^{k+1} = \operatorname{Proj}_{\operatorname{St}}(U^k_+), \qquad\operatorname{Proj}_{\operatorname{St}}(V) = QW^\mathsf{T}\ \text{with SVD}\ V = Q\Lambda W^\mathsf{T} U k + 1 = Proj St ( U + k ) , Proj St ( V ) = Q W T with SVD V = Q Λ W T
end for
where ( β k ) k (\beta_k)_k ( β k ) k is non-decreasing penalty sequence, formally going to infinity. By Theorem 4.1 in [44 ] , this is a regular function, and thus ∂ St Ω k ( U ) = ∂ St ϕ ( U ) + β k ∇ St Ψ ( U ) \partial_{\operatorname{St}}\Omega_k(U) = \partial_{\operatorname{St}}\phi(U) + \beta_k\nabla_{\operatorname{St}}\Psi(U) ∂ St Ω k ( U ) = ∂ St ϕ ( U ) + β k ∇ St Ψ ( U ) . The penalty term increasingly promotes minimization of the lower-level objective Ψ \Psi Ψ , while the term ϕ \phi ϕ selects a preferred solution among the lower-level minimizers. This auxiliary function is injected into a Riemannian subgradient-type method, analyzed in [31 ] for the stationary case ( β k ≡ β ) (\beta_k \equiv\beta) ( β k ≡ β ) . A single iteration reads as
U k + 1 = Proj St ( U k − γ k ( g k + β k ∇ St Ψ ( U k ) ) ) , g k ∈ ∂ St ϕ ( U k ) , (13) U^{k+1} = \operatorname{Proj}_{\operatorname{St}}\left(U^k - \gamma_k\left(g^k + \beta_k\nabla_{\operatorname{St}}\Psi(U^k)\right)\right), \qquad g^k \in\partial_{\operatorname{St}}\phi(U^k), \tag*{(13)} U k + 1 = Proj St ( U k − γ k ( g k + β k ∇ St Ψ ( U k ) ) ) , g k ∈ ∂ St ϕ ( U k ) , (13)
where ( γ k ) k (\gamma_k)_k ( γ k ) k denotes the sequence of step sizes. The Riemannian gradient and subgradient ensure that the search direction lies in the tangent space of the Stiefel manifold, while the orthogonal projection maps the updated point back onto the manifold and thus serves as a retraction. This procedure is briefly discussed below and more detailed in the Appendix. The precise formulation of the resulting method is given in Algorithm 1. The convergence properties of the method are established in the subsequent section.
Gradients and subgradients on the Stiefel manifold. Since St ( K , R ) \operatorname{St}(K,R) St ( K , R ) is an embedded submanifold of R K × R \mathbb{R}^{K \times R} R K × R , the Riemannian gradient of Ψ \Psi Ψ can be obtained by projecting its Euclidean gradient onto the tangent space
∇ St Ψ ( U ) = Proj T U St ( ∇ Ψ ( U ) ) . \nabla_{\operatorname{St}}\Psi(U) = \operatorname{Proj}_{T_U\operatorname{St}}(\nabla\Psi(U)). ∇ St Ψ ( U ) = Proj T U St ( ∇Ψ ( U )) .
For the generally nondifferentiable convex function ϕ \phi ϕ , the projection of its Euclidean subdifferential onto the tangent space gives the Clarke subdifferential of its restriction to the Stiefel manifold
∂ St ϕ ( U ) = Proj T U St ( ∂ ϕ ( U ) ) . \partial_{\operatorname{St}}\phi(U) = \operatorname{Proj}_{T_U\operatorname{St}}(\partial\phi(U)). ∂ St ϕ ( U ) = Proj T U St ( ∂ ϕ ( U )) .
This follows from [44 Thm. 5.1] , since the restriction of ϕ \phi ϕ to the Stiefel manifold is Lipschitz continuous.
Retractions on the Stiefel manifold. Since tangent vectors do not generally remain on the manifold after an explicit update step, a retraction is used to map the resulting point back onto St. In this work, we employ the polar decomposition-based retraction to exploit its nonexpansiveness.
Convergence Analysis
Since the bilevel design problem (11) is generally nonsmooth and nonconvex on the Stiefel manifold, convergence to global minimizers cannot be expected in general. Instead, we establish asymptotic convergence to suitably defined stationary points. To quantify stationarity, we follow the approach of [31 ] and use a Moreau-type envelope. For λ > 0 \lambda> 0 λ > 0 and a τ \tau τ -weakly convex function h : U → R h:\mathcal{U}\to\mathbb{R} h : U → R , we define
h λ ( U ) = min V ∈ St ( K , R ) { h ( V ) + 1 2 λ ∥ V − U ∥ F 2 } , U ∈ St ( K , R ) , prox λ h ( U ) = argmin V ∈ St ( K , R ) { h ( V ) + 1 2 λ ∥ V − U ∥ F 2 } , U ∈ St ( K , R ) . (14) \begin{aligned}
h_{\lambda}(\mathbf{U}) &= \min_{\mathbf{V}\in\operatorname{St}(K,\mathbb{R})}\left\{h(\mathbf{V})+\frac{1}{2\lambda}\lVert\mathbf{V}-\mathbf{U}\rVert_{F}^{2}\right\}, && \mathbf{U}\in\operatorname{St}(K,\mathbb{R}),\\
\operatorname{prox}_{\lambda h}(\mathbf{U}) &= \underset{\mathbf{V}\in\operatorname{St}(K,\mathbb{R})}{\operatorname{argmin}}\left\{h(\mathbf{V})+\frac{1}{2\lambda}\lVert\mathbf{V}-\mathbf{U}\rVert_{F}^{2}\right\}, && \mathbf{U}\in\operatorname{St}(K,\mathbb{R}). \tag*{(14)}
\end{aligned} h λ ( U ) prox λh ( U ) = V ∈ St ( K , R ) min { h ( V ) + 2 λ 1 ∥ V − U ∥ F 2 } , = V ∈ St ( K , R ) argmin { h ( V ) + 2 λ 1 ∥ V − U ∥ F 2 } , U ∈ St ( K , R ) , U ∈ St ( K , R ) . (14)
Note that the proximal mapping need not be single-valued in general. However, the particular choice of U ^ ∈ prox λ h ( U ) \widehat{\mathbf{U}}\in\operatorname{prox}_{\lambda h}(\mathbf{U}) U ∈ prox λh ( U ) does not affect the subsequent analysis, since every proximal point satisfies the same first-order optimality condition. Throughout, whenever prox λ h ( U ) \operatorname{prox}_{\lambda h}(\mathbf{U}) prox λh ( U ) is used as a point, we refer to an arbitrary selection from the proximal mapping. For U ^ ∈ prox λ h ( U ) \widehat{\mathbf{U}}\in\operatorname{prox}_{\lambda h}(\mathbf{U}) U ∈ prox λh ( U ) , the first-order optimality condition gives
0 ∈ ∂ St h ( U ^ ) + 1 λ Proj T U ^ St ( U ^ − U ) . 0\in\partial_{\operatorname{St}}h(\widehat{\mathbf{U}})+\frac{1}{\lambda}\operatorname{Proj}_{T_{\widehat{\mathbf{U}}}\operatorname{St}}(\widehat{\mathbf{U}}-\mathbf{U}). 0 ∈ ∂ St h ( U ) + λ 1 Proj T U St ( U − U ) .
Consequently,
dist ( 0 , ∂ St h ( U ^ ) ) ≤ λ − 1 ∥ Proj T U ^ St ( U ^ − U ) ∥ F ≤ λ − 1 ∥ U ^ − U ∥ F = : Θ λ h ( U ) . (15) \operatorname{dist}(0,\partial_{\operatorname{St}}h(\widehat{\mathbf{U}}))\leq\lambda^{-1}\left\lVert\operatorname{Proj}_{T_{\widehat{\mathbf{U}}}\operatorname{St}}(\widehat{\mathbf{U}}-\mathbf{U})\right\rVert_{F}\leq\lambda^{-1}\lVert\widehat{\mathbf{U}}-\mathbf{U}\rVert_{F}=:\Theta_{\lambda h}(\mathbf{U}). \tag*{(15)} dist ( 0 , ∂ St h ( U )) ≤ λ − 1 Proj T U St ( U − U ) F ≤ λ − 1 ∥ U − U ∥ F =: Θ λh ( U ) . (15)
Thus, Θ λ h \Theta_{\lambda h} Θ λh provides a stationarity measure for h h h . In particular, Θ λ h ( U ) = 0 \Theta_{\lambda h}(\mathbf{U})=0 Θ λh ( U ) = 0 implies U ^ = U \widehat{\mathbf{U}}=\mathbf{U} U = U and hence 0 ∈ ∂ St h ( U ) 0\in\partial_{\operatorname{St}}h(\mathbf{U}) 0 ∈ ∂ St h ( U ) . This framework is applied to both levels of the bilevel problem. For the lower-level objective, we use Θ λ Ψ \Theta_{\lambda\Psi} Θ λ Ψ , which measures violation of lower-level stationarity. In particular, since Ψ \Psi Ψ is differentiable with Lipschitz continuous Riemannian gradient, we have
∥ ∇ St Ψ ( U ) ∥ F ≤ L ∇ St Ψ ∥ U − U ^ ∥ F + ∥ ∇ St Ψ ( U ^ ) ∥ F ≤ ( L ∇ St Ψ λ + 1 ) Θ λ Ψ ( U ) . (16) \lVert\nabla_{\operatorname{St}}\Psi(\mathbf{U})\rVert_{F}\leq L_{\nabla_{\operatorname{St}}\Psi}\lVert\mathbf{U}-\widehat{\mathbf{U}}\rVert_{F}+\lVert\nabla_{\operatorname{St}}\Psi(\widehat{\mathbf{U}})\rVert_{F}\leq\left(L_{\nabla_{\operatorname{St}}\Psi}\lambda+1\right)\Theta_{\lambda\Psi}(\mathbf{U}). \tag*{(16)} ∥ ∇ St Ψ ( U ) ∥ F ≤ L ∇ St Ψ ∥ U − U ∥ F + ∥ ∇ St Ψ ( U ) ∥ F ≤ ( L ∇ St Ψ λ + 1 ) Θ λ Ψ ( U ) . (16)
For the penalized objective Ω k = ϕ + β k Ψ \Omega_k=\phi+\beta_k\Psi Ω k = ϕ + β k Ψ , we consider β k Θ λ Ω k / β k \beta_k\Theta_{\lambda\Omega_k/\beta_k} β k Θ λ Ω k / β k , as a measure of upper-level stationarity. In particular, (15) yields the bound
dist ( 0 , ∂ St Ω k ( prox λ Ω k / β k ( U ) ) ) ≤ β k Θ λ Ω k / β k ( U ) . \operatorname{dist}(0,\partial_{\operatorname{St}}\Omega_k(\operatorname{prox}_{\lambda\Omega_k/\beta_k}(\mathbf{U})))\leq\beta_k\Theta_{\lambda\Omega_k/\beta_k}(\mathbf{U}). dist ( 0 , ∂ St Ω k ( prox λ Ω k / β k ( U ))) ≤ β k Θ λ Ω k / β k ( U ) .
Another key technical tool in our analysis is the following Riemannian subgradient inequality on the Stiefel manifold for weakly convex functions, taken from [31 Theorem 1] .
Theorem 4.1 (Riemannian sugradient inequality). Let U ⊂ R K × R \mathcal{U}\subset\mathbb{R}^{K\times R} U ⊂ R K × R be any bounded, open, and convex set that contains St ( K , R ) \operatorname{St}(K,R) St ( K , R ) . Suppose that h : U → R h:\mathcal{U}\to\mathbb{R} h : U → R is τ \tau τ -weakly convex for some τ ≥ 0 \tau\geq0 τ ≥ 0 . Then, there exists a constant L > 0 L>0 L > 0 such that h h h is L L L -Lipschitz continuous on St ( K , R ) \operatorname{St}(K,R) St ( K , R ) and satisfies
h ( V ) ≥ h ( U ) + ⟨ ∇ ~ St h ( U ) , V − U ⟩ − τ + L 2 ∥ V − U ∥ F 2 h(\mathbf{V})\geq h(\mathbf{U})+\left\langle\widetilde{\nabla}_{\operatorname{St}}h(\mathbf{U}),\mathbf{V}-\mathbf{U}\right\rangle-\frac{\tau+L}{2}\lVert\mathbf{V}-\mathbf{U}\rVert_{F}^{2} h ( V ) ≥ h ( U ) + ⟨ ∇ St h ( U ) , V − U ⟩ − 2 τ + L ∥ V − U ∥ F 2 for all
∇ ~ St h ( U ) ∈ ∂ St h ( U ) , U , V ∈ St ( K , R ) . \widetilde{\nabla}_{\operatorname{St}}h(\mathbf{U})\in\partial_{\operatorname{St}}h(\mathbf{U}),\qquad\mathbf{U},\mathbf{V}\in\operatorname{St}(K,R). ∇ St h ( U ) ∈ ∂ St h ( U ) , U , V ∈ St ( K , R ) .
Compared to the corresponding Euclidean inequality for weakly convex functions (B.1), the Riemannian inequality contains the additional term L L L , where L L L is a Lipschitz constant of h h h on St. This additional term arises from restricting h h h to the nonconvex Stiefel manifold and accounts for the geometry of the manifold. For τ = 0 \tau= 0 τ = 0 , the inequality reduces to the corresponding Riemannian subgradient inequality for convex functions. In the smooth case, the Riemannian subgradient is replaced by the Riemannian gradient. Thus, the inequality provides a unified first-order estimate for the smooth lower-level objective and the potentially nonsmooth penalized objectives considered here.
We first investigate the decrease of the stationarity measure associated with the lower-level problem. Recall that ϕ ∣ S t \phi|_{\mathrm{St}} ϕ ∣ St is L ϕ L_{\phi} L ϕ -Lipschitz continuous, Ψ ∣ S t \Psi|_{\mathrm{St}} Ψ ∣ St is L Ψ L_{\Psi} L Ψ -Lipschitz continuous, and Ψ \Psi Ψ is L ∇ Ψ L_{\nabla\Psi} L ∇Ψ -weakly convex on U \mathcal{U} U .
Proposition 4.2. Let { U k } \{\mathrm{U}^{k}\} { U k } be the sequence generated by (13) with arbitrary initialization, step sizes ( γ k ) k (\gamma_k)_k ( γ k ) k and penalty parameters ( β k ) k (\beta_k)_k ( β k ) k . Then, for every λ < ( L ∇ Ψ + L Ψ + L ϕ / β 0 ) − 1 \lambda< (L_{\nabla\Psi} + L_{\Psi} + L_{\phi}/\beta_0)^{-1} λ < ( L ∇Ψ + L Ψ + L ϕ / β 0 ) − 1 , the following estimate holds for all k ≥ 0 k \ge0 k ≥ 0 :
λ 2 Θ λ Ψ ( U k ) ≤ ( b k + b k 2 − 4 a k c k 2 ∣ a k ∣ ) 2 ≤ b k 2 a k 2 + 2 c k ∣ a k ∣ (17) \lambda^2\Theta_{\lambda\Psi}(\mathrm{U}^k) \le\left(\frac{b_k+\sqrt{b_k^2-4a_kc_k}}{2|a_k|}\right)^2 \le\frac{b_k^2}{a_k^2}+\frac{2c_k}{|a_k|} \tag*{(17)} λ 2 Θ λ Ψ ( U k ) ≤ ( 2∣ a k ∣ b k + b k 2 − 4 a k c k ) 2 ≤ a k 2 b k 2 + ∣ a k ∣ 2 c k (17) where
a k = γ k 2 λ ( L ϕ + β k ( L ∇ Ψ + L Ψ − 1 λ ) ) (18) a_k = \frac{\gamma_k}{2\lambda}\left(L_{\phi}+\beta_k\left(L_{\nabla\Psi}+L_{\Psi}-\frac{1}{\lambda}\right)\right) \tag*{(18)} a k = 2 λ γ k ( L ϕ + β k ( L ∇Ψ + L Ψ − λ 1 ) ) (18) b k = γ k λ L ϕ (19) b_k = \frac{\gamma_k}{\lambda}L_{\phi} \tag*{(19)} b k = λ γ k L ϕ (19) c k = ( Ψ λ ( U k ) − Ψ λ ( U k + 1 ) ) + γ k 2 2 λ ( β k L Ψ + L ϕ ) 2 . (20) c_k = \left(\Psi_{\lambda}(\mathrm{U}^k)-\Psi_{\lambda}(\mathrm{U}^{k+1})\right)+\frac{\gamma_k^2}{2\lambda}(\beta_kL_{\Psi}+L_{\phi})^2. \tag*{(20)} c k = ( Ψ λ ( U k ) − Ψ λ ( U k + 1 ) ) + 2 λ γ k 2 ( β k L Ψ + L ϕ ) 2 . (20)
Proof. By definition of the Moreau envelope, the operator prox λ Ψ ( U k + 1 ) \operatorname{prox}_{\lambda\Psi}(\mathrm{U}^{k+1}) prox λ Ψ ( U k + 1 ) and the fact that prox λ Ψ ( U k ) ∈ S t ( K , R ) \operatorname{prox}_{\lambda\Psi}(\mathrm{U}^{k}) \in\mathrm{St}(K,\mathbb{R}) prox λ Ψ ( U k ) ∈ St ( K , R ) , we have
Ψ λ ( U k + 1 ) = Ψ ( prox λ Ψ ( U k + 1 ) ) + 1 2 λ ∥ prox λ Ψ ( U k + 1 ) − U k + 1 ∥ F 2 (21) \Psi_{\lambda}(\mathrm{U}^{k+1})=\Psi(\operatorname{prox}_{\lambda\Psi}(\mathrm{U}^{k+1}))+\frac{1}{2\lambda}\left\|\operatorname{prox}_{\lambda\Psi}(\mathrm{U}^{k+1})-\mathrm{U}^{k+1}\right\|_{\mathrm{F}}^2 \tag*{(21)} Ψ λ ( U k + 1 ) = Ψ ( prox λ Ψ ( U k + 1 )) + 2 λ 1 prox λ Ψ ( U k + 1 ) − U k + 1 F 2 (21)
≤ Ψ ( prox λ Ψ ( U k ) ) + 1 2 λ ∥ prox λ Ψ ( U k ) − U k + 1 ∥ F 2 . (22) \le\Psi(\operatorname{prox}_{\lambda\Psi}(\mathrm{U}^{k}))+\frac{1}{2\lambda}\left\|\operatorname{prox}_{\lambda\Psi}(\mathrm{U}^{k})-\mathrm{U}^{k+1}\right\|_{\mathrm{F}}^2. \tag*{(22)} ≤ Ψ ( prox λ Ψ ( U k )) + 2 λ 1 prox λ Ψ ( U k ) − U k + 1 F 2 . (22)
The non-expansiveness condition (A.1) gives
∥ prox λ Ψ ( U k ) − U k + 1 ∥ F 2 ≤ ∥ U k − γ k ( g k + β k ∇ S t Ψ ( U k ) ) − prox λ Ψ ( U k ) ∥ F 2 = ∥ U k − prox λ Ψ ( U k ) ∥ F 2 − 2 γ k ⟨ U k − prox λ Ψ ( U k ) , g k + β k ∇ S t Ψ ( U k ) ⟩ + γ k 2 ∥ g k + β k ∇ S t Ψ ( U k ) ∥ F 2 . \begin{aligned}
\left\|\operatorname{prox}_{\lambda\Psi}(\mathrm{U}^{k})-\mathrm{U}^{k+1}\right\|_{\mathrm{F}}^2
\le\left\|\mathrm{U}^{k}-\gamma_k\left(g^k+\beta_k\nabla_{\mathrm{St}}\Psi(\mathrm{U}^{k})\right)-\operatorname{prox}_{\lambda\Psi}(\mathrm{U}^{k})\right\|_{\mathrm{F}}^2 \\
&= \left\|\mathrm{U}^{k}-\operatorname{prox}_{\lambda\Psi}(\mathrm{U}^{k})\right\|_{\mathrm{F}}^2-2\gamma_k\left\langle\mathrm{U}^{k}-\operatorname{prox}_{\lambda\Psi}(\mathrm{U}^{k}),g^k+\beta_k\nabla_{\mathrm{St}}\Psi(\mathrm{U}^{k})\right\rangle+\gamma_k^2\left\|g^k+\beta_k\nabla_{\mathrm{St}}\Psi(\mathrm{U}^{k})\right\|_{\mathrm{F}}^2.
\end{aligned} prox λ Ψ ( U k ) − U k + 1 F 2 ≤ U k − γ k ( g k + β k ∇ St Ψ ( U k ) ) − prox λ Ψ ( U k ) F 2 = U k − prox λ Ψ ( U k ) F 2 − 2 γ k ⟨ U k − prox λ Ψ ( U k ) , g k + β k ∇ St Ψ ( U k ) ⟩ + γ k 2 g k + β k ∇ St Ψ ( U k ) F 2 .
To simplify the notation, let us set U ^ k ≡ prox λ Ψ ( U k ) \widehat{\mathrm{U}}^k \equiv\operatorname{prox}_{\lambda\Psi}(\mathrm{U}^{k}) U k ≡ prox λ Ψ ( U k ) . Since the mapping Ω k = ϕ + β k Ψ \Omega_k=\phi+\beta_k\Psi Ω k = ϕ + β k Ψ is β k L ∇ Ψ \beta_kL_{\nabla\Psi} β k L ∇Ψ -weakly convex on U \mathcal{U} U and L ϕ + β k L Ψ L_{\phi}+\beta_kL_{\Psi} L ϕ + β k L Ψ -Lipschitz continuous on St, it follows
⟨ g k + β k ∇ S t Ψ ( U k ) , U k − U ^ k ⟩ ≥ Ω k ( U k ) − Ω k ( U ^ k ) − β k ( L ∇ Ψ + L Ψ ) + L ϕ 2 ∥ U k − U ^ k ∥ F 2 . \left\langle g_k+\beta_k\nabla_{\mathrm{St}}\Psi(\mathrm{U}^{k}),\mathrm{U}^{k}-\widehat{\mathrm{U}}^k\right\rangle\ge\Omega_k(\mathrm{U}^{k})-\Omega_k(\widehat{\mathrm{U}}^k)-\frac{\beta_k(L_{\nabla\Psi}+L_{\Psi})+L_{\phi}}{2}\left\|\mathrm{U}^{k}-\widehat{\mathrm{U}}^k\right\|_{\mathrm{F}}^2. ⟨ g k + β k ∇ St Ψ ( U k ) , U k − U k ⟩ ≥ Ω k ( U k ) − Ω k ( U k ) − 2 β k ( L ∇Ψ + L Ψ ) + L ϕ U k − U k F 2 .
Moreover, the Lipschitz continuity of ϕ \phi ϕ and Ψ \Psi Ψ implies
∥ J k + β k ∇ S t Ψ ( U k ) ∥ F ≤ β k L Ψ + L ϕ , (23) \left\|J^k+\beta_k\nabla_{\mathrm{St}}\Psi(U^k)\right\|_F\le\beta_kL_\Psi+L_\phi, \tag*{(23)} J k + β k ∇ St Ψ ( U k ) F ≤ β k L Ψ + L ϕ , (23)
ϕ ( U k ) − ϕ ( U ^ k ) ≥ − L ϕ ∥ U k − U ^ k ∥ F . (24) \phi(U^k)-\phi(\widehat{U}^k)\ge-L_\phi\left\|U^k-\widehat{U}^k\right\|_F. \tag*{(24)} ϕ ( U k ) − ϕ ( U k ) ≥ − L ϕ U k − U k F . (24)
Using these bounds, we can continue the estimation with
∥ U ^ k − U k + 1 ∥ F 2 ≤ ∥ U k − U ^ k ∥ F 2 − 2 γ k ( Ω k ( U k ) − Ω k ( U ^ k ) ) + γ k ( β k ( L ∇ Ψ + L Ψ ) + L ϕ ) ∥ U k − U ^ k ∥ F 2 + γ k 2 ( β k L Ψ + L ϕ ) 2 ≤ ( 1 + γ k ( β k ( L ∇ Ψ + L Ψ ) + L ϕ ) ) ∥ U k − U ^ k ∥ F 2 + 2 γ k L ϕ ∥ U k − U ^ k ∥ F + 2 γ k β k ( Ψ ( U ^ k ) − Ψ ( U k ) ) + γ k 2 ( β k L Ψ + L ϕ ) 2 \begin{aligned}
\left\|\widehat{U}^k-U^{k+1}\right\|_F^2
&\le\left\|U^k-\widehat{U}^k\right\|_F^2-2\gamma_k\left(\Omega_k(U^k)-\Omega_k(\widehat{U}^k)\right)\\
&\quad+\gamma_k\left(\beta_k(L_{\nabla\Psi}+L_\Psi)+L_\phi\right)\left\|U^k-\widehat{U}^k\right\|_F^2+\gamma_k^2(\beta_kL_\Psi+L_\phi)^2\\
&\le\left(1+\gamma_k\left(\beta_k(L_{\nabla\Psi}+L_\Psi)+L_\phi\right)\right)\left\|U^k-\widehat{U}^k\right\|_F^2\\
&\quad+2\gamma_kL_\phi\left\|U^k-\widehat{U}^k\right\|_F\\
&\quad+2\gamma_k\beta_k\left(\Psi(\widehat{U}^k)-\Psi(U^k)\right)+\gamma_k^2(\beta_kL_\Psi+L_\phi)^2
\end{aligned} U k − U k + 1 F 2 ≤ U k − U k F 2 − 2 γ k ( Ω k ( U k ) − Ω k ( U k ) ) + γ k ( β k ( L ∇Ψ + L Ψ ) + L ϕ ) U k − U k F 2 + γ k 2 ( β k L Ψ + L ϕ ) 2 ≤ ( 1 + γ k ( β k ( L ∇Ψ + L Ψ ) + L ϕ ) ) U k − U k F 2 + 2 γ k L ϕ U k − U k F + 2 γ k β k ( Ψ ( U k ) − Ψ ( U k ) ) + γ k 2 ( β k L Ψ + L ϕ ) 2
Using the definition of the Moreau envelope once more, we see
Ψ λ ( U k ) = Ψ ( U ^ k ) + 1 2 λ ∥ U k − U ^ k ∥ F 2 , \Psi_\lambda(U^k)=\Psi(\widehat{U}^k)+\frac{1}{2\lambda}\left\|U^k-\widehat{U}^k\right\|_F^2, Ψ λ ( U k ) = Ψ ( U k ) + 2 λ 1 U k − U k F 2 ,
and since Ψ λ ( U k ) ≤ Ψ ( U k ) \Psi_\lambda(U^k)\le\Psi(U^k) Ψ λ ( U k ) ≤ Ψ ( U k ) , we infer
2 γ k β k ( Ψ ( U ^ k ) − Ψ ( U k ) ) ≤ − γ k β k λ ∥ U k − U ^ k ∥ F 2 . 2\gamma_k\beta_k\left(\Psi(\widehat{U}^k)-\Psi(U^k)\right)\le-\frac{\gamma_k\beta_k}{\lambda}\left\|U^k-\widehat{U}^k\right\|_F^2. 2 γ k β k ( Ψ ( U k ) − Ψ ( U k ) ) ≤ − λ γ k β k U k − U k F 2 .
Injecting this into the penultimate bound, we are left with
∥ U ^ k − U k + 1 ∥ F 2 ≤ ( 1 + γ k ( β k ( L ∇ Ψ + L Ψ ) + L ϕ ) − γ k β k λ ) ∥ U k − U ^ k ∥ F 2 + 2 γ k L ϕ ∥ U k − U ^ k ∥ F + γ k 2 ( β k L Ψ + L ϕ ) 2 \begin{aligned}
\left\|\widehat{U}^k-U^{k+1}\right\|_F^2
&\le\left(1+\gamma_k\left(\beta_k(L_{\nabla\Psi}+L_\Psi)+L_\phi\right)-\frac{\gamma_k\beta_k}{\lambda}\right)\left\|U^k-\widehat{U}^k\right\|_F^2\\
&\quad+2\gamma_kL_\phi\left\|U^k-\widehat{U}^k\right\|_F+\gamma_k^2(\beta_kL_\Psi+L_\phi)^2
\end{aligned} U k − U k + 1 F 2 ≤ ( 1 + γ k ( β k ( L ∇Ψ + L Ψ ) + L ϕ ) − λ γ k β k ) U k − U k F 2 + 2 γ k L ϕ U k − U k F + γ k 2 ( β k L Ψ + L ϕ ) 2
Combining all these estimates,
Ψ λ ( U k + 1 ) ≤ Ψ λ ( U k ) + γ k 2 λ [ L ϕ + β k ( L ∇ Ψ + L Ψ − 1 λ ) ] ∥ U k − U ^ k ∥ F 2 + γ k L ϕ λ ∥ U k − U ^ k ∥ F + γ k 2 2 λ ( β k L Ψ + L ϕ ) 2 = a k ∥ U k − U ^ k ∥ F 2 + b k ∥ U k − U ^ k ∥ F + c k + Ψ λ ( U k + 1 ) , \begin{aligned}
\Psi_\lambda(U^{k+1})
&\le\Psi_\lambda(U^k)+\frac{\gamma_k}{2\lambda}\left[L_\phi+\beta_k\left(L_{\nabla\Psi}+L_\Psi-\frac{1}{\lambda}\right)\right]\left\|U^k-\widehat{U}^k\right\|_F^2\\
&\quad+\frac{\gamma_kL_\phi}{\lambda}\left\|U^k-\widehat{U}^k\right\|_F+\frac{\gamma_k^2}{2\lambda}(\beta_kL_\Psi+L_\phi)^2\\
&=a_k\left\|U^k-\widehat{U}^k\right\|_F^2+b_k\left\|U^k-\widehat{U}^k\right\|_F+c_k+\Psi_\lambda(U^{k+1}),
\end{aligned} Ψ λ ( U k + 1 ) ≤ Ψ λ ( U k ) + 2 λ γ k [ L ϕ + β k ( L ∇Ψ + L Ψ − λ 1 ) ] U k − U k F 2 + λ γ k L ϕ U k − U k F + 2 λ γ k 2 ( β k L Ψ + L ϕ ) 2 = a k U k − U k F 2 + b k U k − U k F + c k + Ψ λ ( U k + 1 ) ,
where a k a_k a k , b k b_k b k and c k c_k c k are defined in equations (18) , (19) and (20) , respectively. By the assumption on λ \lambda λ , we have a k < 0 a_k<0 a k < 0 , which yields the desired result. The second estimate follows from the concavity of the square root function. ■
Theorem 4.3. Let { U k } \{U^k\} { U k } be the sequence generated by (13) with arbitrary initialization, step sizes ( γ k ) k (\gamma_k)_k ( γ k ) k and monotonically increasing penalty parameters ( β k ) k (\beta_k)_k ( β k ) k . Then, for every λ < ( L ∇ Ψ + L Ψ + L ϕ / β 0 ) − 1 \lambda<(L_{\nabla\Psi}+L_\Psi+L_\phi/\beta_0)^{-1} λ < ( L ∇Ψ + L Ψ + L ϕ / β 0 ) − 1 , the following estimate holds
min 0 ≤ k ≤ T Θ λ 2 Ψ ( U k ) ≤ 4 λ L λ Δ Ψ 0 + 2 L λ ( L Ψ + L ϕ / β 0 ) 2 ∑ k = 0 T ( γ k β k ) 2 + 4 L ϕ 2 ∑ k = 0 T γ k / β k λ 2 L λ 2 ∑ k = 0 T γ k β k . (25) \min_{0\le k\le T}\Theta_\lambda^2\Psi(U^k)\le\frac{4\lambda L_\lambda\Delta_\Psi^0+2L_\lambda(L_\Psi+L_\phi/\beta_0)^2\sum_{k=0}^{T}(\gamma_k\beta_k)^2+4L_\phi^2\sum_{k=0}^{T}\gamma_k/\beta_k}{\lambda^2L_\lambda^2\sum_{k=0}^{T}\gamma_k\beta_k}. \tag*{(25)} 0 ≤ k ≤ T min Θ λ 2 Ψ ( U k ) ≤ λ 2 L λ 2 ∑ k = 0 T γ k β k 4 λ L λ Δ Ψ 0 + 2 L λ ( L Ψ + L ϕ / β 0 ) 2 ∑ k = 0 T ( γ k β k ) 2 + 4 L ϕ 2 ∑ k = 0 T γ k / β k . (25)
where L λ : = 1 / λ − L ∇ Ψ − L Ψ − L ϕ / β 0 > 0 L_\lambda:= 1/\lambda- L_{\nabla\Psi} - L_\Psi- L_\phi/\beta_0 > 0 L λ := 1/ λ − L ∇Ψ − L Ψ − L ϕ / β 0 > 0 and Δ Ψ 0 : = Ψ ( U 0 ) − min S t Ψ \Delta_\Psi^0 := \Psi(U^0) - \min_{\mathrm{St}} \Psi Δ Ψ 0 := Ψ ( U 0 ) − min St Ψ . In particular, the right-hand side of (25) converges to zero as T → ∞ T \to\infty T → ∞ if and only if the following design criteria for the step-size and penalty sequences are satisfied:
∑ k = 0 T γ k β k → ∞ , ∑ k = 0 T ( γ k β k ) 2 ∑ k = 0 T γ k β k → 0 , ∑ k = 0 T γ k / β k ∑ k = 0 T γ k β k → 0. \sum_{k=0}^{T} \gamma_k\beta_k \to\infty,\qquad
\frac{\sum_{k=0}^{T}(\gamma_k\beta_k)^2}{\sum_{k=0}^{T}\gamma_k\beta_k} \to0,\qquad
\frac{\sum_{k=0}^{T}\gamma_k/\beta_k}{\sum_{k=0}^{T}\gamma_k\beta_k} \to0. k = 0 ∑ T γ k β k → ∞ , ∑ k = 0 T γ k β k ∑ k = 0 T ( γ k β k ) 2 → 0 , ∑ k = 0 T γ k β k ∑ k = 0 T γ k / β k → 0.
Proof. First, we observe the inequalities
∑ k = 0 T c k = Ψ λ ( U 0 ) − Ψ λ ( U T + 1 ) + 1 2 λ ∑ k = 0 T γ k 2 ( β k L Ψ + L ϕ ) 2 ≤ Ψ λ ( U 0 ) − min S t Ψ λ + 1 2 λ ( L Ψ + L ϕ / β 0 ) 2 ∑ k = 0 T ( γ k β k ) 2 , (26) \begin{aligned}
\sum_{k=0}^{T} c_k = \Psi_\lambda(U^0)-\Psi_\lambda(U^{T+1})+\frac{1}{2\lambda}\sum_{k=0}^{T}\gamma_k^2(\beta_kL_\Psi+L_\phi)^2 \\
&\leq\Psi_\lambda(U^0)-\min_{\mathrm{St}}\Psi_\lambda+\frac{1}{2\lambda}(L_\Psi+L_\phi/\beta_0)^2\sum_{k=0}^{T}(\gamma_k\beta_k)^2, \tag*{(26)}
\end{aligned} k = 0 ∑ T c k = Ψ λ ( U 0 ) − Ψ λ ( U T + 1 ) + 2 λ 1 k = 0 ∑ T γ k 2 ( β k L Ψ + L ϕ ) 2 ≤ Ψ λ ( U 0 ) − St min Ψ λ + 2 λ 1 ( L Ψ + L ϕ / β 0 ) 2 k = 0 ∑ T ( γ k β k ) 2 , (26)
∑ k = 0 T b k 2 ∣ a k ∣ = 2 L ϕ 2 λ ∑ k = 0 T γ k ( β k ( 1 λ − L ∇ Ψ − L Ψ ) − L ϕ ) − 1 ≤ 2 L ϕ 2 λ L λ − 1 ∑ k = 0 T γ k / β k , (27) \sum_{k=0}^{T}\frac{b_k^2}{|a_k|}
=\frac{2L_\phi^2}{\lambda}\sum_{k=0}^{T}\gamma_k\left(\beta_k\left(\frac{1}{\lambda}-L_{\nabla\Psi}-L_\Psi\right)-L_\phi\right)^{-1}
\leq\frac{2L_\phi^2}{\lambda}L_\lambda^{-1}\sum_{k=0}^{T}\gamma_k/\beta_k, \tag*{(27)} k = 0 ∑ T ∣ a k ∣ b k 2 = λ 2 L ϕ 2 k = 0 ∑ T γ k ( β k ( λ 1 − L ∇Ψ − L Ψ ) − L ϕ ) − 1 ≤ λ 2 L ϕ 2 L λ − 1 k = 0 ∑ T γ k / β k , (27)
∑ k = 0 T ∣ a k ∣ = 1 2 λ ∑ k = 0 T γ k ( β k ( 1 λ − L ∇ Ψ − L Ψ ) − L ϕ ) ≥ 1 2 λ L λ ∑ k = 0 T γ k β k . (28) \sum_{k=0}^{T}|a_k|
=\frac{1}{2\lambda}\sum_{k=0}^{T}\gamma_k\left(\beta_k\left(\frac{1}{\lambda}-L_{\nabla\Psi}-L_\Psi\right)-L_\phi\right)
\geq\frac{1}{2\lambda}L_\lambda\sum_{k=0}^{T}\gamma_k\beta_k. \tag*{(28)} k = 0 ∑ T ∣ a k ∣ = 2 λ 1 k = 0 ∑ T γ k ( β k ( λ 1 − L ∇Ψ − L Ψ ) − L ϕ ) ≥ 2 λ 1 L λ k = 0 ∑ T γ k β k . (28)
With these and Proposition 4.2 we arrive at
( ∑ k = 0 T ∣ a k ∣ ) min 0 ≤ k ≤ T Θ λ Ψ ( U k ) ≤ ∑ k = 0 T ∣ a k ∣ Θ λ Ψ ( U k ) ≤ 1 λ 2 ( ∑ k = 0 T b k 2 ∣ a k ∣ + 2 ∑ k = 0 T c k ) ≤ 2 λ 2 ( Ψ λ ( U 0 ) − min S t Ψ λ ) + 1 λ 3 ( L Ψ + L ϕ / β 0 ) 2 ∑ k = 0 T ( γ k β k ) 2 + 2 L ϕ 2 λ 3 L λ − 1 ∑ k = 0 T γ k / β k . \begin{aligned}
\left(\sum_{k=0}^{T}|a_k|\right)\min_{0\leq k\leq T}\Theta_{\lambda\Psi}(U^k)
\leq\sum_{k=0}^{T}|a_k|\Theta_{\lambda\Psi}(U^k)
\leq\frac{1}{\lambda^2}\left(\sum_{k=0}^{T}\frac{b_k^2}{|a_k|}+2\sum_{k=0}^{T}c_k\right) \\
&\leq\frac{2}{\lambda^2}\left(\Psi_\lambda(U^0)-\min_{\mathrm{St}}\Psi_\lambda\right)
+\frac{1}{\lambda^3}(L_\Psi+L_\phi/\beta_0)^2\sum_{k=0}^{T}(\gamma_k\beta_k)^2
+\frac{2L_\phi^2}{\lambda^3}L_\lambda^{-1}\sum_{k=0}^{T}\gamma_k/\beta_k.
\end{aligned} ( k = 0 ∑ T ∣ a k ∣ ) 0 ≤ k ≤ T min Θ λ Ψ ( U k ) ≤ k = 0 ∑ T ∣ a k ∣ Θ λ Ψ ( U k ) ≤ λ 2 1 ( k = 0 ∑ T ∣ a k ∣ b k 2 + 2 k = 0 ∑ T c k ) ≤ λ 2 2 ( Ψ λ ( U 0 ) − St min Ψ λ ) + λ 3 1 ( L Ψ + L ϕ / β 0 ) 2 k = 0 ∑ T ( γ k β k ) 2 + λ 3 2 L ϕ 2 L λ − 1 k = 0 ∑ T γ k / β k .
Moreover, note that Ψ λ ( U 0 ) ≤ Ψ ( U 0 ) \Psi_\lambda(U^0)\leq\Psi(U^0) Ψ λ ( U 0 ) ≤ Ψ ( U 0 ) , and Ψ λ ( U ) ≥ min V Ψ ( V ) = min S t Ψ \Psi_\lambda(U)\geq\min_V\Psi(V)=\min_{\mathrm{St}}\Psi Ψ λ ( U ) ≥ min V Ψ ( V ) = min St Ψ . Hence,
Ψ λ ( U 0 ) − min S t Ψ λ ≤ Ψ ( U 0 ) − min S t Ψ . \Psi_\lambda(U^0)-\min_{\mathrm{St}}\Psi_\lambda\leq\Psi(U^0)-\min_{\mathrm{St}}\Psi. Ψ λ ( U 0 ) − St min Ψ λ ≤ Ψ ( U 0 ) − St min Ψ.
Putting ∑ k = 0 T ∣ a k ∣ \sum_{k=0}^{T}|a_k| ∑ k = 0 T ∣ a k ∣ on the other side and multiplying the numerator and denominator of the fraction by λ L λ \lambda L_\lambda λ L λ yields the result. ■
Theorem 4.3 provides a general upper bound on the stationarity measure that accounts for the feasibility violation. It also specifies conditions on the step sizes and penalty parameters that guarantee convergence to a stationary point of the lower-level problem. The bound depends on the auxiliary parameter λ > 0 \lambda>0 λ > 0 , which must be chosen sufficiently small and is then kept fixed. As λ → 0 \lambda\to0 λ → 0 , we have λ L λ → 1 \lambda L_\lambda\to1 λ L λ → 1 , while L λ L_\lambda L λ , which appears as the coefficient of the quadratic term, becomes arbitrarily large. Conversely, as λ \lambda λ approaches its upper admissible bound, the constant in the denominator becomes arbitrarily small, causing the overall bound to deteriorate.
In the following two corollaries, we specify the step sizes and penalty parameters and show that, under the differentiability of Ψ \Psi Ψ , the convergence rate of the stationarity measure can be transferred to the lower-level stationarity measure. In particular, we obtain an explicit convergence rate for ∥ ∇ S t Ψ ( U k ) ∥ \lVert\nabla_{\mathrm{St}}\Psi(U^k)\rVert ∥ ∇ St Ψ ( U k )∥ , rather than only for the Moreau-envelope-based stationarity measure Θ λ Ψ ( U k ) \Theta_{\lambda\Psi}(U^k) Θ λ Ψ ( U k ) . The first choice of step sizes and penalty parameters yields a convergence rate for the lower-level stationarity and guarantees the existence of a subsequence converging to a stationary point. The second corollary employs slightly more restrictive step sizes, resulting in a marginally worse convergence rate, but guarantees that every limit point of a convergent subsequence is a stationary point of the lower-level problem.
Corollary 4.4. Let { U k } \{U^k\} { U k } be the sequence generated by (13) with arbitrary initialization. Let β k → ∞ \beta_k \to\infty β k → ∞ be increasing monotonically such that ∑ k = 0 T 1 / ( β k 2 k + 1 ) ∈ o ( T ) \sum_{k=0}^{T} 1/(\beta_k^2\sqrt{k+1}) \in o(\sqrt{T}) ∑ k = 0 T 1/ ( β k 2 k + 1 ) ∈ o ( T ) and set γ k = γ ~ / ( β k k + 1 ) \gamma_k = \widetilde{\gamma}/(\beta_k\sqrt{k+1}) γ k = γ / ( β k k + 1 ) for some γ ~ > 0 \widetilde{\gamma} > 0 γ > 0 . Then, for every λ < ( L ∇ Ψ + L Ψ + L ϕ / β 0 ) − 1 \lambda< (L_{\nabla\Psi}+L_{\Psi}+L_{\phi}/\beta_0)^{-1} λ < ( L ∇Ψ + L Ψ + L ϕ / β 0 ) − 1 , we have the rate
min 0 ≤ k ≤ T ∥ ∇ S t Ψ ( U k ) ∥ ∈ O ( log T T 1 / 4 ) (29) \min_{0\leq k\leq T}\lVert\nabla_{\mathrm{St}}\Psi(U^k)\rVert\in O\left(\frac{\sqrt{\log T}}{T^{1/4}}\right) \tag*{(29)} 0 ≤ k ≤ T min ∥ ∇ St Ψ ( U k )∥ ∈ O ( T 1/4 log T ) (29) and the sequence { U k } \{U^k\} { U k } admits a convergent subsequence U τ ( k ) → U ∗ U^{\tau(k)} \to U^* U τ ( k ) → U ∗ with ∇ S t Ψ ( U ∗ ) = 0 \nabla_{\mathrm{St}}\Psi(U^*) = 0 ∇ St Ψ ( U ∗ ) = 0 .
Proof. It follows from (16) that ∥ ∇ S t Ψ ( U k ) ∥ ≤ ( L ∇ S t Ψ λ + 1 ) ∥ ∇ S t Ψ ( prox λ Ψ ( U k ) ) ∥ \lVert\nabla_{\mathrm{St}}\Psi(U^k)\rVert\leq(L_{\nabla_{\mathrm{St}}\Psi}\lambda+ 1)\lVert\nabla_{\mathrm{St}}\Psi(\operatorname{prox}_{\lambda\Psi}(U^k))\rVert ∥ ∇ St Ψ ( U k )∥ ≤ ( L ∇ St Ψ λ + 1 ) ∥ ∇ St Ψ ( prox λ Ψ ( U k ))∥ . Inserting γ k \gamma_k γ k and β k \beta_k β k in Theorem 4.3 and noting that ∑ k = 0 T 1 k + 1 > T + 1 \sum_{k=0}^{T}\frac{1}{\sqrt{k+1}}>\sqrt{T+1} ∑ k = 0 T k + 1 1 > T + 1 and ∑ k = 0 T 1 k + 1 < log ( T + 1 ) + 1 \sum_{k=0}^{T}\frac{1}{k+1}<\log(T+1)+1 ∑ k = 0 T k + 1 1 < log ( T + 1 ) + 1 gives the rate. Moreover, Theorem 4.3 implies that there is a subsequence { U k n } \{U^{k_n}\} { U k n } such that ∥ ∇ S t Ψ ( prox λ Ψ ( U k n ) ) ∥ F ≤ Θ ( U k n ) → 0 \lVert\nabla_{\mathrm{St}}\Psi(\operatorname{prox}_{\lambda\Psi}(U^{k_n}))\rVert_F\leq\Theta(U^{k_n})\to0 ∥ ∇ St Ψ ( prox λ Ψ ( U k n )) ∥ F ≤ Θ ( U k n ) → 0 . Since the Stiefel manifold is compact, we can pass to another convergent subsequence U k n i → U ∗ ∈ St ( K , R ) U^{k_{n_i}}\to U^*\in\operatorname{St}(K,\mathbb{R}) U k n i → U ∗ ∈ St ( K , R ) . Then it follows that prox λ Ψ ( U k n i ) → U ∗ \operatorname{prox}_{\lambda\Psi}(U^{k_{n_i}})\to U^* prox λ Ψ ( U k n i ) → U ∗ and the continuity of the gradient implies
∥ ∇ S t Ψ ( prox λ Ψ ( U k n i ) ) ∥ F → ∥ ∇ S t Ψ ( U ∗ ) ∥ F = 0. \lVert\nabla_{\mathrm{St}}\Psi(\operatorname{prox}_{\lambda\Psi}(U^{k_{n_i}}))\rVert_F\to\lVert\nabla_{\mathrm{St}}\Psi(U^*)\rVert_F=0. ∥ ∇ St Ψ ( prox λ Ψ ( U k n i )) ∥ F → ∥ ∇ St Ψ ( U ∗ ) ∥ F = 0.
Corollary 4.5. Let { U k } \{U^k\} { U k } be the sequence generated by (13) with arbitrary initialization. Let β k → ∞ \beta_k\to\infty β k → ∞ be monotonically increasing with β k ∈ O ( k 1 / 4 ) \beta_k\in O(k^{1/4}) β k ∈ O ( k 1/4 ) and set γ k = γ ~ / ( β k ( k + 1 ) 1 / 2 + ε ) \gamma_k=\widetilde{\gamma}/(\beta_k(k+1)^{1/2+\varepsilon}) γ k = γ / ( β k ( k + 1 ) 1/2 + ε ) for some fixed ε , γ ~ > 0 \varepsilon,\widetilde{\gamma}>0 ε , γ > 0 . Then, for every λ < ( L ∇ Ψ + L Ψ + L ϕ / β 0 ) − 1 \lambda<(L_{\nabla\Psi}+L_{\Psi}+L_{\phi}/\beta_0)^{-1} λ < ( L ∇Ψ + L Ψ + L ϕ / β 0 ) − 1 , we have the rate
min 0 ≤ k ≤ T ∥ ∇ S t Ψ ( U k ) ∥ 2 ≤ 1 T + 1 ∑ k = 0 T ∥ ∇ S t Ψ ( prox λ Ψ ( U k ) ) ∥ 2 ∈ O ( T − 1 / 2 + ε ) . (30) \min_{0\leq k\leq T}\lVert\nabla_{\mathrm{St}}\Psi(U^k)\rVert^2\leq\frac{1}{T+1}\sum_{k=0}^{T}\lVert\nabla_{\mathrm{St}}\Psi(\operatorname{prox}_{\lambda\Psi}(U^k))\rVert^2\in O(T^{-1/2+\varepsilon}). \tag*{(30)} 0 ≤ k ≤ T min ∥ ∇ St Ψ ( U k ) ∥ 2 ≤ T + 1 1 k = 0 ∑ T ∥ ∇ St Ψ ( prox λ Ψ ( U k )) ∥ 2 ∈ O ( T − 1/2 + ε ) . (30) Especially, the limit point U ∗ U^* U ∗ of any convergent subsequence U τ ( k ) U^{\tau(k)} U τ ( k ) satisfies ∇ S t Ψ ( U ∗ ) = 0 \nabla_{\mathrm{St}}\Psi(U^*)=0 ∇ St Ψ ( U ∗ ) = 0 .
Proof. It follows from (16) that ∥ ∇ S t Ψ ( U k ) ∥ ≤ ( L ∇ S t Ψ λ + 1 ) ∥ ∇ S t Ψ ( prox λ Ψ ( U k ) ) ∥ \lVert\nabla_{\mathrm{St}}\Psi(U^k)\rVert\leq(L_{\nabla_{\mathrm{St}}\Psi}\lambda+1)\lVert\nabla_{\mathrm{St}}\Psi(\operatorname{prox}_{\lambda\Psi}(U^k))\rVert ∥ ∇ St Ψ ( U k )∥ ≤ ( L ∇ St Ψ λ + 1 ) ∥ ∇ St Ψ ( prox λ Ψ ( U k ))∥ . By Proposition 4.2 we have
1 T + 1 ∑ k = 0 T Θ λ Ψ 2 ( U k ) ≤ 1 λ 2 ( T + 1 ) ∑ k = 0 T 1 ∣ a k ∣ ( b k 2 ∣ a k ∣ + 2 c k ) ≤ 1 λ 2 ( T + 1 ) max 0 ≤ k ≤ T ( 1 ∣ a k ∣ ) ∑ k = 0 T ( b k 2 ∣ a k ∣ + 2 c k ) . \frac{1}{T+1}\sum_{k=0}^{T}\Theta_{\lambda\Psi}^2(U^k)\leq\frac{1}{\lambda^2(T+1)}\sum_{k=0}^{T}\frac{1}{|a_k|}\left(\frac{b_k^2}{|a_k|}+2c_k\right)\leq\frac{1}{\lambda^2(T+1)}\max_{0\leq k\leq T}\left(\frac{1}{|a_k|}\right)\sum_{k=0}^{T}\left(\frac{b_k^2}{|a_k|}+2c_k\right). T + 1 1 k = 0 ∑ T Θ λ Ψ 2 ( U k ) ≤ λ 2 ( T + 1 ) 1 k = 0 ∑ T ∣ a k ∣ 1 ( ∣ a k ∣ b k 2 + 2 c k ) ≤ λ 2 ( T + 1 ) 1 0 ≤ k ≤ T max ( ∣ a k ∣ 1 ) k = 0 ∑ T ( ∣ a k ∣ b k 2 + 2 c k ) .
Further, max 0 ≤ k ≤ T 1 ∣ a k ∣ ∈ O ( 1 / ( γ T β T ) ) = O ( T 1 / 2 + ε ) \max_{0\leq k\leq T}\frac{1}{|a_k|}\in O(1/(\gamma_T\beta_T))=O(T^{1/2+\varepsilon}) max 0 ≤ k ≤ T ∣ a k ∣ 1 ∈ O ( 1/ ( γ T β T )) = O ( T 1/2 + ε ) , and by (27) and (26)
∑ k = 0 T b k 2 ∣ a k ∣ + 2 c k ≤ 2 L ϕ 2 λ L λ − 1 ∑ k = 0 T γ ~ ( k + 1 ) 1 + ε + 2 Δ Ψ 0 + 1 2 λ ( L Ψ + L ϕ / β 0 ) 2 ∑ k = 0 T ( γ k β k ) 2 ≤ 2 L ϕ 2 λ L λ − 1 ∑ k = 0 T γ ~ ( k + 1 ) 1 + ε + 2 Δ Ψ 0 + 1 2 λ ( L Ψ + L ϕ / β 0 ) 2 ∑ k = 0 T γ ~ 2 ( k + 1 ) 1 + 2 ε \begin{aligned}
\sum_{k=0}^{T}\frac{b_k^2}{|a_k|}+2c_k\leq\frac{2L_\phi^2}{\lambda}L_\lambda^{-1}\sum_{k=0}^{T}\frac{\widetilde{\gamma}}{(k+1)^{1+\varepsilon}}+2\Delta_\Psi^0+\frac{1}{2\lambda}(L_\Psi+L_\phi/\beta_0)^2\sum_{k=0}^{T}\left(\gamma_k\beta_k\right)^2 \\
&\leq\frac{2L_\phi^2}{\lambda}L_\lambda^{-1}\sum_{k=0}^{T}\frac{\widetilde{\gamma}}{(k+1)^{1+\varepsilon}}+2\Delta_\Psi^0+\frac{1}{2\lambda}(L_\Psi+L_\phi/\beta_0)^2\sum_{k=0}^{T}\frac{\widetilde{\gamma}^2}{(k+1)^{1+2\varepsilon}}
\end{aligned} k = 0 ∑ T ∣ a k ∣ b k 2 + 2 c k ≤ λ 2 L ϕ 2 L λ − 1 k = 0 ∑ T ( k + 1 ) 1 + ε γ + 2 Δ Ψ 0 + 2 λ 1 ( L Ψ + L ϕ / β 0 ) 2 k = 0 ∑ T ( γ k β k ) 2 ≤ λ 2 L ϕ 2 L λ − 1 k = 0 ∑ T ( k + 1 ) 1 + ε γ + 2 Δ Ψ 0 + 2 λ 1 ( L Ψ + L ϕ / β 0 ) 2 k = 0 ∑ T ( k + 1 ) 1 + 2 ε γ 2
Since the average converges to zero, the entire sequence satisfies ∥ ∇ S t Ψ ( prox λ Ψ ( U k ) ) ∥ F → 0 \lVert\nabla_{\mathrm{St}}\Psi(\operatorname{prox}_{\lambda\Psi}(U^k))\rVert_F \to0 ∥ ∇ St Ψ ( prox λ Ψ ( U k )) ∥ F → 0 . The remainder of the proof follows in the same manner as in Corollary 4.4 . ■
The corollaries specify the step sizes up to a multiplicative constant, while the penalty parameters still allow some flexibility. We briefly provide examples of penalty parameter sequences that satisfy the assumptions of the analysis.
Polynomial growth: Let
β k = C ( k + 1 ) p , C > 0 , p > 0. \beta_k = C(k+1)^p,\qquad C>0,p>0. β k = C ( k + 1 ) p , C > 0 , p > 0.
Then
∑ k = 0 T 1 β k 2 k + 1 = ∑ k = 0 T 1 ( k + 1 ) 1 / 2 + 2 p ≤ { T 1 / 2 − 2 p − 1 1 / 2 − 2 p ∈ o ( T ) p < 1 4 , log ( T ) ∈ o ( T ) p = 1 4 , O ( 1 ) ⊂ o ( T ) p > 1 4 . \sum_{k=0}^{T}\frac{1}{\beta_k^2\sqrt{k+1}}
=\sum_{k=0}^{T}\frac{1}{(k+1)^{1/2+2p}}
\le
\begin{cases}
\frac{T^{1/2-2p}-1}{1/2-2p}\in o(\sqrt{T}) & p<\frac{1}{4},\\
\log(T)\in o(\sqrt{T}) & p=\frac{1}{4},\\
\mathcal{O}(1)\subset o(\sqrt{T}) & p>\frac{1}{4}.
\end{cases} k = 0 ∑ T β k 2 k + 1 1 = k = 0 ∑ T ( k + 1 ) 1/2 + 2 p 1 ≤ ⎩ ⎨ ⎧ 1/2 − 2 p T 1/2 − 2 p − 1 ∈ o ( T ) log ( T ) ∈ o ( T ) O ( 1 ) ⊂ o ( T ) p < 4 1 , p = 4 1 , p > 4 1 .
Hence, the assumptions of the first corollary are satisfied for all p > 0 p>0 p > 0 , whereas the second corollary requires p ≤ 1 / 4 p\le1/4 p ≤ 1/4 .
Logarithmic growth: Let
β k ≥ C log ( k + 2 ) , C > 0. \beta_k\ge C\sqrt{\log(k+2)},\qquad C>0. β k ≥ C log ( k + 2 ) , C > 0.
Then
1 T ∑ k = 0 T 1 k + 1 β k 2 ∈ o ( log log T T ) → 0. \frac{1}{\sqrt{T}}\sum_{k=0}^{T}\frac{1}{\sqrt{k+1}\beta_k^2}
\in o\left(\frac{\log\log T}{\sqrt{T}}\right)\to0. T 1 k = 0 ∑ T k + 1 β k 2 1 ∈ o ( T log log T ) → 0.
To satisfy the assumptions of the second corollary, we may choose β k = C log ( k + 2 ) \beta_k=C\sqrt{\log(k+2)} β k = C log ( k + 2 ) since log ( k + 2 ) ∈ O ( k 1 / 4 ) \sqrt{\log(k+2)}\in\mathcal{O}(k^{1/4}) log ( k + 2 ) ∈ O ( k 1/4 ) .
Next, we analyze upper-level stationarity. While for the lower level we track the evolution of the auxiliary sequence { prox λ Ψ ( U k ) } k \{\operatorname{prox}_{\lambda\Psi}(U^k)\}_k { prox λ Ψ ( U k ) } k , for the upper level we instead consider the sequence U ^ k : = prox λ Ω k / β k ( U k ) \widehat{U}^k:=\operatorname{prox}_{\lambda\Omega_k/\beta_k}(U^k) U k := prox λ Ω k / β k ( U k ) and derive a general upper bound for the time-dependent stationarity measure β k Θ λ Ω k / β k \beta_k\Theta_{\lambda\Omega_k/\beta_k} β k Θ λ Ω k / β k . This measure provides a bound on the distance to the subdifferential ∂ S t Ω k ( U ^ k ) \partial_{\mathrm{St}}\Omega_k(\widehat{U}^k) ∂ St Ω k ( U k ) to zero. The resulting bound directly yields conditions on the penalty parameters under which a subsequence of these subgradients converges to zero. In contrast to the lower-level case, however, this does not imply that the subgradients of Ω k \Omega_k Ω k evaluated along the algorithm-generated sequence { U k } \{U^k\} { U k } converge to zero. This is due to the lack of differentiability of the upper-level objective and the scaling induced by the increasing penalty parameter. Therefore, we do not aim to establish convergence of these subgradients to zero. Instead, combined with additional regularity assumptions on Ψ \Psi Ψ and suitable regularity conditions at the limit points of the algorithm, we can show that a limit point U ∗ U^* U ∗ not only belongs to the lower-level stationary set
N Ψ : = { U ∣ ∇ S t Ψ ( U ) = 0 } , \mathcal{N}_{\Psi}:=\{U\mid\nabla_{\mathrm{St}}\Psi(U)=0\}, N Ψ := { U ∣ ∇ St Ψ ( U ) = 0 } ,
but is, in fact, a stationary point of the upper-level problem ϕ \phi ϕ when restricted to N Ψ \mathcal{N}_{\Psi} N Ψ . Before proving the bounds for the stationarity measure, we establish several technical inequalities. The following lemma shows that the auxiliary parameter λ \lambda λ must be chosen sufficiently small to exploit the additional convexity of the Moreau envelope. Moreover, the proof builds on arguments from simple bilevel optimization in Euclidean spaces; however, some of these arguments fail here due to the lack of convexity of ϕ \phi ϕ when restricted to the Stiefel manifold. We overcome this issue by introducing an additional auxiliary sequence along the Euclidean line segments connecting the two sequences on the manifold.
Lemma 4.6. Let { U k } \{\mathrm{U}^{k}\} { U k } be the sequence generated by (13) with arbitrary initialization, step sizes ( γ k ) k (\gamma_k)_k ( γ k ) k and monotonically increasing penalty parameters ( β k ) k (\beta_k)_k ( β k ) k . Define ρ : = L ∇ Ψ + 4 L Ψ + 4 L ϕ / β 0 \rho:= L_{\nabla\Psi}+4L_{\Psi}+4L_{\phi}/\beta_0 ρ := L ∇Ψ + 4 L Ψ + 4 L ϕ / β 0 and choose λ < 1 / ρ \lambda<1/\rho λ < 1/ ρ . Moreover, define U ^ k : = prox ( λ / β k ) Ω k ( U k ) \widehat{\mathrm{U}}^{k}:=\operatorname{prox}_{(\lambda/\beta_k)\Omega_k}(\mathrm{U}^{k}) U k := prox ( λ / β k ) Ω k ( U k ) . For arbitrary g k ∈ ∂ S t ϕ ( U k ) \boldsymbol{g}^{k}\in\partial_{\mathrm{St}}\phi(\mathrm{U}^{k}) g k ∈ ∂ St ϕ ( U k ) and V ∈ S t \mathrm{V}\in\mathrm{St} V ∈ St , the following inequalities hold:
( 1 λ − ρ ) ∥ U k − U ^ k ∥ F 2 ≤ 8 ⟨ 1 β k g k + ∇ S t Ψ ( U k ) , U k − U ^ k ⟩ (31) \left(\frac{1}{\lambda}-\rho\right)\left\|\mathrm{U}^{k}-\widehat{\mathrm{U}}^{k}\right\|_{F}^{2}
\leq8\left\langle\frac{1}{\beta_k}\boldsymbol{g}^{k}+\nabla_{\mathrm{St}}\Psi(\mathrm{U}^{k}),\mathrm{U}^{k}-\widehat{\mathrm{U}}^{k}\right\rangle \tag*{(31)} ( λ 1 − ρ ) U k − U k F 2 ≤ 8 ⟨ β k 1 g k + ∇ St Ψ ( U k ) , U k − U k ⟩ (31) γ k β k ⟨ 1 β k g k + ∇ S t Ψ ( U k ) , U k − V ⟩ ≤ 1 2 ∥ U k − V ∥ F 2 − 1 2 ∥ U k + 1 − V ∥ F 2 + 1 2 ( γ k β k ) 2 ( 1 β 0 L ϕ + L Ψ ) 2 (32) \gamma_k\beta_k\left\langle\frac{1}{\beta_k}\boldsymbol{g}^{k}+\nabla_{\mathrm{St}}\Psi(\mathrm{U}^{k}),\mathrm{U}^{k}-\mathrm{V}\right\rangle
\leq\frac{1}{2}\left\|\mathrm{U}^{k}-\mathrm{V}\right\|_{F}^{2}
-\frac{1}{2}\left\|\mathrm{U}^{k+1}-\mathrm{V}\right\|_{F}^{2}
+\frac{1}{2}(\gamma_k\beta_k)^{2}\left(\frac{1}{\beta_0}L_{\phi}+L_{\Psi}\right)^{2} \tag*{(32)} γ k β k ⟨ β k 1 g k + ∇ St Ψ ( U k ) , U k − V ⟩ ≤ 2 1 U k − V F 2 − 2 1 U k + 1 − V F 2 + 2 1 ( γ k β k ) 2 ( β 0 1 L ϕ + L Ψ ) 2 (32) 1 2 ∥ U k − U ^ k ∥ F 2 − 1 2 ∥ U k + 1 − U ^ k ∥ F 2 ≤ λ [ ( β k − 1 Ω k ) λ ( U k ) − ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) − ( β k − 1 − β k + 1 − 1 ) min U ∈ S t ϕ ( U ) ] (33) \frac{1}{2}\left\|\mathrm{U}^{k}-\widehat{\mathrm{U}}^{k}\right\|_{F}^{2}
-\frac{1}{2}\left\|\mathrm{U}^{k+1}-\widehat{\mathrm{U}}^{k}\right\|_{F}^{2}
\leq\lambda\left[(\beta_k^{-1}\Omega_k)_{\lambda}(\mathrm{U}^{k})-(\beta_{k+1}^{-1}\Omega_{k+1})_{\lambda}(\mathrm{U}^{k+1})-(\beta_k^{-1}-\beta_{k+1}^{-1})\min_{\mathrm{U}\in\mathrm{St}}\phi(\mathrm{U})\right] \tag*{(33)} 2 1 U k − U k F 2 − 2 1 U k + 1 − U k F 2 ≤ λ [ ( β k − 1 Ω k ) λ ( U k ) − ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) − ( β k − 1 − β k + 1 − 1 ) U ∈ St min ϕ ( U ) ] (33)
Proof. For (31) note that 1 β k Ω k \frac{1}{\beta_k}\Omega_k β k 1 Ω k is L ∇ Ψ L_{\nabla\Psi} L ∇Ψ -weakly convex on U \mathcal{U} U , therefore f k ( U ) : = 1 β k Ω k ( U ) + 1 2 λ ∥ U − U k ∥ F 2 f_k(\mathrm{U}):=\frac{1}{\beta_k}\Omega_k(\mathrm{U})+\frac{1}{2\lambda}\left\|\mathrm{U}-\mathrm{U}^{k}\right\|_{F}^{2} f k ( U ) := β k 1 Ω k ( U ) + 2 λ 1 U − U k F 2 is ( 1 / λ − L ∇ Ψ ) (1/\lambda-L_{\nabla\Psi}) ( 1/ λ − L ∇Ψ ) -strongly convex on U \mathcal{U} U . Define U ˙ k : = argmin U ∈ [ U k , U ^ k ] f k ( U ) \dot{\mathrm{U}}^{k}:=\operatorname*{argmin}_{\mathrm{U}\in[\mathrm{U}^{k},\widehat{\mathrm{U}}^{k}]}f_k(\mathrm{U}) U ˙ k := argmin U ∈ [ U k , U k ] f k ( U ) where [ U k , U ^ k ] ⊂ U [\mathrm{U}^{k},\widehat{\mathrm{U}}^{k}]\subset\mathcal{U} [ U k , U k ] ⊂ U denotes the line segment between U k \mathrm{U}^{k} U k and U ^ k \widehat{\mathrm{U}}^{k} U k in the ambient Euclidean space. By the strong convexity of f k f_k f k and the fact that [ U k , U ^ k ] [\mathrm{U}^{k},\widehat{\mathrm{U}}^{k}] [ U k , U k ] is convex, U ˙ k \dot{\mathrm{U}}^{k} U ˙ k is unique and for all U ∈ [ U k , U ^ k ] \mathrm{U}\in[\mathrm{U}^{k},\widehat{\mathrm{U}}^{k}] U ∈ [ U k , U k ] holds
f k ( U ) − f k ( U ˙ k ) ≥ 1 2 ( 1 λ − L ∇ Ψ ) ∥ U − U ˙ k ∥ F 2 . f_k(\mathrm{U})-f_k(\dot{\mathrm{U}}^{k})
\geq\frac{1}{2}\left(\frac{1}{\lambda}-L_{\nabla\Psi}\right)\left\|\mathrm{U}-\dot{\mathrm{U}}^{k}\right\|_{F}^{2}. f k ( U ) − f k ( U ˙ k ) ≥ 2 1 ( λ 1 − L ∇Ψ ) U − U ˙ k F 2 .
Then, we have
1 2 ( 1 λ − L ∇ Ψ ) ∥ U k − U ^ k ∥ F 2 ≤ 1 2 ( 1 λ − L ∇ Ψ ) ( 2 ∥ U k − U ˙ k ∥ F 2 + 2 ∥ U ˙ k − U ^ k ∥ F 2 ) \frac{1}{2}\left(\frac{1}{\lambda}-L_{\nabla\Psi}\right)\left\|\mathrm{U}^{k}-\widehat{\mathrm{U}}^{k}\right\|_{F}^{2}
\leq\frac{1}{2}\left(\frac{1}{\lambda}-L_{\nabla\Psi}\right)\left(2\left\|\mathrm{U}^{k}-\dot{\mathrm{U}}^{k}\right\|_{F}^{2}+2\left\|\dot{\mathrm{U}}^{k}-\widehat{\mathrm{U}}^{k}\right\|_{F}^{2}\right) 2 1 ( λ 1 − L ∇Ψ ) U k − U k F 2 ≤ 2 1 ( λ 1 − L ∇Ψ ) ( 2 U k − U ˙ k F 2 + 2 U ˙ k − U k F 2 )
≤ 2 ( f k ( U k ) − f k ( U ˙ k ) + f k ( U ^ k ) − f k ( U ˙ k ) ) \leq2\left(f_k(\mathrm{U}^{k})-f_k(\dot{\mathrm{U}}^{k})+f_k(\widehat{\mathrm{U}}^{k})-f_k(\dot{\mathrm{U}}^{k})\right) ≤ 2 ( f k ( U k ) − f k ( U ˙ k ) + f k ( U k ) − f k ( U ˙ k ) )
≤ 4 ( f k ( U k ) − f k ( U ˙ k ) ) , \leq4\left(f_k(\mathrm{U}^{k})-f_k(\dot{\mathrm{U}}^{k})\right), ≤ 4 ( f k ( U k ) − f k ( U ˙ k ) ) ,
where, in the last inequality, we have used the fact that U ^ k ∈ argmin U ∈ S t f k ( U ) \widehat{\mathrm{U}}^{k}\in\operatorname*{argmin}_{\mathrm{U}\in\mathrm{St}}f_k(\mathrm{U}) U k ∈ argmin U ∈ St f k ( U ) and therefore f k ( U ^ k ) ≤ f k ( U k ) f_k(\widehat{\mathrm{U}}^{k})\leq f_k(\mathrm{U}^{k}) f k ( U k ) ≤ f k ( U k ) . Defining ρ ~ = L ∇ Ψ + L Ψ + L ϕ / β 0 < ρ \widetilde{\rho}=L_{\nabla\Psi}+L_{\Psi}+L_{\phi}/\beta_0<\rho ρ = L ∇Ψ + L Ψ + L ϕ / β 0 < ρ and using the definition of f k f_k f k yields
f k ( U k ) − f k ( U ˙ k ) = 1 β k Ω k ( U k ) + 1 2 λ ∥ U k − U k ∥ F 2 − 1 β k Ω k ( U ˙ k ) − 1 2 λ ∥ U ˙ k − U k ∥ F 2 + 1 2 ( 1 λ − ρ ~ ) ∥ U k − U ˙ k ∥ F 2 − 1 2 ( 1 λ − ρ ~ ) ∥ U k − U ˙ k ∥ F 2 = 1 β k Ω k ( U k ) − 1 β k Ω k ( U ˙ k ) − ρ ~ 2 ∥ U k − U ˙ k ∥ F 2 − 1 2 ( 1 λ − ρ ~ ) ∥ U k − U ˙ k ∥ F 2 ≤ 1 β k Ω k ( U k ) − 1 β k Ω k ( U ˙ k ) − L ∇ Ψ + L Ψ + L ϕ / β 0 2 ∥ U k − U ˙ k ∥ F 2 ≤ ⟨ 1 β k ω k , U k − U ˙ k ⟩ − L Ψ + L ϕ / β 0 2 ∥ U k − U ˙ k ∥ F 2 , \begin{aligned}
f_k(\mathrm{U}^{k})-f_k(\dot{\mathrm{U}}^{k})
&=\frac{1}{\beta_k}\Omega_k(\mathrm{U}^{k})+\frac{1}{2\lambda}\left\|\mathrm{U}^{k}-\mathrm{U}^{k}\right\|_{F}^{2}
-\frac{1}{\beta_k}\Omega_k(\dot{\mathrm{U}}^{k})-\frac{1}{2\lambda}\left\|\dot{\mathrm{U}}^{k}-\mathrm{U}^{k}\right\|_{F}^{2}\\
&\quad+\frac{1}{2}\left(\frac{1}{\lambda}-\widetilde{\rho}\right)\left\|\mathrm{U}^{k}-\dot{\mathrm{U}}^{k}\right\|_{F}^{2}
-\frac{1}{2}\left(\frac{1}{\lambda}-\widetilde{\rho}\right)\left\|\mathrm{U}^{k}-\dot{\mathrm{U}}^{k}\right\|_{F}^{2}\\
&=\frac{1}{\beta_k}\Omega_k(\mathrm{U}^{k})-\frac{1}{\beta_k}\Omega_k(\dot{\mathrm{U}}^{k})
-\frac{\widetilde{\rho}}{2}\left\|\mathrm{U}^{k}-\dot{\mathrm{U}}^{k}\right\|_{F}^{2}
-\frac{1}{2}\left(\frac{1}{\lambda}-\widetilde{\rho}\right)\left\|\mathrm{U}^{k}-\dot{\mathrm{U}}^{k}\right\|_{F}^{2}\\
&\leq\frac{1}{\beta_k}\Omega_k(\mathrm{U}^{k})-\frac{1}{\beta_k}\Omega_k(\dot{\mathrm{U}}^{k})
-\frac{L_{\nabla\Psi}+L_{\Psi}+L_{\phi}/\beta_0}{2}\left\|\mathrm{U}^{k}-\dot{\mathrm{U}}^{k}\right\|_{F}^{2}\\
&\leq\left\langle\frac{1}{\beta_k}\boldsymbol{\omega}^{k},\mathrm{U}^{k}-\dot{\mathrm{U}}^{k}\right\rangle
-\frac{L_{\Psi}+L_{\phi}/\beta_0}{2}\left\|\mathrm{U}^{k}-\dot{\mathrm{U}}^{k}\right\|_{F}^{2},
\end{aligned} f k ( U k ) − f k ( U ˙ k ) = β k 1 Ω k ( U k ) + 2 λ 1 U k − U k F 2 − β k 1 Ω k ( U ˙ k ) − 2 λ 1 U ˙ k − U k F 2 + 2 1 ( λ 1 − ρ ) U k − U ˙ k F 2 − 2 1 ( λ 1 − ρ ) U k − U ˙ k F 2 = β k 1 Ω k ( U k ) − β k 1 Ω k ( U ˙ k ) − 2 ρ U k − U ˙ k F 2 − 2 1 ( λ 1 − ρ ) U k − U ˙ k F 2 ≤ β k 1 Ω k ( U k ) − β k 1 Ω k ( U ˙ k ) − 2 L ∇Ψ + L Ψ + L ϕ / β 0 U k − U ˙ k F 2 ≤ ⟨ β k 1 ω k , U k − U ˙ k ⟩ − 2 L Ψ + L ϕ / β 0 U k − U ˙ k F 2 ,
where the last estimate is a consequence of 1 β k Ω k \frac{1}{\beta_k}\Omega_k β k 1 Ω k being L ∇ Ψ L_{\nabla\Psi} L ∇Ψ -weakly convex on U \mathcal{U} U and ω k ∈ ∂ Ω k ( U k ) \omega^k \in\partial\Omega_k(U^k) ω k ∈ ∂ Ω k ( U k ) being an Euclidean subgradient. Now observe that U ˙ k = t U k + ( 1 − t ) U ^ k \dot{U}^k=tU^k+(1-t)\widehat{U}^k U ˙ k = t U k + ( 1 − t ) U k for some t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] and hence
U k − U ˙ k = ( 1 − t ) U k − ( 1 − t ) U ^ k = ( 1 − t ) ( U k − U ^ k ) . U^k-\dot{U}^k=(1-t)U^k-(1-t)\widehat{U}^k=(1-t)(U^k-\widehat{U}^k). U k − U ˙ k = ( 1 − t ) U k − ( 1 − t ) U k = ( 1 − t ) ( U k − U k ) .
From Theorem 4.1 we deduce the bound
⟨ 1 β k ω k , U k − U ^ k ⟩ ≤ ⟨ 1 β k Proj T U k S t ( ω k ) , U k − U ^ k ⟩ + L Ψ + L ϕ / β 0 2 ∥ U ^ k − U k ∥ F 2 . \left\langle\frac{1}{\beta_k}\omega^k,U^k-\widehat{U}^k\right\rangle\leq\left\langle\frac{1}{\beta_k}\operatorname{Proj}_{T_{U^k}\mathrm{St}}(\omega^k),U^k-\widehat{U}^k\right\rangle+\frac{L_{\Psi}+L_{\phi}/\beta_0}{2}\left\lVert\widehat{U}^k-U^k\right\rVert_F^2. ⟨ β k 1 ω k , U k − U k ⟩ ≤ ⟨ β k 1 Proj T U k St ( ω k ) , U k − U k ⟩ + 2 L Ψ + L ϕ / β 0 U k − U k F 2 .
Combined with non-negativity of the right hand side, this leads to
⟨ 1 β k ω k , U k − U ˙ k ⟩ − L Ψ + L ϕ / β 0 2 ∥ U ^ k − U k ∥ F 2 = ( 1 − t ) ( ⟨ 1 β k ω k , U k − U ^ k ⟩ − ( 1 − t ) L Ψ + L ϕ / β 0 2 ∥ U k − U ^ k ∥ F 2 ) ≤ ( 1 − t ) ( ⟨ 1 β k g k + ∇ S t Ψ ( U k ) , U k − U ^ k ⟩ + L Ψ + L ϕ / β 0 2 ∥ U k − U ^ k ∥ F 2 ) ≤ ⟨ 1 β k g k + ∇ S t Ψ ( U k ) , U k − U ^ k ⟩ + L Ψ + L ϕ / β 0 2 ∥ U k − U ^ k ∥ F 2 . \begin{aligned}
\left\langle\frac{1}{\beta_k}\omega^k,U^k-\dot{U}^k\right\rangle-\frac{L_{\Psi}+L_{\phi}/\beta_0}{2}\left\lVert\widehat{U}^k-U^k\right\rVert_F^2
&=(1-t)\left(\left\langle\frac{1}{\beta_k}\omega^k,U^k-\widehat{U}^k\right\rangle-(1-t)\frac{L_{\Psi}+L_{\phi}/\beta_0}{2}\left\lVert U^k-\widehat{U}^k\right\rVert_F^2\right)\\
&\leq(1-t)\left(\left\langle\frac{1}{\beta_k}g^k+\nabla_{\mathrm{St}}\Psi(U^k),U^k-\widehat{U}^k\right\rangle+\frac{L_{\Psi}+L_{\phi}/\beta_0}{2}\left\lVert U^k-\widehat{U}^k\right\rVert_F^2\right)\\
&\leq\left\langle\frac{1}{\beta_k}g^k+\nabla_{\mathrm{St}}\Psi(U^k),U^k-\widehat{U}^k\right\rangle+\frac{L_{\Psi}+L_{\phi}/\beta_0}{2}\left\lVert U^k-\widehat{U}^k\right\rVert_F^2.
\end{aligned} ⟨ β k 1 ω k , U k − U ˙ k ⟩ − 2 L Ψ + L ϕ / β 0 U k − U k F 2 = ( 1 − t ) ( ⟨ β k 1 ω k , U k − U k ⟩ − ( 1 − t ) 2 L Ψ + L ϕ / β 0 U k − U k F 2 ) ≤ ( 1 − t ) ( ⟨ β k 1 g k + ∇ St Ψ ( U k ) , U k − U k ⟩ + 2 L Ψ + L ϕ / β 0 U k − U k F 2 ) ≤ ⟨ β k 1 g k + ∇ St Ψ ( U k ) , U k − U k ⟩ + 2 L Ψ + L ϕ / β 0 U k − U k F 2 .
Putting all together, we conclude with
1 8 ( 1 λ − L ∇ Ψ ) ∥ U k − U ^ k ∥ F 2 ≤ f k ( U k ) − f k ( U ˙ k ) ≤ ⟨ 1 β k g k + ∇ S t Ψ ( U k ) , U k − U ^ k ⟩ + L Ψ + L ϕ / β 0 2 ∥ U k − U ^ k ∥ F 2 . \begin{aligned}
\frac{1}{8}\left(\frac{1}{\lambda}-L_{\nabla\Psi}\right)\left\lVert U^k-\widehat{U}^k\right\rVert_F^2\leq f_k(U^k)-f_k(\dot{U}^k) \\
&\leq\left\langle\frac{1}{\beta_k}g^k+\nabla_{\mathrm{St}}\Psi(U^k),U^k-\widehat{U}^k\right\rangle+\frac{L_{\Psi}+L_{\phi}/\beta_0}{2}\left\lVert U^k-\widehat{U}^k\right\rVert_F^2.
\end{aligned} 8 1 ( λ 1 − L ∇Ψ ) U k − U k F 2 ≤ f k ( U k ) − f k ( U ˙ k ) ≤ ⟨ β k 1 g k + ∇ St Ψ ( U k ) , U k − U k ⟩ + 2 L Ψ + L ϕ / β 0 U k − U k F 2 .
Finally, subtracting L Ψ + L ϕ / β 0 2 ∥ U k − U ^ k ∥ F 2 \frac{L_{\Psi}+L_{\phi}/\beta_0}{2}\left\lVert U^k-\widehat{U}^k\right\rVert_F^2 2 L Ψ + L ϕ / β 0 U k − U k F 2 from both sides and using the definition of ρ \rho ρ yields (31) .
Next, we consider
∥ U k + 1 − V ∥ F 2 = ∥ Proj S t ( U k − γ k ( g k + β k ∇ S t Ψ ( U k ) ) ) − V ∥ F 2 ≤ ∥ U k − γ k ( g k + β k ∇ S t Ψ ( U k ) ) − V ∥ F 2 = ∥ U k − V ∥ F 2 − 2 γ k ⟨ g k + β k ∇ S t Ψ ( U k ) , U k − V ⟩ + γ k 2 ∥ g k + β k ∇ S t Ψ ( U k ) ∥ F 2 . \begin{aligned}
\left\lVert U^{k+1}-V\right\rVert_F^2
&=\left\lVert\operatorname{Proj}_{\mathrm{St}}\left(U^k-\gamma_k\left(g^k+\beta_k\nabla_{\mathrm{St}}\Psi(U^k)\right)\right)-V\right\rVert_F^2\\
&\leq\left\lVert U^k-\gamma_k\left(g^k+\beta_k\nabla_{\mathrm{St}}\Psi(U^k)\right)-V\right\rVert_F^2\\
&=\left\lVert U^k-V\right\rVert_F^2-2\gamma_k\left\langle g^k+\beta_k\nabla_{\mathrm{St}}\Psi(U^k),U^k-V\right\rangle+\gamma_k^2\left\lVert g^k+\beta_k\nabla_{\mathrm{St}}\Psi(U^k)\right\rVert_F^2.
\end{aligned} U k + 1 − V F 2 = Proj St ( U k − γ k ( g k + β k ∇ St Ψ ( U k ) ) ) − V F 2 ≤ U k − γ k ( g k + β k ∇ St Ψ ( U k ) ) − V F 2 = U k − V F 2 − 2 γ k ⟨ g k + β k ∇ St Ψ ( U k ) , U k − V ⟩ + γ k 2 g k + β k ∇ St Ψ ( U k ) F 2 .
where V ∈ S t ( K , R ) V\in\mathrm{St}(K,R) V ∈ St ( K , R ) and Lemma A.1 have been used. To bound the last quadratic term on the right-hand side, we observe
∥ g k + β k ∇ S t Ψ ( U k ) ∥ F 2 = β k 2 ∥ 1 β k g k + ∇ S t Ψ ( U k ) ∥ F 2 ≤ β k 2 ( 1 β 0 L ϕ + L Ψ ) 2 . \left\lVert g^k+\beta_k\nabla_{\mathrm{St}}\Psi(U^k)\right\rVert_F^2=\beta_k^2\left\lVert\frac{1}{\beta_k}g^k+\nabla_{\mathrm{St}}\Psi(U^k)\right\rVert_F^2\leq\beta_k^2\left(\frac{1}{\beta_0}L_{\phi}+L_{\Psi}\right)^2. g k + β k ∇ St Ψ ( U k ) F 2 = β k 2 β k 1 g k + ∇ St Ψ ( U k ) F 2 ≤ β k 2 ( β 0 1 L ϕ + L Ψ ) 2 .
Substituting this into the previous display and rearranging the terms yields (32) . For the final relation, we start with
( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) = min U ∈ S t { β k + 1 − 1 Ω k + 1 ( U ) + 1 2 λ ∥ U − U k + 1 ∥ F 2 } ≤ β k + 1 − 1 Ω k + 1 ( U ^ k ) + 1 2 λ ∥ U ^ k − U k + 1 ∥ F 2 \left(\beta_{k+1}^{-1}\Omega_{k+1}\right)\lambda(U^{k+1})=\min_{U\in\mathrm{St}}\left\{\beta_{k+1}^{-1}\Omega_{k+1}(U)+\frac{1}{2\lambda}\left\lVert U-U^{k+1}\right\rVert_F^2\right\}\leq\beta_{k+1}^{-1}\Omega_{k+1}(\widehat{U}^k)+\frac{1}{2\lambda}\left\lVert\widehat{U}^k-U^{k+1}\right\rVert_F^2 ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) = U ∈ St min { β k + 1 − 1 Ω k + 1 ( U ) + 2 λ 1 U − U k + 1 F 2 } ≤ β k + 1 − 1 Ω k + 1 ( U k ) + 2 λ 1 U k − U k + 1 F 2
and by the definition of U ^ k \hat{U}^{k} U ^ k we have
( β k − 1 Ω k ) λ ( U k ) = β k − 1 Ω k ( U ^ k ) + 1 2 λ ∥ U ^ k − U k ∥ F 2 . (\beta_k^{-1}\Omega_k)_\lambda(U^k)=\beta_k^{-1}\Omega_k(\hat{U}^k)+\frac{1}{2\lambda}\lVert\hat{U}^k-U^k\rVert_F^2. ( β k − 1 Ω k ) λ ( U k ) = β k − 1 Ω k ( U ^ k ) + 2 λ 1 ∥ U ^ k − U k ∥ F 2 .
Adding these two together, we conclude with
1 2 λ ∥ U ^ k − U k ∥ F 2 − 1 2 λ ∥ U ^ k − U k + 1 ∥ F 2 ≤ ( ( β k − 1 Ω k ) λ ( U ^ k ) − β k − 1 Ω k ( U ^ k ) ) + ( β k + 1 − 1 Ω k + 1 ( U ^ k ) − ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) ) ≤ ( β k − 1 Ω k ) λ ( U k ) − ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) − ( β k − 1 − β k + 1 − 1 ) ϕ ( U ^ k ) . \begin{aligned}
\frac{1}{2\lambda}\lVert\hat{U}^k-U^k\rVert_F^2-\frac{1}{2\lambda}\lVert\hat{U}^k-U^{k+1}\rVert_F^2
\leq\left((\beta_k^{-1}\Omega_k)_\lambda(\hat{U}^k)-\beta_k^{-1}\Omega_k(\hat{U}^k)\right)+\left(\beta_{k+1}^{-1}\Omega_{k+1}(\hat{U}^k)-(\beta_{k+1}^{-1}\Omega_{k+1})_\lambda(U^{k+1})\right) \\
&\leq(\beta_k^{-1}\Omega_k)_\lambda(U^k)-(\beta_{k+1}^{-1}\Omega_{k+1})_\lambda(U^{k+1})-(\beta_k^{-1}-\beta_{k+1}^{-1})\phi(\hat{U}^k).
\end{aligned} 2 λ 1 ∥ U ^ k − U k ∥ F 2 − 2 λ 1 ∥ U ^ k − U k + 1 ∥ F 2 ≤ ( ( β k − 1 Ω k ) λ ( U ^ k ) − β k − 1 Ω k ( U ^ k ) ) + ( β k + 1 − 1 Ω k + 1 ( U ^ k ) − ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) ) ≤ ( β k − 1 Ω k ) λ ( U k ) − ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) − ( β k − 1 − β k + 1 − 1 ) ϕ ( U ^ k ) .
By monotonicity β k − 1 − β k + 1 − 1 ≥ 0 \beta_k^{-1}-\beta_{k+1}^{-1}\geq0 β k − 1 − β k + 1 − 1 ≥ 0 and estimating ϕ ( U ^ k ) \phi(\hat{U}^k) ϕ ( U ^ k ) with its minimum, we arrive at (33) . ■
Theorem 4.7. Let { U k } \{U^k\} { U k } be the sequence generated by (13) with arbitrary initialization, step sizes ( γ k ) k (\gamma_k)_k ( γ k ) k and monotonically increasing penalty parameters ( β k ) k (\beta_k)_k ( β k ) k . Define ρ : = L ∇ Ψ + 4 L Ψ + 4 L ϕ / β 0 \rho:= L_{\nabla\Psi}+4L_\Psi+4L_\phi/\beta_0 ρ := L ∇Ψ + 4 L Ψ + 4 L ϕ / β 0 . Then, for every λ < 1 / ρ \lambda<1/\rho λ < 1/ ρ , the following estimate holds
min 0 ≤ k ≤ T β k 2 Θ λ Ω k / β k ( U k ) 2 ≤ 8 1 − λ ρ β 0 Ω 0 ( U 0 ) + β T + 1 2 C max + 2 β T + 1 2 ∣ ϕ ∗ ∣ + L 2 2 λ ∑ k = 0 T β k 2 ( γ k β k ) 2 ∑ k = 0 T γ k β k , (34) \min_{0\leq k\leq T}\beta_k^2\Theta_{\lambda\Omega_k/\beta_k}(U^k)^2\leq\frac{8}{1-\lambda\rho}\frac{\beta_0\Omega_0(U^0)+\beta_{T+1}^2C_{\max}+2\beta_{T+1}^2|\phi^*|+\frac{L^2}{2\lambda}\sum_{k=0}^{T}\beta_k^2(\gamma_k\beta_k)^2}{\sum_{k=0}^{T}\gamma_k\beta_k}, \tag*{(34)} 0 ≤ k ≤ T min β k 2 Θ λ Ω k / β k ( U k ) 2 ≤ 1 − λ ρ 8 ∑ k = 0 T γ k β k β 0 Ω 0 ( U 0 ) + β T + 1 2 C m a x + 2 β T + 1 2 ∣ ϕ ∗ ∣ + 2 λ L 2 ∑ k = 0 T β k 2 ( γ k β k ) 2 , (34) where C max : = β 0 − 1 max S t ϕ + max S t Ψ + ∣ min S t Ψ ∣ C_{\max}:=\beta_0^{-1}\max_{\mathrm{St}}\phi+\max_{\mathrm{St}}\Psi+|\min_{\mathrm{St}}\Psi| C m a x := β 0 − 1 max St ϕ + max St Ψ + ∣ min St Ψ∣ , ϕ ∗ : = min S t ϕ \phi^*:=\min_{\mathrm{St}}\phi ϕ ∗ := min St ϕ and L : = β 0 − 1 L ϕ + L Ψ L:=\beta_0^{-1}L_\phi+L_\Psi L := β 0 − 1 L ϕ + L Ψ . In particular, the right-hand side of (34) converges to zero as T → ∞ T\to\infty T → ∞ if and only if the following design criteria for the step-size and penalty sequences are satisfied:
∑ k = 0 T γ k β k → ∞ , ∑ k = 0 T β k 2 ( γ k β k ) 2 ∑ k = 0 T γ k β k → 0 , β T + 1 2 ∑ k = 0 T γ k β k → 0. \sum_{k=0}^{T}\gamma_k\beta_k\to\infty,\qquad
\frac{\sum_{k=0}^{T}\beta_k^2(\gamma_k\beta_k)^2}{\sum_{k=0}^{T}\gamma_k\beta_k}\to0,\qquad
\frac{\beta_{T+1}^2}{\sum_{k=0}^{T}\gamma_k\beta_k}\to0. k = 0 ∑ T γ k β k → ∞ , ∑ k = 0 T γ k β k ∑ k = 0 T β k 2 ( γ k β k ) 2 → 0 , ∑ k = 0 T γ k β k β T + 1 2 → 0.
Proof. Define U ^ k : = prox ( λ / β k ) Ω k ( U k ) \hat{U}^k:=\operatorname{prox}_{(\lambda/\beta_k)\Omega_k}(U^k) U ^ k := prox ( λ / β k ) Ω k ( U k ) and as defined in (15) we have
Θ ( λ / β k ) Ω k ( U k ) = λ − 1 ∥ U ^ k − U k ∥ . \Theta_{(\lambda/\beta_k)\Omega_k}(U^k)=\lambda^{-1}\lVert\hat{U}^k-U^k\rVert. Θ ( λ / β k ) Ω k ( U k ) = λ − 1 ∥ U ^ k − U k ∥ .
The inequalities of Lemma 4.6 yield the following estimate:
( γ k β k ) β k 2 λ − 2 ∥ U k − U ^ k ∥ 2 ≤ 8 λ ( 1 − λ ρ ) β k 2 ( γ k β k ) ⟨ 1 β k g k + ∇ S t Ψ ( U k ) , U k − U ^ k ⟩ ≤ 8 1 − λ ρ β k 2 [ ( β k − 1 Ω k ) λ ( U k ) − ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) \begin{aligned}
(\gamma_k\beta_k)\beta_k^2\lambda^{-2}\lVert U^k-\hat{U}^k\rVert^2
\leq\frac{8}{\lambda(1-\lambda\rho)}\beta_k^2(\gamma_k\beta_k)\left\langle\frac{1}{\beta_k}g^k+\nabla_{\mathrm{St}}\Psi(U^k),U^k-\hat{U}^k\right\rangle\\
&\leq\frac{8}{1-\lambda\rho}\beta_k^2\left[(\beta_k^{-1}\Omega_k)_\lambda(U^k)-(\beta_{k+1}^{-1}\Omega_{k+1})_\lambda(U^{k+1})\right.
\end{aligned} ( γ k β k ) β k 2 λ − 2 ∥ U k − U ^ k ∥ 2 ≤ λ ( 1 − λ ρ ) 8 β k 2 ( γ k β k ) ⟨ β k 1 g k + ∇ St Ψ ( U k ) , U k − U ^ k ⟩ ≤ 1 − λ ρ 8 β k 2 [ ( β k − 1 Ω k ) λ ( U k ) − ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 )
− ( β k − 1 − β k + 1 − 1 ) ϕ ∗ + 1 2 λ ( γ k β k ) 2 ( 1 β 0 L ϕ + L Ψ ) 2 ] . \left.-(\beta_k^{-1}-\beta_{k+1}^{-1})\phi^*+\frac{1}{2\lambda}(\gamma_k\beta_k)^2\left(\frac{1}{\beta_0}L_\phi+L_\Psi\right)^2\right]. − ( β k − 1 − β k + 1 − 1 ) ϕ ∗ + 2 λ 1 ( γ k β k ) 2 ( β 0 1 L ϕ + L Ψ ) 2 ] .
To obtain a recursion, consider that ( β k ) k (\beta_k)_k ( β k ) k is monotonically increasing, we estimate
− β k 2 ( β k − 1 − β k + 1 − 1 ) ϕ ∗ ≤ β k β k + 1 ( β k − 1 − β k + 1 − 1 ) ∣ ϕ ∗ ∣ ≤ ( β k + 1 − β k ) ∣ ϕ ∗ ∣ . -\beta_k^2(\beta_k^{-1}-\beta_{k+1}^{-1})\phi^*
\leq\beta_k\beta_{k+1}(\beta_k^{-1}-\beta_{k+1}^{-1})|\phi^*|
\leq(\beta_{k+1}-\beta_k)|\phi^*|. − β k 2 ( β k − 1 − β k + 1 − 1 ) ϕ ∗ ≤ β k β k + 1 ( β k − 1 − β k + 1 − 1 ) ∣ ϕ ∗ ∣ ≤ ( β k + 1 − β k ) ∣ ϕ ∗ ∣.
Additionally, we have
− β k 2 ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) = − β k + 1 2 ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) + ( β k + 1 2 − β k 2 ) ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) ≤ − β k + 1 2 ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) + ( β k + 1 2 − β k 2 ) ( 1 β 0 max U ∈ S t ϕ ( U ) + max U ∈ S t Ψ ( U ) ) \begin{aligned}
-\beta_k^2(\beta_{k+1}^{-1}\Omega_{k+1})_\lambda(U^{k+1})
=-\beta_{k+1}^2(\beta_{k+1}^{-1}\Omega_{k+1})_\lambda(U^{k+1})+(\beta_{k+1}^2-\beta_k^2)(\beta_{k+1}^{-1}\Omega_{k+1})_\lambda(U^{k+1}) \\
&\leq-\beta_{k+1}^2(\beta_{k+1}^{-1}\Omega_{k+1})_\lambda(U^{k+1})+(\beta_{k+1}^2-\beta_k^2)\left(\frac{1}{\beta_0}\max_{U\in\mathrm{St}}\phi(U)+\max_{U\in\mathrm{St}}\Psi(U)\right)
\end{aligned} − β k 2 ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) = − β k + 1 2 ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) + ( β k + 1 2 − β k 2 ) ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) ≤ − β k + 1 2 ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) + ( β k + 1 2 − β k 2 ) ( β 0 1 U ∈ St max ϕ ( U ) + U ∈ St max Ψ ( U ) )
We use the upper bound
( 1 β k + 1 Ω k + 1 ) λ ( U k + 1 ) ≤ 1 β k + 1 Ω k + 1 ( U k + 1 ) ≤ 1 β 0 max U ∈ S t ϕ ( U ) + max U ∈ S t Ψ ( U ) \left(\frac{1}{\beta_{k+1}}\Omega_{k+1}\right)_{\lambda}(U^{k+1}) \leq\frac{1}{\beta_{k+1}}\Omega_{k+1}(U^{k+1}) \leq\frac{1}{\beta_0}\max_{U\in\mathrm{St}}\phi(U)+\max_{U\in\mathrm{St}}\Psi(U) ( β k + 1 1 Ω k + 1 ) λ ( U k + 1 ) ≤ β k + 1 1 Ω k + 1 ( U k + 1 ) ≤ β 0 1 U ∈ St max ϕ ( U ) + U ∈ St max Ψ ( U )
in order to obtain the expression − β k + 1 2 ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) -\beta_{k+1}^{2}(\beta_{k+1}^{-1}\Omega_{k+1})_{\lambda}(U^{k+1}) − β k + 1 2 ( β k + 1 − 1 Ω k + 1 ) λ ( U k + 1 ) for the recursion. Summing over k = 0 , … , T k=0,\ldots,T k = 0 , … , T yields
∑ k = 0 T ( γ k β k ) β k 2 Θ λ / β k Ω k ( U k ) 2 ≤ 8 1 − λ ρ [ β 0 2 ( β 0 − 1 Ω 0 ) λ ( U 0 ) − β T + 1 2 ( β T + 1 − 1 Ω T + 1 ) λ ( U T + 1 ) ] + ( β T + 1 2 − β 0 2 ) 1 β 0 max U ∈ S t ϕ + max U ∈ S t Ψ + ( β T + 1 − β 0 ) ∣ ϕ ∗ ∣ + 1 2 λ ( 1 β 0 L ϕ + L Ψ ) 2 ∑ k = 0 T β k 2 ( γ k β k ) 2 . \begin{aligned}
\sum_{k=0}^{T}(\gamma_k\beta_k)\beta_k^2\Theta_{\lambda/\beta_k}\Omega_k(U^k)^2 \leq\frac{8}{1-\lambda\rho}\left[\beta_0^2(\beta_0^{-1}\Omega_0)_{\lambda}(U^0)-\beta_{T+1}^2(\beta_{T+1}^{-1}\Omega_{T+1})_{\lambda}(U^{T+1})\right] \\
&+(\beta_{T+1}^2-\beta_0^2)\frac{1}{\beta_0}\max_{U\in\mathrm{St}}\phi+\max_{U\in\mathrm{St}}\Psi\\
&+(\beta_{T+1}-\beta_0)|\phi^*|+\frac{1}{2\lambda}\left(\frac{1}{\beta_0}L_\phi+L_\Psi\right)^2\sum_{k=0}^{T}\beta_k^2(\gamma_k\beta_k)^2.
\end{aligned} k = 0 ∑ T ( γ k β k ) β k 2 Θ λ / β k Ω k ( U k ) 2 ≤ 1 − λ ρ 8 [ β 0 2 ( β 0 − 1 Ω 0 ) λ ( U 0 ) − β T + 1 2 ( β T + 1 − 1 Ω T + 1 ) λ ( U T + 1 ) ] + ( β T + 1 2 − β 0 2 ) β 0 1 U ∈ St max ϕ + U ∈ St max Ψ + ( β T + 1 − β 0 ) ∣ ϕ ∗ ∣ + 2 λ 1 ( β 0 1 L ϕ + L Ψ ) 2 k = 0 ∑ T β k 2 ( γ k β k ) 2 .
Moreover, note that β 0 2 ( β 0 Ω 0 ) λ ( U 0 ) ≤ β 0 Ω 0 ( U 0 ) \beta_0^2(\beta_0\Omega_0)_{\lambda}(U^0)\leq\beta_0\Omega_0(U^0) β 0 2 ( β 0 Ω 0 ) λ ( U 0 ) ≤ β 0 Ω 0 ( U 0 ) and β T + 1 − 1 Ω T + 1 ) λ ( U T + 1 ) ≥ − ( β T + 1 − 1 ∣ ϕ ∗ ∣ + ∣ min S t Ψ ∣ ) \beta_{T+1}^{-1}\Omega_{T+1})_{\lambda}(U^{T+1})\geq-(\beta_{T+1}^{-1}|\phi^*|+|\min_{\mathrm{St}}\Psi|) β T + 1 − 1 Ω T + 1 ) λ ( U T + 1 ) ≥ − ( β T + 1 − 1 ∣ ϕ ∗ ∣ + ∣ min St Ψ∣ ) . Hence,
β 0 2 ( β 0 − 1 Ω 0 ) λ ( U 0 ) − β T + 1 2 ( β T + 1 − 1 Ω T + 1 ) λ ( U T + 1 ) ≤ β 0 Ω 0 ( U 0 ) + β T + 1 ∣ ϕ ∗ ∣ + β T + 1 2 ∣ min S t Ψ ∣ . \beta_0^2(\beta_0^{-1}\Omega_0)_{\lambda}(U^0)-\beta_{T+1}^2(\beta_{T+1}^{-1}\Omega_{T+1})_{\lambda}(U^{T+1})\leq\beta_0\Omega_0(U^0)+\beta_{T+1}|\phi^*|+\beta_{T+1}^2\left|\min_{\mathrm{St}}\Psi\right|. β 0 2 ( β 0 − 1 Ω 0 ) λ ( U 0 ) − β T + 1 2 ( β T + 1 − 1 Ω T + 1 ) λ ( U T + 1 ) ≤ β 0 Ω 0 ( U 0 ) + β T + 1 ∣ ϕ ∗ ∣ + β T + 1 2 St min Ψ .
By positivity, we have min 0 ≤ k ≤ T β k 2 Θ λ / β k Ω k ( U k ) 2 ∑ k = 0 T γ k β k ≤ ∑ k = 0 T γ k β k β k 2 Θ λ / β k Ω k ( U k ) 2 \min_{0\leq k\leq T}\beta_k^2\Theta_{\lambda/\beta_k}\Omega_k(U^k)^2\sum_{k=0}^{T}\gamma_k\beta_k\leq\sum_{k=0}^{T}\gamma_k\beta_k\beta_k^2\Theta_{\lambda/\beta_k}\Omega_k(U^k)^2 min 0 ≤ k ≤ T β k 2 Θ λ / β k Ω k ( U k ) 2 ∑ k = 0 T γ k β k ≤ ∑ k = 0 T γ k β k β k 2 Θ λ / β k Ω k ( U k ) 2 . Cancelling the negative terms yield the bound (34) . ■
Theorem 4.7 provides a general upper bound on the stationarity measure β k Θ λ Ω k / β k \beta_k\Theta_{\lambda\Omega_k/\beta_k} β k Θ λ Ω k / β k that accounts for the penalized objective function. It also specifies conditions on the step sizes and penalty parameters that guarantee convergence to a stationary point. The dependence on the auxiliary parameter λ > 0 \lambda>0 λ > 0 is similar to that in Theorem 4.3: as λ → 0 \lambda\to0 λ → 0 , the coefficient of the quadratic term becomes arbitrarily large, while as λ \lambda λ approaches its upper admissible bound, the constant in the denominator becomes arbitrarily small, causing the overall bound to deteriorate.
In the following corollary, we specify the step sizes and penalty parameters to obtain a convergence rate for the penalized problem.
Corollary 4.8. Let { U k } \{U^k\} { U k } be the sequence generated by (13) with arbitrary initialization. Set γ k = γ ~ / ( β k k + 1 ) \gamma_k=\widetilde{\gamma}/(\beta_k\sqrt{k+1}) γ k = γ / ( β k k + 1 ) with β k = C ( k + 1 ) p \beta_k=C(k+1)^p β k = C ( k + 1 ) p for some C > 0 C>0 C > 0 and p ∈ ( 0 , 1 / 2 ) p\in(0,1/2) p ∈ ( 0 , 1/2 ) . Define U ^ k = prox λ Ω k / β k ( U k ) \widehat{U}^k=\operatorname{prox}_{\lambda\Omega_k/\beta_k}(U^k) U k = prox λ Ω k / β k ( U k ) . Then
min 0 ≤ k ≤ T dist ( 0 , ∂ S t Ω k ( U ^ k ) ) ∈ O ( T − ( 1 / 4 − p ) ) . (35) \min_{0\leq k\leq T}\operatorname{dist}(0,\partial_{\mathrm{St}}\Omega_k(\widehat{U}^k))\in O\left(T^{-(1/4-p)}\right). \tag*{(35)} 0 ≤ k ≤ T min dist ( 0 , ∂ St Ω k ( U k )) ∈ O ( T − ( 1/4 − p ) ) . (35) In particular, the stationarity measure converges to zero as T → ∞ T\to\infty T → ∞ for any p < 1 / 4 p<1/4 p < 1/4 .
Proof. Recall from (15) that U ^ k \widehat{U}^k U k fulfills dist ( 0 , ∂ S t Ω k ( U ^ k ) ) ≤ β k Θ λ Ω k / β k ( U k ) \operatorname{dist}(0,\partial_{\mathrm{St}}\Omega_k(\widehat{U}^k))\leq\beta_k\Theta_{\lambda\Omega_k/\beta_k}(U^k) dist ( 0 , ∂ St Ω k ( U k )) ≤ β k Θ λ Ω k / β k ( U k ) . Using the definition of the penalty and step-size parameter, we obtain for p < 1 / 2 p<1/2 p < 1/2
∑ k = 0 T γ k β k = γ ~ C ∑ k = 0 T 1 k + 1 ≥ γ ~ C T + 1 \sum_{k=0}^{T}\gamma_k\beta_k=\widetilde{\gamma}C\sum_{k=0}^{T}\frac{1}{\sqrt{k+1}}\geq\widetilde{\gamma}C\sqrt{T+1} k = 0 ∑ T γ k β k = γ C k = 0 ∑ T k + 1 1 ≥ γ C T + 1
∑ k = 0 T γ k 2 β k 4 = γ ~ 2 C 4 ∑ k = 0 T 1 ( k + 1 ) 1 − 2 p = γ ~ 2 C 4 ( 1 + ∑ k = 1 T 1 ( k + 1 ) 1 − 2 p ) ≤ γ ~ 2 C 4 ( 1 + ∫ 0 T 1 ( x + 1 ) 1 − 2 p d x ) ≤ γ ~ 2 C 4 ( 1 + ( T + 1 ) 2 p 2 p ) . \begin{aligned}
\sum_{k=0}^{T}\gamma_k^2\beta_k^4=\widetilde{\gamma}^2C^4\sum_{k=0}^{T}\frac{1}{(k+1)^{1-2p}}=\widetilde{\gamma}^2C^4\left(1+\sum_{k=1}^{T}\frac{1}{(k+1)^{1-2p}}\right) \\
&\leq\widetilde{\gamma}^2C^4\left(1+\int_0^T\frac{1}{(x+1)^{1-2p}}\,\mathrm{d}x\right)\leq\widetilde{\gamma}^2C^4\left(1+\frac{(T+1)^{2p}}{2p}\right).
\end{aligned} k = 0 ∑ T γ k 2 β k 4 = γ 2 C 4 k = 0 ∑ T ( k + 1 ) 1 − 2 p 1 = γ 2 C 4 ( 1 + k = 1 ∑ T ( k + 1 ) 1 − 2 p 1 ) ≤ γ 2 C 4 ( 1 + ∫ 0 T ( x + 1 ) 1 − 2 p 1 d x ) ≤ γ 2 C 4 ( 1 + 2 p ( T + 1 ) 2 p ) .
From Theorem 4.7 , we deduce that
min 0 ≤ k ≤ T dist ( 0 , ∂ S t Ω k ( U ^ k ) ) ≤ 8 1 − λ ρ β 0 Ω 0 ( U 0 ) + C 2 ( T + 2 ) 2 p C max + 2 C ( T + 2 ) p ∣ ϕ ∗ ∣ + L 2 γ ~ 2 C 4 2 λ ( 1 + ( T + 1 ) 2 p 2 p ) γ ~ C T + 1 ∈ O ( T p − 1 / 4 ) . \begin{aligned}
\min_{0\leq k\leq T}\operatorname{dist}(0,\partial_{\mathrm{St}}\Omega_k(\widehat{U}^k))
&\leq\sqrt{\frac{8}{1-\lambda\rho}\frac{\beta_0\Omega_0(U^0)+C^2(T+2)^{2p}C_{\max}+2C(T+2)^p|\phi^*|+\frac{L^2\tilde{\gamma}^2 C^4}{2\lambda}\left(1+\frac{(T+1)^{2p}}{2p}\right)}{\tilde{\gamma}C\sqrt{T+1}}} \\
&\in O(T^{p-1/4}).
\end{aligned} 0 ≤ k ≤ T min dist ( 0 , ∂ St Ω k ( U k )) ≤ 1 − λ ρ 8 γ ~ C T + 1 β 0 Ω 0 ( U 0 ) + C 2 ( T + 2 ) 2 p C m a x + 2 C ( T + 2 ) p ∣ ϕ ∗ ∣ + 2 λ L 2 γ ~ 2 C 4 ( 1 + 2 p ( T + 1 ) 2 p ) ∈ O ( T p − 1/4 ) .
The corollary shows that the distance to the Riemannian subdifferential can be made arbitrarily small. However, this does not yet imply that the corresponding Riemannian subgradients converge. In contrast to the lower-level problem, the subdifferential here is set-valued rather than given by a continuous gradient. Moreover, since ϕ \phi ϕ is assumed to be convex only in the ambient Euclidean space, the corresponding outer semicontinuity of the Riemannian subdifferential is not immediate. The following lemma shows that, nevertheless, convergent subsequences of Riemannian subgradients have limits that remain in the Riemannian subdifferential.
Lemma 4.9. Let { V k } \{V^k\} { V k } be a convergent sequence in S t ( K , R ) \mathrm{St}(K,R) St ( K , R ) with limit point V ∗ V^* V ∗ and g k ∈ ∂ S t ϕ ( V k ) g^k \in\partial_{\mathrm{St}}\phi(V^k) g k ∈ ∂ St ϕ ( V k ) be a collection of Riemannian subgradients of the convex function ϕ \phi ϕ . Then { g k } \{g^k\} { g k } admits a converging subsequence g τ ( k ) → g ∗ ∈ ∂ S t ϕ ( V ∗ ) g^{\tau(k)} \to g^* \in\partial_{\mathrm{St}}\phi(V^*) g τ ( k ) → g ∗ ∈ ∂ St ϕ ( V ∗ ) .
Proof. Since S t ( K , R ) \mathrm{St}(K,R) St ( K , R ) is compact and ϕ \phi ϕ is convex, the Euclidean subgradients of ϕ \phi ϕ are uniformly bounded on S t ( K , R ) \mathrm{St}(K,R) St ( K , R ) , i.e.
( ∃ M > 0 ) ( ∀ V ∈ S t ( K , R ) ) : ∀ g ~ ∈ ∂ ϕ ( V ) : ∥ g ~ ∥ ≤ M . (\exists M>0)(\forall V\in\mathrm{St}(K,R)):\ \forall\widetilde{g}\in\partial\phi(V):\quad\lVert\widetilde{g}\rVert\leq M. ( ∃ M > 0 ) ( ∀ V ∈ St ( K , R )) : ∀ g ∈ ∂ ϕ ( V ) : ∥ g ∥ ≤ M .
Hence, every collection of Euclidean subgradients { g ~ k ∈ ∂ ϕ ( V k ) } \{\widetilde{g}^k\in\partial\phi(V^k)\} { g k ∈ ∂ ϕ ( V k )} is bounded. Since we are in finite dimensional spaces, every bounded sequence admits a convergent subsequence. Thus, we can pick a convergence subsequence g ~ τ ( k ) → g ~ ∗ \widetilde{g}^{\tau(k)}\to\widetilde{g}^* g τ ( k ) → g ∗ . We show that g ~ ∗ ∈ ∂ ϕ ( V ∗ ) \widetilde{g}^*\in\partial\phi(V^*) g ∗ ∈ ∂ ϕ ( V ∗ ) . For every k k k and every V ∈ R K × R V\in\mathbb{R}^{K\times R} V ∈ R K × R ,
ϕ ( V ) ≥ ϕ ( V τ ( k ) ) + ⟨ g ~ τ ( k ) , V − V τ ( k ) ⟩ . \phi(V)\geq\phi(V^{\tau(k)})+\langle\widetilde{g}^{\tau(k)},V-V^{\tau(k)}\rangle. ϕ ( V ) ≥ ϕ ( V τ ( k ) ) + ⟨ g τ ( k ) , V − V τ ( k ) ⟩ .
Passing to the limit as k → ∞ k\to\infty k → ∞ and using the continuity of convex functions yields g ~ ∗ ∈ ∂ ϕ ( V ∗ ) \widetilde{g}^*\in\partial\phi(V^*) g ∗ ∈ ∂ ϕ ( V ∗ ) . Now we show the same for the Riemannian subgradients. We know that every Riemannian subgradient is the orthogonal projection of an Euclidean subgradient onto the tangent space (cf. Appendix § 10 .§ 1 ):
g k = Proj T V k S t ( g ~ k ) . g^k=\operatorname{Proj}_{T_{V^k}\mathrm{St}}(\widetilde{g}^k). g k = Proj T V k St ( g k ) .
Since orthogonal projection is nonexpansive we have ∥ g k ∥ ≤ ∥ g ~ k ∥ \lVert g^k\rVert\leq\lVert\widetilde{g}^k\rVert ∥ g k ∥ ≤ ∥ g k ∥ and hence every collection { g k ∈ ∂ S t ϕ ( V k ) } \{g^k\in\partial_{\mathrm{St}}\phi(V^k)\} { g k ∈ ∂ St ϕ ( V k )} is bounded and admits a converging subsequence g τ ( k ) → g ∗ g^{\tau(k)}\to g^* g τ ( k ) → g ∗ . Then, by the continuity of the tangent-space projection
g ∗ = Proj T V ∗ S t ( g ~ ∗ ) ∈ ∂ S t ϕ ( V ∗ ) . g^*=\operatorname{Proj}_{T_{V^*}\mathrm{St}}(\widetilde{g}^*)\in\partial_{\mathrm{St}}\phi(V^*). g ∗ = Proj T V ∗ St ( g ∗ ) ∈ ∂ St ϕ ( V ∗ ) .
In summary, the above results show that, with U ^ k = prox λ Ω k / β k ( U k ) , \widehat{U}^k=\operatorname{prox}_{\lambda\Omega_k/\beta_k}(U^k), U k = prox λ Ω k / β k ( U k ) , there exists a subsequence { τ ( k ) } \{\tau(k)\} { τ ( k )} and a limit point U ∗ U^* U ∗ such that
U τ ( k ) → U ∗ , U ^ τ ( k ) → U ∗ , U ∗ ∈ N Ψ = { U ∣ ∇ S t Ψ ( U ) = 0 } . U^{\tau(k)}\to U^*,\qquad\widehat{U}^{\tau(k)}\to U^*,\qquad U^*\in N_{\Psi}=\{U\mid\nabla_{\mathrm{St}}\Psi(U)=0\}. U τ ( k ) → U ∗ , U τ ( k ) → U ∗ , U ∗ ∈ N Ψ = { U ∣ ∇ St Ψ ( U ) = 0 } .
Moreover, there exist g ^ k ∈ ∂ S t ϕ ( U ^ k ) \hat{g}^{k} \in\partial_{\mathrm{St}}\phi(\hat{U}^{k}) g ^ k ∈ ∂ St ϕ ( U ^ k ) and g ∗ ∈ ∂ S t ϕ ( U ∗ ) g^{*} \in\partial_{\mathrm{St}}\phi(U^{*}) g ∗ ∈ ∂ St ϕ ( U ∗ ) such that
g ^ τ ( k ) → g ∗ , ∥ g ^ τ ( k ) + β τ ( k ) ∇ S t Ψ ( U ^ τ ( k ) ) ∥ → 0. \hat{g}^{\tau(k)} \to g^{*}, \qquad\left\|\hat{g}^{\tau(k)}+\beta_{\tau(k)}\nabla_{\mathrm{St}}\Psi(\hat{U}^{\tau(k)})\right\| \to0. g ^ τ ( k ) → g ∗ , g ^ τ ( k ) + β τ ( k ) ∇ St Ψ ( U ^ τ ( k ) ) → 0.
These stationarity properties provide useful information about the asymptotic behavior of the algorithm. To obtain a more precise characterization of the limit points and, in particular, to relate them to the upper-level problem, we impose additional regularity assumptions on Ψ \Psi Ψ and at the limit points U ∗ U^{*} U ∗ . Under these assumptions, we can characterize the limit points of the algorithm more precisely: they are, in fact, stationary points of the upper-level objective ϕ \phi ϕ restricted to the stationary set of Ψ \Psi Ψ .
Taylor expansion on the Stiefel manifold. In the following, we use a second-order Taylor expansion of Ψ \Psi Ψ on the Stiefel manifold. We assume that Ψ \Psi Ψ is twice continuously differentiable. Unlike in Euclidean space, where Taylor expansions are formulated along straight lines, on a Riemannian manifold they are formulated along geodesics, which are the manifold analogues of straight lines. Moreover, tangent vectors at different points belong to different tangent spaces and therefore cannot be directly compared. Parallel transport provides a way to move tangent vectors between tangent spaces while preserving the Riemannian metric.
A detailed introduction to geodesics, the exponential and logarithmic maps, and parallel transport is provided in Appendix § 10 .§ 4 ; see also [7 Chapter 10] . Here, let c ( t ) = Exp A ( t ξ ) c(t)=\operatorname{Exp}_{A}(t\xi) c ( t ) = Exp A ( t ξ ) be the geodesic connecting two sufficiently close points A , B ∈ S t A,B \in\mathrm{St} A , B ∈ St , with A = c ( 0 ) A=c(0) A = c ( 0 ) , B = c ( 1 ) = Exp A ( ξ ) B=c(1)=\operatorname{Exp}_{A}(\xi) B = c ( 1 ) = Exp A ( ξ ) and ξ = Log A ( B ) ∈ T A S t \xi=\operatorname{Log}_{A}(B) \in T_{A}\mathrm{St} ξ = Log A ( B ) ∈ T A St . Thus, ξ \xi ξ is the tangent vector at A A A pointing along the geodesic from A A A to B B B . We denote parallel transport along c c c from c ( 0 ) c(0) c ( 0 ) to c ( t ) c(t) c ( t ) by
P t ξ = P t ← 0 c : T c ( 0 ) S t → T c ( t ) S t . P_{t\xi}=P^{c}_{t\leftarrow0}:T_{c(0)}\mathrm{St}\to T_{c(t)}\mathrm{St}. P t ξ = P t ← 0 c : T c ( 0 ) St → T c ( t ) St .
Let { V k } \{V^{k}\} { V k } be a convergent sequence in S t ( K , R ) \mathrm{St}(K,R) St ( K , R ) with limit point V ∗ V^{*} V ∗ such that ∇ S t Ψ ( V ∗ ) = 0 \nabla_{\mathrm{St}}\Psi(V^{*})=0 ∇ St Ψ ( V ∗ ) = 0 . For k ∈ N k \in\mathbb{N} k ∈ N sufficiently large, let v k = Log V ∗ ( V k ) ∈ T V ∗ S t v_{k}=\operatorname{Log}_{V^{*}}(V^{k}) \in T_{V^{*}}\mathrm{St} v k = Log V ∗ ( V k ) ∈ T V ∗ St denote the initial velocity of the geodesic c k ( t ) = Exp V ∗ ( t v k ) c_{k}(t)=\operatorname{Exp}_{V^{*}}(tv_{k}) c k ( t ) = Exp V ∗ ( t v k ) with c k ( 0 ) = V ∗ c_{k}(0)=V^{*} c k ( 0 ) = V ∗ and c k ( 1 ) = V k c_{k}(1)=V^{k} c k ( 1 ) = V k . Since ∇ S t Ψ ( V ∗ ) = 0 \nabla_{\mathrm{St}}\Psi(V^{*})=0 ∇ St Ψ ( V ∗ ) = 0 , Taylor’s theorem yields
P v k − 1 ∇ S t Ψ ( V k ) = ∫ 0 1 ( P t v k − 1 ∘ Hess S t Ψ ( c k ( t ) ) ∘ P t v k ) [ v k ] d t . (36) P_{v_{k}}^{-1}\nabla_{\mathrm{St}}\Psi(V^{k})=\int_{0}^{1}\left(P_{tv_{k}}^{-1}\circ\operatorname{Hess}_{\mathrm{St}}\Psi(c_{k}(t))\circ P_{tv_{k}}\right)[v_{k}]\,\mathrm{d}t. \tag*{(36)} P v k − 1 ∇ St Ψ ( V k ) = ∫ 0 1 ( P t v k − 1 ∘ Hess St Ψ ( c k ( t )) ∘ P t v k ) [ v k ] d t . (36)
We define the family of linear operators { B k } k : T V ∗ S t → T V ∗ S t \{B^{k}\}_{k}:T_{V^{*}}\mathrm{St}\to T_{V^{*}}\mathrm{St} { B k } k : T V ∗ St → T V ∗ St by
B k : = ∫ 0 1 P t v k − 1 ∘ Hess S t Ψ ( c k ( t ) ) ∘ P t v k d t . (37) B^{k}:=\int_{0}^{1}P_{tv_{k}}^{-1}\circ\operatorname{Hess}_{\mathrm{St}}\Psi(c_{k}(t))\circ P_{tv_{k}}\,\mathrm{d}t. \tag*{(37)} B k := ∫ 0 1 P t v k − 1 ∘ Hess St Ψ ( c k ( t )) ∘ P t v k d t . (37)
Since c k ( t ) → V ∗ c_{k}(t)\to V^{*} c k ( t ) → V ∗ uniformly in t t t , Hess S t Ψ ( c k ( t ) ) → Hess S t Ψ ( V ∗ ) \operatorname{Hess}_{\mathrm{St}}\Psi(c_{k}(t))\to\operatorname{Hess}_{\mathrm{St}}\Psi(V^{*}) Hess St Ψ ( c k ( t )) → Hess St Ψ ( V ∗ ) uniformly in t t t . Moreover, P t v k → Id P_{tv_{k}}\to\operatorname{Id} P t v k → Id and P t v k − 1 → Id P_{tv_{k}}^{-1}\to\operatorname{Id} P t v k − 1 → Id uniformly in t t t . Consequently,
B k → Hess S t Ψ ( V ∗ ) as k → ∞ . B^{k}\to\operatorname{Hess}_{\mathrm{St}}\Psi(V^{*}) \quad\text{as } k\to\infty. B k → Hess St Ψ ( V ∗ ) as k → ∞.
Throughout the remainder of this section, we impose the following assumptions.
Assumption 1. Ψ \Psi Ψ is twice continuously differentiable on S t ( K , R ) \mathrm{St}(K,R) St ( K , R ) .
Assumption 2 (Constant-rank condition). Let { V k } \{V^{k}\} { V k } be a convergent sequence in S t ( K , R ) \mathrm{St}(K,R) St ( K , R ) with V k → V ∗ V^{k}\to V^{*} V k → V ∗ . The corresponding operators { B k } \{B^{k}\} { B k } defined in (37) satisfy
rank ( B k ) = rank ( Hess S t Ψ ( V ∗ ) ) \operatorname{rank}(B^{k})=\operatorname{rank}\left(\operatorname{Hess}_{\mathrm{St}}\Psi(V^{*})\right) rank ( B k ) = rank ( Hess St Ψ ( V ∗ ) )
for all sufficiently large k k k .
Proposition 4.10. Let { V k } \{V^k\} { V k } be a convergent sequence in St ( K , R ) \operatorname{St}(K,\mathbb{R}) St ( K , R ) with limit point V ∗ V^* V ∗ such that ∇ St Ψ ( V ∗ ) = 0 \nabla_{\operatorname{St}}\Psi(V^*)=0 ∇ St Ψ ( V ∗ ) = 0 . Let g k ∈ ∂ St ϕ ( V k ) g^k\in\partial_{\operatorname{St}}\phi(V^k) g k ∈ ∂ St ϕ ( V k ) be a collection of Riemannian subgradients such that g k → g ∗ ∈ ∂ St ϕ ( V ∗ ) g^k\to g^*\in\partial_{\operatorname{St}}\phi(V^*) g k → g ∗ ∈ ∂ St ϕ ( V ∗ ) and ∥ g k + β k ∇ St Ψ ( V k ) ∥ → 0 \lVert g^k+\beta_k\nabla_{\operatorname{St}}\Psi(V^k)\rVert\to0 ∥ g k + β k ∇ St Ψ ( V k )∥ → 0 for some β → ∞ \beta\to\infty β → ∞ . Suppose Assumption 1 and 2 for Ψ \Psi Ψ and { V k } \{V^k\} { V k } are satisfied. Then there exists ω ∗ ∈ R R × K \omega^*\in\mathbb{R}^{R\times K} ω ∗ ∈ R R × K such that
g ∗ + Hess St Ψ ( V ∗ ) ω ∗ = 0. g^*+\operatorname{Hess}_{\operatorname{St}}\Psi(V^*)\omega^*=0. g ∗ + Hess St Ψ ( V ∗ ) ω ∗ = 0.
Lemma 4.11 (Corollary 3.5 of Stewart [39 ] ). Let { A t } \{A_t\} { A t } be a sequence of matrices converging to A A A as t → ∞ t\to\infty t → ∞ . Then a necessary and sufficient condition for
lim t → ∞ A t + = A + \lim_{t\to\infty}A_t^+=A^+ t → ∞ lim A t + = A + is that rank ( A t ) = rank ( A ) \operatorname{rank}(A_t)=\operatorname{rank}(A) rank ( A t ) = rank ( A ) for all sufficiently large t t t .
Proof of Proposition 4.10. For sufficiently large k ∈ N k\in\mathbb{N} k ∈ N , consider the tangent vectors v k = Log V ∗ ( V k ) ∈ T V ∗ St v_k=\operatorname{Log}_{V^*}(V^k)\in T_{V^*}\operatorname{St} v k = Log V ∗ ( V k ) ∈ T V ∗ St and the operators { B k } \{B^k\} { B k } as defined in (37) . Defining
ω k : = β k v k ∈ T V ∗ St , \omega_k:=\beta_kv_k\in T_{V^*}\operatorname{St}, ω k := β k v k ∈ T V ∗ St ,
we obtain by Taylor’s theorem (36) that β k ∇ St Ψ ( V k ) = P v k B k ω k \beta_k\nabla_{\operatorname{St}}\Psi(V^k)=P_{v_k}B^k\omega_k β k ∇ St Ψ ( V k ) = P v k B k ω k . Hence, g k + P v k B k ω k = g k + β k ∇ St Ψ ( V k ) g^k+P_{v_k}B^k\omega_k=g^k+\beta_k\nabla_{\operatorname{St}}\Psi(V^k) g k + P v k B k ω k = g k + β k ∇ St Ψ ( V k ) . Next, define
ω ^ k : = − ( P v k B k ) + g k , \widehat{\omega}_k:=-(P_{v_k}B^k)^+g^k, ω k := − ( P v k B k ) + g k ,
where ( ⋅ ) + (\cdot)^+ ( ⋅ ) + denotes the Moore–Penrose pseudoinverse. By definition of the pseudoinverse, P v k B k ω ^ k P_{v_k}B^k\widehat{\omega}_k P v k B k ω k is the orthogonal projection of − g k -g^k − g k onto the range of P v k B k P_{v_k}B^k P v k B k . Consequently,
∥ g k + P v k B k ω ^ k ∥ ≤ ∥ g k + P v k B k ω k ∥ = ∥ g k + β k ∇ St Ψ ( V k ) ∥ → 0. \lVert g^k+P_{v_k}B^k\widehat{\omega}_k\rVert\leq\lVert g^k+P_{v_k}B^k\omega_k\rVert=\lVert g^k+\beta_k\nabla_{\operatorname{St}}\Psi(V^k)\rVert\to0. ∥ g k + P v k B k ω k ∥ ≤ ∥ g k + P v k B k ω k ∥ = ∥ g k + β k ∇ St Ψ ( V k )∥ → 0.
By the constant rank condition and Lemma 4.11 we have that indeed ( P v k B k ) + → ( Hess St Ψ ( V ∗ ) ) + (P_{v_k}B^k)^+\to(\operatorname{Hess}_{\operatorname{St}}\Psi(V^*))^+ ( P v k B k ) + → ( Hess St Ψ ( V ∗ ) ) + . Combined with g k → g ∗ g^k\to g^* g k → g ∗ , this yields
ω ^ k → − ( Hess St Ψ ( V ∗ ) ) + g ∗ = : ω ∗ . \widehat{\omega}_k\to-(\operatorname{Hess}_{\operatorname{St}}\Psi(V^*))^+g^*=:\omega^*. ω k → − ( Hess St Ψ ( V ∗ ) ) + g ∗ =: ω ∗ .
Passing to the limit in g k + P v k B k ω ^ k → 0 g^k+P_{v_k}B^k\widehat{\omega}_k\to0 g k + P v k B k ω k → 0 finally gives g ∗ + Hess St Ψ ( V ∗ ) ω ∗ = 0 g^*+\operatorname{Hess}_{\operatorname{St}}\Psi(V^*)\omega^*=0 g ∗ + Hess St Ψ ( V ∗ ) ω ∗ = 0 . ■
Theorem 4.12. Let { U k } \{U^k\} { U k } be the sequence generated by (13) with arbitrary initialization. Set γ k = γ ~ / ( β k k + 1 ) \gamma_k=\widetilde{\gamma}/(\beta_k\sqrt{k}+1) γ k = γ / ( β k k + 1 ) with β k = C ( k + 1 ) p \beta_k=C(k+1)^p β k = C ( k + 1 ) p and p < 1 / 4 p<1/4 p < 1/4 . Define U ^ k = prox λ Ω k / β k ( U k ) \widehat{U}^k=\operatorname{prox}_{\lambda\Omega_k/\beta_k}(U^k) U k = prox λ Ω k / β k ( U k ) . There is a subsequence { τ ( k ) } \{\tau(k)\} { τ ( k )} such that the following holds:
U τ ( k ) → U ∗ U^{\tau(k)}\to U^* U τ ( k ) → U ∗
U ^ τ ( k ) → U ∗ \widehat{U}^{\tau(k)}\to U^* U τ ( k ) → U ∗
U ∗ ∈ N Ψ U^*\in N_\Psi U ∗ ∈ N Ψ
∃ g ^ k ∈ ∂ St ϕ ( U ^ k ) : g ^ τ ( k ) → g ∗ ∈ ∂ St ϕ ( U ∗ ) ∧ ∥ g ^ τ ( k ) + β τ ( k ) ∇ St Ψ ( U ^ τ ( k ) ) ∥ → 0 \exists\widehat{g}^k\in\partial_{\operatorname{St}}\phi(\widehat{U}^k):\widehat{g}^{\tau(k)}\to g^*\in\partial_{\operatorname{St}}\phi(U^*)\land\lVert\widehat{g}^{\tau(k)}+\beta^{\tau(k)}\nabla_{\operatorname{St}}\Psi(\widehat{U}^{\tau(k)})\rVert\to0 ∃ g k ∈ ∂ St ϕ ( U k ) : g τ ( k ) → g ∗ ∈ ∂ St ϕ ( U ∗ ) ∧ ∥ g τ ( k ) + β τ ( k ) ∇ St Ψ ( U τ ( k ) )∥ → 0 .
Suppose that Assumptions 1 and 2 hold for Ψ \Psi Ψ and the sequence { U ^ τ ( k ) } \{\widehat{U}^{\tau(k)}\} { U τ ( k ) } , respectively. If N Ψ N_\Psi N Ψ is a smooth submanifold in a neighborhood of U ∗ U^* U ∗ , then U ∗ U^* U ∗ is a stationary point of ϕ \phi ϕ on N Ψ N_\Psi N Ψ , i.e.
0 ∈ ∂ N Ψ ϕ ( U ∗ ) . 0\in\partial_{N_\Psi}\phi(U^*). 0 ∈ ∂ N Ψ ϕ ( U ∗ ) .
Proof. 1. and 3. follow from Corollary 4.4 . 2. follows from Theorem 4.7 and 4. from Corollary 4.8 and Lemma 4.9 . Since N Ψ \mathcal{N}_{\Psi} N Ψ is a smooth submanifold in a neighborhood of U ∗ U^{*} U ∗ , for every v ∈ T U ∗ N Ψ v \in T_{U^{*}}\mathcal{N}_{\Psi} v ∈ T U ∗ N Ψ there exists a smooth curve c : ( − ε , ε ) → N Ψ c \colon(-\varepsilon,\varepsilon) \to\mathcal{N}_{\Psi} c : ( − ε , ε ) → N Ψ such that c ( 0 ) = U ∗ c(0) = U^{*} c ( 0 ) = U ∗ and c ′ ( 0 ) = v c'(0) = v c ′ ( 0 ) = v . Since Ψ \Psi Ψ is twice continuously differentiable and ∇ S t Ψ ( c ( t ) ) = 0 \nabla\mathop{\mathrm{St}}\nolimits_{\Psi}(c(t)) = 0 ∇ St Ψ ( c ( t )) = 0 for all t t t in a neighborhood of zero, we have
Hess S t Ψ ( U ∗ ) v = Hess S t Ψ ( γ ( 0 ) ) γ ′ ( 0 ) = d d t ∇ S t Ψ ( γ ( t ) ) ∣ t = 0 = 0. \operatorname{Hess}_{\mathop{\mathrm{St}}\nolimits_{\Psi}}(U^{*})v = \operatorname{Hess}_{\mathop{\mathrm{St}}\nolimits_{\Psi}}(\gamma(0))\gamma'(0) = \left.\frac{d}{dt}\nabla_{\mathop{\mathrm{St}}\nolimits_{\Psi}}(\gamma(t))\right|_{t=0} = 0. Hess St Ψ ( U ∗ ) v = Hess St Ψ ( γ ( 0 )) γ ′ ( 0 ) = d t d ∇ St Ψ ( γ ( t )) t = 0 = 0.
Hence, T U ∗ N Ψ ⊆ ker ( Hess S t Ψ ( U ∗ ) ) T_{U^{*}}\mathcal{N}_{\Psi} \subseteq\ker(\operatorname{Hess}_{\mathop{\mathrm{St}}\nolimits_{\Psi}}(U^{*})) T U ∗ N Ψ ⊆ ker ( Hess St Ψ ( U ∗ )) . Applying Proposition 4.10 to the sequence { U ^ τ ( k ) } \{\widehat{U}^{\tau(k)}\} { U τ ( k ) } gives the existence of ω ∗ \omega^{*} ω ∗ such that g ∗ + Hess S t Ψ ( U ∗ ) ω ∗ = 0 g^{*} + \operatorname{Hess}_{\mathop{\mathrm{St}}\nolimits_{\Psi}}(U^{*})\omega^{*} = 0 g ∗ + Hess St Ψ ( U ∗ ) ω ∗ = 0 . Consequently,
g ∗ ∈ ran ( Hess S t Ψ ( U ∗ ) ) = ker ( Hess S t Ψ ( U ∗ ) ) ⊥ ⊂ ( T U ∗ N Ψ ) ⊥ . g^{*} \in\operatorname{ran}(\operatorname{Hess}_{\mathop{\mathrm{St}}\nolimits_{\Psi}}(U^{*})) = \ker(\operatorname{Hess}_{\mathop{\mathrm{St}}\nolimits_{\Psi}}(U^{*}))^{\perp} \subset(T_{U^{*}}\mathcal{N}_{\Psi})^{\perp}. g ∗ ∈ ran ( Hess St Ψ ( U ∗ )) = ker ( Hess St Ψ ( U ∗ ) ) ⊥ ⊂ ( T U ∗ N Ψ ) ⊥ .
Therefore, 0 ∈ ∂ N Ψ φ ( U ∗ ) 0 \in\partial_{\mathcal{N}_{\Psi}}\varphi(U^{*}) 0 ∈ ∂ N Ψ φ ( U ∗ ) .
Numerical Examples and Application
In the numerical experiments, we investigate two aspects. First, we consider an artificial example to illustrate the algorithmic behavior, verify the derived rates, and empirically study the choice of hyperparameters K K K , D D D , and γ ~ \widetilde{\gamma} γ . Second, we apply the algorithm to real data to obtain a diagonal frame decomposition of the Radon transform that promotes sparsity in the given data set. We then use this decomposition to recover images from noisy sinograms using regularizing filters.
Visualization of theoretical results
In the first numerical experiment, we consider a randomly generated positive diagonal matrix Σ ∈ R 10 × 10 \Sigma\in\mathbb{R}^{10 \times10} Σ ∈ R 10 × 10 and seek a diagonal frame decomposition ( U , V , D ) (U,V,D) ( U , V , D ) by first selecting D D D and solving problem (8) via Algorithm 1. The data set X X X consists of S = 50 S = 50 S = 50 synthetically generated vectors in R 10 \mathbb{R}^{10} R 10 , each of which is 2-sparse with respect to a tight wavelet frame W W W (i.e., the transformed data W T X W^{\mathsf{T}}X W T X has only two nonzero entries per column). The wavelet frame W W W is treated as unknown and is not used in the computations. The resulting data set and its transformation with respect to W W W is shown in Figure 1 c (top, middle). While ∥ X ∥ 1 ≈ 118 \lVert X\rVert_{1} \approx118 ∥ X ∥ 1 ≈ 118 , the sparsity measure with respect to the underlying wavelet frame is ∥ W T X ∥ 1 ≈ 85 \lVert W^{\mathsf{T}}X\rVert_{1} \approx85 ∥ W T X ∥ 1 ≈ 85 .
Figure 1. Numerical results for the synthetic data set. The plots illustrate the choice of the diagonal matrix D \mathbf{D} D , the convergence of the lower-level problem, the sparsity induced by the learned frame U ∗ \mathbf{U}^{*} U ∗ , and a comparison of the learned frame with the wavelet frame W \mathbf{W} W used to generate the sparse data.
We first set K = 15 K = 15 K = 15 and choose D D D according to the heuristic rule described in eq. (9) . The choice of D D D does not affect the algorithmic behavior, but determines the sparsity that can be achieved and the condition of V V V . Figure 1 a shows the diagonal entries of D D D together with those of Σ \Sigma Σ . The ten largest and ten smallest values of d d d relative to the corresponding singular values σ \sigma σ are displayed to assess the applicability of the Fan–Pall theorem. Since the largest values of d d d are smaller than the corresponding values of σ \sigma σ , the Fan–Pall conditions are violated, and hence no DFD exists for which both U U U and V V V are tight. Although C D C_{D} C D (defined in (6) ) is empty, we can still approximate frames using Algorithm 1, for which we know the performance guarantees worked out in the previous section. Throughout all experiments, we choose β K = ( 1 + k ) 0.23 \beta_{K} = (1 + k)^{0.23} β K = ( 1 + k ) 0.23 , γ K = γ ~ / ( β K k + 1 ) \gamma_{K} = \widetilde{\gamma}/(\beta_{K}\sqrt{k+1}) γ K = γ / ( β K k + 1 ) for γ ~ = 0.023 \widetilde{\gamma} = 0.023 γ = 0.023 unless stated otherwise. We initialize U 0 U^{0} U 0 by applying the polar retraction to a random Gaussian matrix.
The output frame U ∗ U^{*} U ∗ of the algorithm is shown in Figure 1 d (left), together with the wavelet frame W W W (right). Visually, the algorithm recovers the wavelet structures in which the data set is sparse. Moreover, the transformed data set ( U ∗ ) T X (U^{*})^{\mathsf{T}}X ( U ∗ ) T X is shown in Figure 1 c (bottom). It mostly exhibits the expected 2-sparse structure, both visually and quantitatively, with ∥ ( U ∗ ) T X ∥ 1 ≈ 84 \lVert(U^{*})^{\mathsf{T}}X\rVert_{1} \approx84 ∥( U ∗ ) T X ∥ 1 ≈ 84 which is even slightly smaller than the sparsity obtained with the original wavelet frame.
As detailed in Subsection 3.2, the choice of K K K is less critical than it may seem, provided that K K K is sufficiently large, since some columns of U \mathbf{U} U may vanish. In our example, the wavelet frame that generates the sparse data has 12 columns, so even for K = 15 K = 15 K = 15 , some columns of the learned frame are nearly zero. Figure 2 shows the loss ∥ U k X ∥ 1 \lVert\mathbf{U}^{k}\mathbf{X}\rVert_{1} ∥ U k X ∥ 1 (left) and the condition number of V k = Σ − 1 U k D \mathbf{V}^{k} = \boldsymbol{\Sigma}^{-1}\mathbf{U}^{k}\mathbf{D} V k = Σ − 1 U k D (right) for different choices of K K K , with D \mathbf{D} D chosen according to (9) . The same level of sparsity is achieved for all choices of K K K , although K = 25 K = 25 K = 25 requires more iterations or a larger step size. However, K K K has a substantial impact on the condition number of V k \mathbf{V}^{k} V k . Following the relaxation introduced in § 3 , the goal is therefore to obtain both a sparse representation U T X \mathbf{U}^{\mathsf{T}}\mathbf{X} U T X and frame bounds of V \mathbf{V} V close to 1. Since cond ( Σ ) ≈ 13.6 \operatorname{cond}(\boldsymbol{\Sigma}) \approx13.6 cond ( Σ ) ≈ 13.6 in this example and V \mathbf{V} V cannot be tight for the chosen D \mathbf{D} D , sufficiently large K K K yields condition numbers around 3.6 to 4, whereas small K K K results in condition numbers close to that of Σ \boldsymbol{\Sigma} Σ , reducing the stability advantage of the DFD.
Figure 2. Sparsity loss ∥ U k X ∥ 1 \lVert\mathbf{U}^{k}\mathbf{X}\rVert_{1} ∥ U k X ∥ 1 (left) and condition number of V k = Σ − 1 U k D \mathbf{V}^{k} = \boldsymbol{\Sigma}^{-1}\mathbf{U}^{k}\mathbf{D} V k = Σ − 1 U k D (right) for different choices of K K K as a function of the iteration number for the synthetic example.
Another observation concerns the sensitivity to the initial step size γ ~ \widetilde{\gamma} γ . In Figure 3 we set K = 10 K = 10 K = 10 and D = Σ \mathbf{D} = \boldsymbol{\Sigma} D = Σ since the following observations are independent of the choice of D \mathbf{D} D . Varying only the step size constant γ ~ \widetilde{\gamma} γ leads to substantial differences in the convergence of both the sparsity loss ∥ U k X ∥ 1 \lVert\mathbf{U}^{k}\mathbf{X}\rVert_{1} ∥ U k X ∥ 1 and the condition number of V k \mathbf{V}^{k} V k . If the step size is too large, both the sparsity loss and the condition number remain high for a large number of iterations and then decrease rapidly as the algorithm approaches a good stationary point. If the step size is too small, convergence is excessively slow, and the desired sparsity may not be reached within a practical number of iterations. Thus, a suitable choice of γ ~ \tilde{\gamma} γ ~ is crucial and also depends strongly on the condition numbers of Σ \boldsymbol{\Sigma} Σ and D \mathbf{D} D .
Figure 3. Sparsity loss ∥ U k X ∥ 1 \lVert\mathbf{U}^{k}\mathbf{X}\rVert_{1} ∥ U k X ∥ 1 (left) and condition number of V k = Σ − 1 U k D \mathbf{V}^{k} = \boldsymbol{\Sigma}^{-1}\mathbf{U}^{k}\mathbf{D} V k = Σ − 1 U k D (right) for different step size constants γ ~ \tilde{\gamma} γ ~ for the synthetic example.
Finally, the choice of D \mathbf{D} D has a clear influence on the resulting decomposition. In Figure 4 , we illustrate the convergence behavior for three choices: the Fan–Pall choice from (10) , the data-aware heuristic choice from (9) , and D = Σ \mathbf{D} = \boldsymbol{\Sigma} D = Σ . The data-aware choice achieves a lower sparsity loss than the Fan–Pall choice, but results in a larger condition number for V k \mathbf{V}^{k} V k . In the Fan–Pall case, the condition number converges to approximately 2, whereas in the data-aware case it stabilizes at around 4. The choice D = Σ \mathbf{D} = \boldsymbol{\Sigma} D = Σ exhibits a behavior similar to the Fan–Pall case. Although sparsity is an important objective, a large condition number can lead to unstable reconstruction methods, and thus limit the practical usefulness of the resulting decomposition. Note that the initial plateau in the Fan–Pall and D = Σ \mathbf{D} = \boldsymbol{\Sigma} D = Σ cases is due to the choice of the initial step size. We use the same γ ~ = 0.023 \tilde{\gamma} = 0.023 γ ~ = 0.023 for all choices of D \mathbf{D} D , while the data-aware choice results in smaller gradients and thus smaller effective updates in the algorithm.
Figure 4. Sparsity loss ∥ U k x ∥ 1 \lVert\mathbf{U}^{k}\mathbf{x}\rVert_{1} ∥ U k x ∥ 1 (left) and condition number of V k = Σ − 1 U k D \mathbf{V}^{k}=\Sigma^{-1}\mathbf{U}^{k}\mathbf{D} V k = Σ − 1 U k D (right) for different choices of D \mathbf{D} D as a function of the iteration number for the synthetic example. In the Fan–Pall case D \mathbf{D} D is chosen according to (10) , in the data-aware case according to (9) , and in the third case we set D = Σ \mathbf{D}=\Sigma D = Σ .
Filter-regularization with Learned DFD
In the second numerical experiment, we consider a discretization of the two-dimensional Radon transform for the matrix A \mathbf{A} A . The Radon transform maps a compactly supported square-integrable function to its line integrals over affine lines [32 ] . It provides the mathematical foundation for computed tomography (CT) [33 ] and is widely used in imaging applications [28 , 45 ] . Its discretized version A \mathbf{A} A maps a vectorized image x ∈ R m 1 ⋅ m 2 \mathbf{x}\in\mathbb{R}^{m_{1}\cdot m_{2}} x ∈ R m 1 ⋅ m 2 to a vectorized observation (sinogram) y ∈ R n 1 ⋅ n 2 \mathbf{y}\in\mathbb{R}^{n_{1}\cdot n_{2}} y ∈ R n 1 ⋅ n 2 . The inversion of the Radon transform is ill-posed, meaning that small perturbations in the sinogram can lead to large reconstruction errors. This makes regularization essential for obtaining stable reconstructions from noisy data.
Learning a DFD for large-scale problems can be computationally demanding, as it requires the repeated computation of SVDs of high-dimensional matrices. However, this learning step only has to be performed once for a given operator and training data set. Once the DFD has been computed, reconstructing an image from a sinogram requires only two matrix multiplications and the evaluation of the corresponding filter, making reconstruction computationally inexpensive. To keep the computational cost manageable, we conduct the numerical experiments using images of size 20 × 20 20\times20 20 × 20 , corresponding to 400 pixels, and sinograms of size 20 × 30 20\times30 20 × 30 . Although this resolution is relatively low for practical image reconstruction, it provides a controlled setting for evaluating the reconstruction performance and error characteristics of the proposed method.
We first compute the SVD of A \mathbf{A} A and truncate the smallest singular values, whose contribution to the filtered reconstructions is negligible over the considered range of noise levels. We then learn a DFD for the slightly truncated operator A t = Q Σ W ⊤ \mathbf{A}_{t}=\mathbf{Q}\Sigma\mathbf{W}^{\top} A t = Q Σ W ⊤ with σ 1 ≥ σ 2 ≥ ⋯ ≥ ε > 0 \sigma_{1}\geq\sigma_{2}\geq\cdots\geq\varepsilon>0 σ 1 ≥ σ 2 ≥ ⋯ ≥ ε > 0 . This truncation substantially reduces the computational cost of the learning algorithm and allows for larger step sizes, while having only a minor effect on the resulting filtered reconstructions. We choose K = 2 R K=2R K = 2 R , where R R R is the rank of A t \mathbf{A}_{t} A t , and we choose D \mathbf{D} D according to (10) to satisfy the Fan-Pall Theorem 3.2. We initialize U 0 \mathbf{U}^{0} U 0 by applying the polar retraction to a random Gaussian matrix and we use β k = ( 1 + k ) 0.23 \beta_{k}=(1+k)^{0.23} β k = ( 1 + k ) 0.23 and γ k = γ ~ / ( β k k + 1 ) \gamma_{k}=\widetilde{\gamma}/(\beta_{k}\sqrt{k+1}) γ k = γ / ( β k k + 1 ) with γ ~ ≈ ∥ U 0 ∥ / ∥ β 0 ∇ S t Ψ ( U 0 ) + ∂ S t ϕ ( U 0 ) ∥ \widetilde{\gamma}\approx\lVert\mathbf{U}^{0}\rVert/\lVert\beta_{0}\nabla_{\mathbf{St}}\Psi(\mathbf{U}^{0})+\partial_{\mathrm{St}}\phi(\mathbf{U}^{0})\rVert γ ≈ ∥ U 0 ∥ / ∥ β 0 ∇ St Ψ ( U 0 ) + ∂ St ϕ ( U 0 )∥ .
To learn a tight DFD, we use S = 500 S=500 S = 500 real lung CT images as training data [36 ] . Since we do not have a reliable a priori rule for choosing the initial step size or a suitable stopping criterion, we choose the initial step size such that the algorithm exhibits a rapid decay in the sparsity loss and the condition number of V k \mathbf{V}^{k} V k within a reasonable number of iterations (k ≤ 50000 k\leq50000 k ≤ 50000 ). The influence of the initial step size on the convergence behavior and the resulting frame is similar to that observed in the artificial experiments shown in Figure 3 . Then, we selected the last iterate U ∗ = U k U^\ast= U^k U ∗ = U k after 50000 iterations.
Using the learned frames U ∗ U^\ast U ∗ and V ∗ = Σ − 1 U ∗ D V^\ast= \Sigma^{-1}U^\ast D V ∗ = Σ − 1 U ∗ D , we construct a DFD for A t A_t A t according to Lemma 3.1 . We then apply the filter reconstruction (2) with the soft-thresholding filter f α f_\alpha f α defined in (3) to reconstruct images from noisy sinograms y δ y^\delta y δ . More precisely, we compute
R α D F D ( y δ ) = W T U ∗ f α ( D + , ( V ∗ ) T Q T y δ ) . (38) \mathcal{R}^{\mathrm{DFD}}_\alpha(y^\delta) = \mathbf{W}^{\mathsf{T}} U^\ast f_\alpha(D^+, (V^\ast)^{\mathsf{T}} \mathbf{Q}^{\mathsf{T}} y^\delta). \tag*{(38)} R α DFD ( y δ ) = W T U ∗ f α ( D + , ( V ∗ ) T Q T y δ ) . (38)
The parameter α \alpha α is chosen (unrealistically) to minimize the reconstruction error to the ground truth.
To evaluate reconstruction quality, we use 50 independent test images and compute the mean relative ℓ 2 \ell^2 ℓ 2 -error, peak signal-to-noise ratio (PSNR), and structural similarity index (SSIM) over the test set with respect to the ground truth. We generate noisy sinograms by adding Gaussian noise at different noise levels. For each noise level and reconstruction method, the regularization parameter α \alpha α is chosen to yield the best reconstruction quality. We compare the results with those obtained using the filtered SVD reconstruction
R α S V D ( y δ ) = W T f α ( Σ + , Q T y δ ) . (39) \mathcal{R}^{\mathrm{SVD}}_\alpha(y^\delta) = \mathbf{W}^{\mathsf{T}} f_\alpha(\Sigma^+, \mathbf{Q}^{\mathsf{T}}y^\delta). \tag*{(39)} R α SVD ( y δ ) = W T f α ( Σ + , Q T y δ ) . (39)
In Figure 5 we show the reconstruction quality achieved by filtered SVD and filtered DFD in different metrics. The filtered DFD with the data-aware learned frame consistently outperforms the filtered SVD for the considered noise levels and evaluation metrics, which demonstrates the benefit of adapting the frame to the training data. The performance of the learned DFD could potentially be further improved by increasing the number of training images and the number of iterations used in the learning algorithm.
Figure 5. Comparison of the reconstruction quality measured by the relative ℓ 2 \ell^2 ℓ 2 -error, PSNR, and SSIM. The x x x -axis displays the percentage of added Gaussian noise. For each noise level and regularization method, the parameter α \alpha α is chosen to achieve the best possible reconstruction. The reported values are the mean over 50 test images.
To illustrate the structure of the learned DFD, we visualize the first 100 left and right frame elements in Figure 6 . The left frame elements are reshaped into 20 × 20 20 \times20 20 × 20 images, whereas the right frame elements are reshaped into 20 × 30 20 \times30 20 × 30 sinograms. All elements are displayed using the same grayscale scale, with zero corresponding to middle gray, negative values shown in darker shades, and positive values in lighter shades.
Figure 6. First 100 left DFD elements (U U U , left) and First 100 right DFD elements (V V V , right), arranged in a 10 × 10 10 \times10 10 × 10 grid. Each element is reshaped into a 20 × 20 20 \times20 20 × 20 image or a 20 × 30 20 \times30 20 × 30 sinogram, respectively. The grayscale is centered at zero, with negative values shown in darker shades and positive values in lighter shades.
Conclusion
In this work, we introduced a data-aware approach for constructing diagonal frame decompositions whose frames in the signal space are tight and promote sparse representations of the given data. We formulated the construction as a bilevel optimization problem over the Stiefel manifold, where the nonconvex geometry of the feasible set leads to a nonconvex bilevel problem.
To address this problem, we proposed a penalized subgradient method and established convergence results in a general setting. Under suitable assumptions, we showed that the iterates converge to stationary points at both optimization levels and the derived convergence rates in terms of appropriate stationary measures. The numerical experiments confirm the theoretical behavior of the proposed method and demonstrate its practical ability to construct data-aware DFDs. In particular, the resulting decompositions provide effective regularization tools when applied to inverse problems, where they yield competitive reconstruction results.
Future work will include investigating other sparsity-promoting data terms and their practical performance in the construction of data-aware DFDs. From a theoretical perspective, an interesting direction is to extend convergence analysis towards near-stationary guaranties analogous to those established for nonconvex bilevel optimization in the Euclidean setting [11 , 16 ] . On the computational side, parallelization and more efficient retractions on the Stiefel manifold could further improve the practical performance of the proposed method.
Declaration of generative AI and AI-assisted technologies in the manuscript preparation process
During the preparation of this work, the authors used ChatGPT for language editing, brainstorming, and writing and debugging Python code. After using this tool, the authors reviewed and edited the content as needed and take full responsibility for the content of the published article.
Acknowledgements
This research was funded in whole or in part by the Austrian Science Fund (FWF) J4954-N. For the purpose of open access, the author has applied a CC BY public copyright license to any Author Accepted Manuscript (AAM) version arising from this submission.
Appendices
Tools on the Stiefel manifold
In this appendix we collect some elements from manifold theory which are needed for our analysis. See [7 ] for a general introduction to Riemannian optimization.
Basic notions
For R ≤ K R \le K R ≤ K , we let R K × R \mathbb{R}^{K \times R} R K × R be the Euclidean vector space with inner product ⟨ A , B ⟩ = tr ( A T B ) \langle A,B\rangle= \operatorname{tr}(A^{\mathsf{T}}B) ⟨ A , B ⟩ = tr ( A T B ) , and corresponding norm ∥ A ∥ F : = ⟨ A , A ⟩ \lVert A\rVert_{\mathrm{F}} := \sqrt{\langle A,A\rangle} ∥ A ∥ F := ⟨ A , A ⟩ , the Frobenius norm. The Stiefel manifold on R K × R \mathbb{R}^{K \times R} R K × R is
St ( K , R ) : = { B ∈ R K × R ∣ B T B = Id R } . \operatorname{St}(K,R) := \{B \in\mathbb{R}^{K \times R} \mid B^{\mathsf{T}}B = \operatorname{Id}_{R}\}. St ( K , R ) := { B ∈ R K × R ∣ B T B = Id R } .
We interpret this set as an embedded submanifold of R K × R \mathbb{R}^{K \times R} R K × R via the locally defining function h : R K × R → Sym ( R ) h:\mathbb{R}^{K \times R} \to\operatorname{Sym}(R) h : R K × R → Sym ( R ) , A ↦ h ( A ) = A T A − Id R A \mapsto h(A) = A^{\mathsf{T}}A - \operatorname{Id}_{R} A ↦ h ( A ) = A T A − Id R . Indeed, h − 1 ( 0 ) = St ( K , R ) h^{-1}(0) = \operatorname{St}(K,R) h − 1 ( 0 ) = St ( K , R ) and D h ( A ) [ V ] = Q Dh(A)[V] = Q D h ( A ) [ V ] = Q for V = 1 2 A Q V = \frac{1}{2}AQ V = 2 1 A Q and Q ∈ Sym ( R ) Q \in\operatorname{Sym}(R) Q ∈ Sym ( R ) is a surjective mapping. To shorten the notation we often omit the dimension and write St \operatorname{St} St . The tangent space of the Stiefel manifold at U ∈ St ( K , R ) U \in\operatorname{St}(K,R) U ∈ St ( K , R ) is accordingly defined as
T A St ( K , R ) = ker D h ( A ) = { V ∈ R K × R ∣ V T A + A T V = 0 } . T_{A}\operatorname{St}(K,R) = \ker Dh(A) = \{V \in\mathbb{R}^{K \times R} \mid V^{\mathsf{T}}A + A^{\mathsf{T}}V = 0\}. T A St ( K , R ) = ker D h ( A ) = { V ∈ R K × R ∣ V T A + A T V = 0 } .
This is an Euclidean vector space inheriting the scalar product of its ambient space R K × R \mathbb{R}^{K \times R} R K × R . For a general embedded submanifold M \mathcal{M} M , the product set T M = { ( x , ξ ) ∣ x ∈ M , ξ ∈ T x M } T\mathcal{M} = \{(x,\xi) \mid x \in\mathcal{M},\ \xi\in T_x\mathcal{M}\} T M = {( x , ξ ) ∣ x ∈ M , ξ ∈ T x M } is its tangent bundle .
Retractions
A retraction on a manifold M \mathcal{M} M is a smooth map
Retr : T M → M , ( A , ξ ) ↦ Retr A ( ξ ) \operatorname{Retr}:T\mathcal{M} \to\mathcal{M},\qquad(A,\xi) \mapsto\operatorname{Retr}_{A}(\xi) Retr : T M → M , ( A , ξ ) ↦ Retr A ( ξ )
such that each curve c ( t ) = Retr A ( t ξ ) c(t) = \operatorname{Retr}_{A}(t\xi) c ( t ) = Retr A ( t ξ ) satisfies c ( 0 ) = A c(0) = A c ( 0 ) = A and c ′ ( 0 ) = ξ c'(0) = \xi c ′ ( 0 ) = ξ . There are multiple ways to define retractions on a given manifold, and the practical choice is usually guided by the geometric and algebraic structure of M \mathcal{M} M . For the Stiefel manifold M = St ( K , R ) \mathcal{M} = \operatorname{St}(K,R) M = St ( K , R ) various efficiently computable retractions are known. A common choice is the Q Q Q -factor retraction: Retr A ( ξ ) = Q \operatorname{Retr}_{A}(\xi) = Q Retr A ( ξ ) = Q , where Q R = X + ξ QR = X + \xi QR = X + ξ is a thin QR decomposition. A particular efficient retraction, also used in this paper, is the polar retraction
Retr A ( ξ ) = ( A + ξ ) ( Id R + ξ T ξ ) − 1 / 2 . \operatorname{Retr}_{A}(\xi) = (A+\xi)(\operatorname{Id}_{R}+\xi^{\mathsf{T}}\xi)^{-1/2}. Retr A ( ξ ) = ( A + ξ ) ( Id R + ξ T ξ ) − 1/2 .
It can be efficiently computed through the SVD of A + ξ A+\xi A + ξ . To wit, if A + ξ = Z Λ W T A+\xi= Z\Lambda W^{\mathsf{T}} A + ξ = Z Λ W T , then Retr A ( ξ ) = Z W T \operatorname{Retr}_{A}(\xi) = ZW^{\mathsf{T}} Retr A ( ξ ) = Z W T . An important property of the polar retraction is its nonexpansiveness.
Lemma A.1 (Lemma 1, [31 ] ). Let U ∈ St ( K , R ) U \in\operatorname{St}(K,R) U ∈ St ( K , R ) and let ξ ∈ T U St \xi\in T_U\operatorname{St} ξ ∈ T U St . Define U + : = U + ξ U_+ := U + \xi U + := U + ξ . Then the polar decomposition based retraction (2.4) satisfies
Retr U ( ξ ) = U + ( U + T U + ) − 1 / 2 = Proj St ( U + ) . \operatorname{Retr}_U(\xi) = U_+\left(U_+^\mathsf{T}U_+\right)^{-1/2} = \operatorname{Proj}_{\operatorname{St}}(U_+). Retr U ( ξ ) = U + ( U + T U + ) − 1/2 = Proj St ( U + ) . Moreover,
∥ Retr U ( ξ ) − U ‾ ∥ F ≤ ∥ U + − U ‾ ∥ F ∀ U ‾ ∈ St ( K , R ) . (40) \lVert\operatorname{Retr}_U(\xi) - \overline{U}\rVert_F \le\lVert U_+ - \overline{U}\rVert_F \qquad\forall\overline{U} \in\operatorname{St}(K,R). \tag*{(40)} ∥ Retr U ( ξ ) − U ∥ F ≤ ∥ U + − U ∥ F ∀ U ∈ St ( K , R ) . (40)
Derivatives
For a smooth map F : M → M ′ F:\mathcal{M} \to\mathcal{M}' F : M → M ′ between manifolds, its differential at A ∈ M A \in\mathcal{M} A ∈ M is the linear map D F ( A ) : T A M → T F ( A ) M ′ DF(A):T_A\mathcal{M} \to T_{F(A)}\mathcal{M}' D F ( A ) : T A M → T F ( A ) M ′ defined by
D F ( A ) [ B ] = d d t F ( c ( t ) ) ∣ t = 0 , DF(A)[B] = \left.\frac{\mathrm{d}}{\mathrm{d}t}F(c(t))\right|_{t=0}, D F ( A ) [ B ] = d t d F ( c ( t )) t = 0 ,
where c c c is any smooth curve on M \mathcal{M} M satisfying c ( 0 ) = A c(0)=A c ( 0 ) = A and c ′ ( 0 ) = B c'(0)=B c ′ ( 0 ) = B ; see [7 Def. 3.34] . For a smooth function f : M → R f:\mathcal{M} \to\mathbb{R} f : M → R , the Riemannian gradient ∇ M f ( A ) ∈ T A M \nabla_{\mathcal{M}}f(A) \in T_A\mathcal{M} ∇ M f ( A ) ∈ T A M is the unique tangent vector satisfying D f ( A ) [ B ] = ⟨ B , ∇ M f ( A ) ⟩ A Df(A)[B] = \langle B,\nabla_{\mathcal{M}}f(A)\rangle_A D f ( A ) [ B ] = ⟨ B , ∇ M f ( A ) ⟩ A for all B ∈ T A M B \in T_A\mathcal{M} B ∈ T A M ; see [7 Def. 3.58] . The Riemannian Hessian is the covariant derivative of the Riemannian gradient and can be viewed as a linear map
Hess M f ( A ) : T A M → T A M . \operatorname{Hess}_{\mathcal{M}}f(A):T_A\mathcal{M} \to T_A\mathcal{M}. Hess M f ( A ) : T A M → T A M .
Since the Stiefel manifold is an embedded submanifold of the Euclidean space R K × R \mathbb{R}^{K \times R} R K × R , Riemannian derivatives can be expressed in terms of Euclidean derivatives and the orthogonal projection onto the tangent space. The orthogonal projection onto the tangent space T A St ( K , R ) T_A\operatorname{St}(K,R) T A St ( K , R ) is the operator such that V − Proj T A St ( V ) ∈ T A St ( K , R ) ⊥ V-\operatorname{Proj}_{T_A\operatorname{St}}(V) \in T_A\operatorname{St}(K,R)^\perp V − Proj T A St ( V ) ∈ T A St ( K , R ) ⊥ . Using the Euclidean structure of the embedding space, one can easily compute that
Proj T A St ( V ) = V − A A T V + V T A 2 = ( I d − A A T ) V + A A T V − V T A 2 . \operatorname{Proj}_{T_A\operatorname{St}}(V) = V-A\frac{A^\mathsf{T}V+V^\mathsf{T}A}{2} = \left(I_d-AA^\mathsf{T}\right)V+A\frac{A^\mathsf{T}V-V^\mathsf{T}A}{2}. Proj T A St ( V ) = V − A 2 A T V + V T A = ( I d − A A T ) V + A 2 A T V − V T A .
The projector yields a convenient formula for the Riemannian gradient of a differentiable function f : St → R f:\operatorname{St} \to\mathbb{R} f : St → R in terms of a differentiable extension f ˉ : R K × R → R \bar{f}:\mathbb{R}^{K \times R} \to\mathbb{R} f ˉ : R K × R → R by [7 Proposition 3.61]
∇ St f ( A ) = Proj T A St ( ∇ f ˉ ( A ) ) = ∇ f ˉ ( A ) − A A T ∇ f ˉ ( A ) + ∇ f ˉ ( A ) T A 2 . \nabla_{\operatorname{St}}f(A) = \operatorname{Proj}_{T_A\operatorname{St}}(\nabla\bar{f}(A)) = \nabla\bar{f}(A)-A\frac{A^\mathsf{T}\nabla\bar{f}(A)+\nabla\bar{f}(A)^\mathsf{T}A}{2}. ∇ St f ( A ) = Proj T A St ( ∇ f ˉ ( A )) = ∇ f ˉ ( A ) − A 2 A T ∇ f ˉ ( A ) + ∇ f ˉ ( A ) T A .
If f f f is smooth enough the Riemannian Hessian Hess St f ( A ) \operatorname{Hess}_{\operatorname{St}}f(A) Hess St f ( A ) is a self-adjoint linear map on T A St T_A\operatorname{St} T A St given by
Hess St f ( A ) [ B ] = Proj T A St ( Hess St f ˉ ( A ) [ B ] ) + P B ( Proj T A St ⊥ ( ∇ f ˉ ( A ) ) ) . \operatorname{Hess}_{\operatorname{St}}f(A)[B] = \operatorname{Proj}_{T_A\operatorname{St}}\left(\operatorname{Hess}_{\operatorname{St}}\bar{f}(A)[B]\right) + \mathcal{P}_B\left(\operatorname{Proj}_{T_A\operatorname{St}}^\perp(\nabla\bar{f}(A))\right). Hess St f ( A ) [ B ] = Proj T A St ( Hess St f ˉ ( A ) [ B ] ) + P B ( Proj T A St ⊥ ( ∇ f ˉ ( A )) ) .
where P B \mathcal{P}_B P B is the differential of A ↦ Proj T A St A \mapsto\operatorname{Proj}_{T_A\operatorname{St}} A ↦ Proj T A St at A A A along B B B and Proj T A St ⊥ = I d − Proj T A St \operatorname{Proj}_{T_A\operatorname{St}}^\perp=I_d-\operatorname{Proj}_{T_A\operatorname{St}} Proj T A St ⊥ = I d − Proj T A St . Since we use only first-order methods, the Hessian serves only as a theoretical tool, and we do not need to compute it explicitly in our experiments.
For a convex function g ˉ : R K × R → R \bar{g}:\mathbb{R}^{K \times R} \to\mathbb{R} g ˉ : R K × R → R , the Riemannian (Clarke) subdifferential ∂ St g ( A ) \partial_{\operatorname{St}}g(A) ∂ St g ( A ) of the restriction g = g ˉ ∣ St g=\bar{g}|_{\operatorname{St}} g = g ˉ ∣ St is also given by the projector [44 Theorem 5.1]
∂ St g ( A ) = Proj T A St ( ∂ g ˉ ( A ) ) ∀ A ∈ St ( K , R ) . \partial_{\operatorname{St}}g(A) = \operatorname{Proj}_{T_A\operatorname{St}}\left(\partial\bar{g}(A)\right) \qquad\forall A \in\operatorname{St}(K,R). ∂ St g ( A ) = Proj T A St ( ∂ g ˉ ( A ) ) ∀ A ∈ St ( K , R ) .
In particular, although g g g is generally no longer convex, any Euclidean subgradient g ′ ( A ) ∈ ∂ g ˉ ( A ) g'(A) \in\partial\bar{g}(A) g ′ ( A ) ∈ ∂ g ˉ ( A ) gives rise to a Riemannian subgradient through the projection operator Proj T A St ( g ′ ( A ) ) \operatorname{Proj}_{T_A\operatorname{St}}(g'(A)) Proj T A St ( g ′ ( A )) .
Parallel Transport and Taylor expansion
In our optimality analysis, we make use of the Taylor expansion on the Stiefel manifold. We briefly introduce the basic tools required to apply it; for a detailed treatment, we refer to [7 Chap. 5, Chap. 10] . Notably, this tool is not specific to the Stiefel manifold but applies to arbitrary Riemannian submanifolds.
The so-called parallel transport is a tool that allows us to transport a tangent vector ξ ∈ T A S t \xi\in T_A\mathrm{St} ξ ∈ T A St from A \mathbf{A} A to another point B ∈ S t \mathbf{B} \in\mathrm{St} B ∈ St . Given a smooth curve c : I → S t c:I \to\mathrm{St} c : I → St with c ( t 0 ) = A c(t_0)=\mathbf{A} c ( t 0 ) = A and c ( t 1 ) = B c(t_1)=\mathbf{B} c ( t 1 ) = B , there exists a unique smooth map (vector field on c c c ) Z : I → T S t Z:I \to T\mathrm{St} Z : I → T St such that Z ( t ) ∈ T c ( t ) S t Z(t) \in T_{c(t)}\mathrm{St} Z ( t ) ∈ T c ( t ) St for all t ∈ I t \in I t ∈ I , Z ( t 0 ) = ξ Z(t_0)=\xi Z ( t 0 ) = ξ , and Proj c ( t ) ( d d t Z ( t ) ) = 0 \operatorname{Proj}_{c(t)}\left(\frac{\mathrm{d}}{\mathrm{d}t}Z(t)\right)=0 Proj c ( t ) ( d t d Z ( t ) ) = 0 . Here, d d t Z \frac{\mathrm{d}}{\mathrm{d}t}Z d t d Z denotes the classical derivative of Z Z Z in the embedding space. A vector field Z Z Z satisfying these requirements is said to be parallel. The parallel transport of tangent vectors at c ( t 0 ) c(t_0) c ( t 0 ) to the tangent space at c ( t 1 ) c(t_1) c ( t 1 ) along c c c is the map
P T t 1 ← t 0 c : T c ( t 0 ) S t → T c ( t 1 ) S t \mathrm{PT}^{c}_{t_1\leftarrow t_0}:T_{c(t_0)}\mathrm{St}\to T_{c(t_1)}\mathrm{St} PT t 1 ← t 0 c : T c ( t 0 ) St → T c ( t 1 ) St
defined by P T t 1 ← t 0 c ( ξ ) = Z ( t 1 ) \mathrm{PT}^{c}_{t_1\leftarrow t_0}(\xi)=Z(t_1) PT t 1 ← t 0 c ( ξ ) = Z ( t 1 ) . In the case of the Stiefel manifold, parallel transport is a linear isometry and P T t ← t 0 c \mathrm{PT}^{c}_{t\leftarrow t_0} PT t ← t 0 c is the identity.
To obtain a second-order Taylor expansion, a particular curve between points is used, namely the geodesic generated by the so-called exponential map. For every ( A , ξ ) ∈ T S t (\mathbf{A},\xi)\in T\mathrm{St} ( A , ξ ) ∈ T St there exists a unique maximal geodesic γ : I → S t \gamma:I\to\mathrm{St} γ : I → St with γ ( 0 ) = A \gamma(0)=\mathbf{A} γ ( 0 ) = A and γ ′ ( 0 ) = ξ \gamma'(0)=\xi γ ′ ( 0 ) = ξ , where maximal means that the interval I I I is as large as possible. If I I I contains [ 0 , 1 ] [0,1] [ 0 , 1 ] the exponential map is defined by
Exp ( A , ξ ) = Exp A ( ξ ) = γ ( 1 ) . \operatorname{Exp}(\mathbf{A},\xi)=\operatorname{Exp}_{\mathbf{A}}(\xi)=\gamma(1). Exp ( A , ξ ) = Exp A ( ξ ) = γ ( 1 ) .
For B \mathbf{B} B sufficiently close to A \mathbf{A} A , there exists a tangent vector ξ ∈ T A S t \xi\in T_{\mathbf{A}}\mathrm{St} ξ ∈ T A St such that B = Exp A ( ξ ) \mathbf{B}=\operatorname{Exp}_{\mathbf{A}}(\xi) B = Exp A ( ξ ) . This tangent vector is denoted by the logarithmic map
Log A ( B ) = ξ . \operatorname{Log}_{\mathbf{A}}(\mathbf{B})=\xi. Log A ( B ) = ξ .
Now consider the geodesic c ( t ) = Exp A ( t ξ ) c(t)=\operatorname{Exp}_{\mathbf{A}}(t\xi) c ( t ) = Exp A ( t ξ ) between A \mathbf{A} A and B \mathbf{B} B . We write P t ξ = P T t ← 0 c P_{t\xi}=\mathrm{PT}^{c}_{t\leftarrow0} P t ξ = PT t ← 0 c . Then, if f f f is at least twice continuously differentiable, the following Taylor expansion of the Riemannian gradient holds:
P t ξ − 1 ∇ S t f ( c ( t ) ) = ∇ S t f ( A ) + ∫ 0 t ( P τ ξ − 1 ∘ Hess S t f ( c ( τ ) ) ∘ P τ ξ ) [ ξ ] d τ . P_{t\xi}^{-1}\nabla_{\mathrm{St}}f(c(t))=\nabla_{\mathrm{St}}f(\mathbf{A})+\int_0^t\left(P_{\tau\xi}^{-1}\circ\operatorname{Hess}_{\mathrm{St}}f(c(\tau))\circ P_{\tau\xi}\right)[\xi]\,\mathrm{d}\tau. P t ξ − 1 ∇ St f ( c ( t )) = ∇ St f ( A ) + ∫ 0 t ( P τ ξ − 1 ∘ Hess St f ( c ( τ )) ∘ P τ ξ ) [ ξ ] d τ .
Weakly convex functions
A function f : U ⊂ R n → R f:U\subset\mathbb{R}^n\to\mathbb{R} f : U ⊂ R n → R is called τ \tau τ -weakly convex if
x ↦ f ( x ) + τ 2 ∥ x ∥ 2 x\mapsto f(x)+\frac{\tau}{2}\lVert x\rVert^2 x ↦ f ( x ) + 2 τ ∥ x ∥ 2
is convex for some τ ≥ 0 \tau\geq0 τ ≥ 0 . Thus, weak convexity allows for a controlled deviation from convexity and includes convex functions as the special case τ = 0 \tau=0 τ = 0 . If f f f is differentiable and τ \tau τ -weakly convex it satisfies the gradient inequality
f ( x ^ ) ≥ f ( x ) + ⟨ ∇ f ( x ) , x ^ − x ⟩ − τ 2 ∥ x ^ − x ∥ 2 ∀ x ^ , x ∈ U . (41) f(\hat{x})\geq f(x)+\langle\nabla f(x),\hat{x}-x\rangle-\frac{\tau}{2}\lVert\hat{x}-x\rVert^2\qquad\forall\hat{x},x\in U. \tag*{(41)} f ( x ^ ) ≥ f ( x ) + ⟨ ∇ f ( x ) , x ^ − x ⟩ − 2 τ ∥ x ^ − x ∥ 2 ∀ x ^ , x ∈ U . (41)