PaperlayerView exact revision on arXiv

Source-linked AI summary

Computing Data-Aware Diagonal Frame Decompositions

Andrea Ebner, Dirk Lorenz, Mathias Staudigl

arXiv:2610.35691v1math.NAcs.NAmath.OC

TL;DR

Singular-vector decompositions are determined by the operator and may not give sparse representations for a particular data set. The paper constructs data-aware tight-frame decompositions through bilevel optimization on the Stiefel manifold, with convergence to stationary points under suitable assumptions. Numerical experiments support sparse representations and competitive reconstruction results for inverse problems.

  • Problem

    Singular vectors are determined by the matrix and generally do not provide sparse representations adapted to a given signal distribution.

    Source: §3 · p. 2

  • Method

    The authors formulate data-aware tight-frame decomposition as a bilevel optimization problem on the Stiefel manifold and solve it with a penalized subgradient method.

    Source: §6 · p. 32

  • Results

    Numerical experiments support the method's practical construction of data-aware decompositions and report competitive reconstruction results on inverse problems.

    Source: §6 · p. 32

  • Takeaways & Limitations

    The resulting decompositions provide regularization tools for inverse problems, where they yield competitive reconstruction results.

    Source: §6 · p. 32

    The convergence analysis establishes asymptotic convergence to stationary points, not global minimizers; the authors identify further work on near-stationarity guarantees and computational efficiency.

    Source: §4.2 · p. 14, §6 · p. 32

Abstract

from arXiv · show

We present a method for computing a specific type of matrix decomposition that combines a structured framework with data-driven adaptation. This framework allows for an efficient and stable representation of signals or images using frames by identifying sets of vectors that naturally capture the essential features of the given data. The resulting decomposition enables the development of regularization techniques that enhance the quality of reconstruction by preserving important signal characteristics while suppressing noise. We develop an optimization-based algorithm to compute the decomposition and establish convergence properties of the resulting iterates. Numerical experiments on synthetic data and tomographic image reconstruction illustrate the behavior of the proposed method and its performance compared to conventional spectral regularization methods.

1 Introduction

The paper studies a data-aware diagonal tight frame decomposition for sparse representation. It frames the task as finding matrices for a given operator and data set.

1 Introduction

  • The proposed diagonal tight frame decomposition adapts a tight-frame analogue of the singular value decomposition to data-aware sparse representation.Unlike an orthonormal basis, its corresponding singular vectors form a tight frame.Source: §1 · p. 1
  • Given a matrix A and data set X, the decomposition seeks matrices U, D, and V satisfying prescribed properties.Source: §1 · p. 1

3. Decomposition: A⊤V = UD,

The section motivates decompositions that combine operator structure with frames adapted to data, then connects that design to inverse problems and sparse representations. It outlines the reduction, bilevel optimization, convergence analysis, and distinction from related frame-design work.

3. Decomposition: A⊤V = UD,

  • Tight frames allow data-dependent sparse representations, unlike singular vectors determined solely by A; frame decompositions also support operator inversion and regularization.Tight-frame duals are particularly easy to compute, and sparsity can incorporate prior information about the signal class.Source: §3 · p. 2

1.1 Applications

  • Ill-posed inverse problems require regularization because direct inversion of an ill-conditioned discretization is sensitive to measurement noise.Non-tight finite-dimensional frames additionally require controlled frame bounds and computation of the corresponding dual frame.Source: §1.1 · pp. 2–3
  • When signal coefficients in U are sparse, the decomposition yields sparse observation coefficients in the dual frame, which can be stored with their indices.Filtering the signal coefficients can suppress noise while preserving significant components in a regularized reconstruction.Source: §1.1 · p. 3

1.2 Main contributions

  • The authors reduce the decomposition to positive diagonal matrices, characterize feasible D choices, and determine V from U and D once D is fixed.The tightness constraint leads to optimization on the Stiefel manifold.Source: §1.2 · p. 4
  • A bilevel Stiefel-manifold formulation places tightness and decomposition constraints at the lower level and data sparsity in the upper-level objective.The authors address its nonconvexity with a penalized subgradient method applicable beyond this decomposition problem.Source: §1.2 · p. 4
  • The authors analyze convergence of both optimization levels to stationary points under stated assumptions and report numerical evidence of sparse, data-adapted frames.Source: §1.2 · p. 4

1.3 Related work

  • Unlike scalable-frame work that tests diagonal scalings of a fixed frame, this approach jointly optimizes the frame and scaling to represent a prescribed operator and promote data-dependent sparsity.Prior frame-construction methods cited here instead address prescribed structural properties.Source: §1.3 · p. 4

2 Preliminaries

The preliminaries establish the finite-dimensional conventions and frame properties used in the decomposition. They relate Parseval frames to Stiefel-manifold matrices through transposition.

2 Preliminaries

  • The paper uses real finite-dimensional inner-product spaces, with Frobenius norms for matrices and ℓ2 norms for vectors unless stated otherwise.Source: §2 · p. 5

2.1 Frames

  • A frame has positive lower and upper bounds; it is tight when they coincide, Parseval when both equal one, and overcomplete when it is not a basis.The union of p orthonormal bases is a tight-frame example with bounds p.Source: §2.1 · p. 5
  • Frame analysis maps vectors to coefficients with U⊤, while synthesis uses U; tightness is characterized by UU⊤ = A Id, and a Parseval frame has UU⊤ = Id.For a tight frame, the canonical dual is a scaled copy of the frame; for a Parseval frame, it is the frame itself.Source: §2.1 · pp. 5–6

2.2 Stiefel manifold

  • Transposing a Stiefel-manifold matrix gives a Parseval frame, and every Parseval frame arises this way; the Stiefel manifold is compact.Source: §2.2 · p. 6

3 Computing data-aware tight frame decompositions

The method selects tight frame decompositions to promote sparse representations of sampled data, then reformulates the constrained design problem for computation. It reduces the matrix problem to a positive diagonal matrix and optimizes a frame on the Stiefel manifold.

3 Computing data-aware tight frame decompositions

  • Data-aware tight DFD design minimizes sampled frame-coefficient sparsity, but its nonconvex constraints motivate a tractable reformulation with convergence guarantees for a first-order method.The objective is convex, while the tight-DFD constraints are not.Source: §3 · p. 7

3.1 Reduction to Parseval tight DFDs for positive diagonal matrices

  • A reduced SVD converts the construction for a general matrix into one for its positive diagonal singular-value matrix, with Parseval-frame constraints simplifying the problem.Once the diagonal scaling D is fixed, the second frame is determined by the first.Source: §3.1 · pp. 7–8, §3.2 · p. 8

3.2 Predetermined quasi-singular values

  • For fixed scaling values D, a Parseval tight DFD exists exactly when d_i ≥ σ_i ≥ d_{i+K−R} for i=1,…,R; K>R adds adaptation freedom, while K=R permits no data adaptation.Additional rows may offer little benefit if they converge to zero; choosing D also trades spectral compatibility against sparsity.Source: §3.2 · pp. 9–10

3.3 Bilevel Optimization on the Stiefel Manifold

  • The Stiefel-manifold bilevel formulation relaxes exact feasibility: when Ψ(U)=ϵ<1, the resulting V has frame bounds 1−ϵ and 1+ϵ.The data-driven choice of D aims to align U with dominant data directions while keeping Ψ small; small coefficients are replaced by a neutral value.Source: §3.3 · pp. 10–11

4 The Numerical Scheme

This section formulates data-aware DFD computation as a bilevel optimization problem on the Stiefel manifold and develops a penalty-based Riemannian subgradient scheme. It establishes convergence and stationarity guarantees for the iterates, including conditional stationarity of limit points for the upper-level objective.

4 The Numerical Scheme

  • The bilevel model defines feasibility through minimizers of Ψ on the Stiefel manifold, with ϕ selecting a preferred solution; its analysis uses a Riemannian subgradient inequality that accounts for manifold geometry.The inequality’s additional Lipschitz-constant term arises from restricting the function to the nonconvex Stiefel manifold.Source: §4 · p. 12, §4.2 · p. 15

4.1 Penalty Subgradient Method on the Stiefel Manifold

  • The method increases a penalty on the lower-level objective while the upper-level objective selects among its minimizers, using tangent-space subgradient steps and retraction onto the Stiefel manifold.The retraction is based on the polar decomposition and is chosen for its nonexpansiveness.Source: §4.1 · pp. 13–14

4.2 Convergence Analysis

  • Theorem 4.3 bounds lower-level stationarity while accounting for feasibility violation, and suitable step-size and penalty conditions make the bound vanish.The auxiliary parameter λ must be chosen sufficiently small and then held fixed; the bound deteriorates as λ approaches its upper admissible limit.Source: §4.2 · pp. 16–17
  • Under the first corollary’s step-size and penalty conditions, the lower-level Riemannian gradient has a convergence rate and the iterates admit a subsequence converging to a stationary point.The corollaries transfer rates from the Moreau-envelope stationarity measure to the lower-level gradient norm.Source: §4.2 · p. 18
  • With the second corollary’s more restrictive step sizes, the lower-level gradient has a convergence rate and every limit point of a convergent subsequence is stationary.This guarantee comes with a marginally worse convergence rate than the first corollary’s.Source: §4.2 · p. 18
  • Under additional regularity assumptions on Ψ and at the algorithm’s limit points, a limit point is stationary for the upper-level objective restricted to the lower-level stationary set.The analysis does not establish that upper-level penalized-objective subgradients along the generated iterates converge to zero.Source: §4.2 · p. 19
  • Theorem 4.7 bounds the penalized-problem stationarity measure and gives step-size and penalty-sequence criteria for convergence; its bound depends on λ < 1/ρ.The bound deteriorates as λ approaches either endpoint of its admissible range: near zero its quadratic coefficient grows, and near the upper bound its denominator constant shrinks.Source: §4.2 · pp. 22–23
  • For βk = C(k + 1)^p with 0 < p < 1/2, Corollary 4.8 gives a stationarity measure that converges to zero when p < 1/4.The corollary also specifies γk = ˜γ/(βk(k + 1)).Source: §4.2 · p. 23
  • For convergent Vk, any collection of Riemannian subgradients of convex ϕ admits a convergent subsequence whose limit remains in the Riemannian subdifferential at V*.This supplies the subgradient-limit property needed despite the set-valued subdifferential.Source: §4.2 · p. 24
  • A subsequence of iterates and their proximal points converges to U* with ∇StΨ(U*) = 0, and the limit points can be characterized as stationary for ϕ on the stationary set under additional regularity.The latter characterization requires twice continuous differentiability, the constant-rank condition, and a smooth stationary set near U*.Source: §4.2 · pp. 24–25
  • The cited passage specifies βk = C(k + 1)^p for p < 1/4, defines Ũk = proxλΩk/βk(Uk), and asserts the existence of a subsequence {τ(k)}.Source: §4.2 · p. 26

5 Numerical Examples and Application

The numerical examples examine learned diagonal frame decompositions on synthetic data and for tomographic reconstruction. The learned frame recovers sparse structure in the synthetic example, while filtered DFD consistently outperforms filtered SVD in the reported reconstruction comparisons.

5.1 Visualization of theoretical results

  • The synthetic experiment uses 50 vectors that are 2-sparse in an unknown tight wavelet frame, and tests algorithm behavior and parameter choices.For the heuristic D, Fan–Pall conditions are violated, so no DFD with both U and V tight exists, but Algorithm 1 still approximates frames.Source: §5.1 · p. 27, §5 · p. 27
  • ∥(U∗)⊤X∥1 ≈84, slightly below the generating wavelet frame’s sparsity measure of approximately 85.The learned frame visually recovers the wavelet structures despite the generating frame being unknown during computation.Source: §5.1 · p. 27, Figure 1 · p. 28
  • Sufficiently large K yields condition numbers around 3.6 to 4, while small K leaves them close to cond(Σ) ≈13.6.All tested K values achieve the same sparsity level, though K = 25 requires more iterations or a larger step size.Source: §5.1 · p. 28, Figure 2 · p. 29
  • A too-small step size makes convergence excessively slow, while a too-large step size keeps sparsity loss and condition number high before they decrease.The suitable step-size constant also depends strongly on the condition numbers of Σ and D.Source: §5.1 · pp. 28–29, Figure 3 · p. 29
  • The data-aware D choice achieves lower sparsity loss than Fan–Pall but raises Vk’s condition number to about 4 rather than about 2.D = Σ behaves similarly to Fan–Pall; a larger condition number can limit reconstruction stability.Source: §5.1 · p. 29, Figure 4 · p. 30

5.2 Filter-regularization with Learned DFD

  • Learning large-scale DFDs can be computationally demanding, and the reconstruction evaluation uses relatively low-resolution 20 × 20 images and 20 × 30 sinograms.The authors describe this resolution as a controlled setting for evaluating reconstruction performance and error characteristics.Source: §5.2 · p. 30
  • The tomography experiment learns a DFD from 500 real lung CT images and applies soft-thresholding filters to reconstruct images from noisy sinograms.The operator is truncated before learning to reduce computation, with only a minor effect on filtered reconstructions.Source: §5.2 · pp. 30–31
  • Filtered DFD with the data-aware learned frame consistently outperforms filtered SVD across the considered noise levels and evaluation metrics.Figure 5 reports relative ℓ2-error, PSNR, and SSIM averaged over 50 test images.Source: Figure 5 · p. 31, §5.2 · p. 31

6 Conclusion

The paper constructs data-aware diagonal frame decompositions through bilevel optimization on the Stiefel manifold and analyzes a penalized subgradient method. Under suitable assumptions, its iterates converge to stationary points, and experiments show competitive reconstruction results for inverse problems.

6 Conclusion

  • The proposed data-aware decompositions use tight frames that promote sparse representations of the given data.The construction is formulated as a bilevel optimization problem over the Stiefel manifold, whose nonconvex geometry makes the bilevel problem nonconvex.Source: §6 · p. 32
  • Under suitable assumptions, the penalized subgradient method’s iterates converge to stationary points at both optimization levels, with convergence rates given by appropriate stationary measures.Numerical experiments confirm the method’s theoretical behavior and show competitive reconstruction results when the decompositions are used for inverse-problem regularization.Source: §6 · p. 32
  • Future work includes testing other sparsity-promoting data terms and their practical performance in constructing data-aware DFDs.The authors also identify near-stationarity analysis, parallelization, and more efficient Stiefel-manifold retractions as future directions.Source: §6 · p. 32

A Tools on the Stiefel manifold

The appendix introduces manifold-theory tools used in the paper’s analysis. It treats the Stiefel manifold as an embedded submanifold and specifies its tangent spaces.

A Tools on the Stiefel manifold

  • The appendix collects manifold-theory elements needed for the analysis, with a general introduction to Riemannian optimization cited for further background.The Stiefel manifold is treated as an embedded submanifold of the Euclidean matrix space through a locally defining function.Source: A Tools on the Stiefel manifold · p. 33, §A.1 · p. 33

A.1 Basic notions

  • At a Stiefel-manifold point A, the tangent space consists of matrices V satisfying V⊤A + A⊤V = 0.The manifold is the zero set of h(A) = A⊤A − Id_R.Source: §A.1 · p. 33
  • The tangent bundle of a manifold M is the set of pairs (x, ξ) where x ∈ M and ξ belongs to the tangent space at x.Source: §A.1 · p. 33

A.2 Retractions

Retractions provide smooth ways to move from a point along a tangent direction while remaining on a manifold. The paper uses the polar retraction on the Stiefel manifold.

A.2 Retractions

  • A retraction maps a point and tangent direction to a curve whose initial point is the manifold point and whose initial velocity is the tangent direction.The practical choice of retraction is guided by the manifold’s geometric and algebraic structure.Source: §A.2 · p. 33
  • For the Stiefel manifold, the paper uses the polar retraction, computed from the SVD of A + ξ as ZW⊤ when A + ξ = ZΛW⊤.A common alternative is the Q-factor retraction, obtained from a thin QR decomposition.Source: §A.2 · p. 33
  • The polar retraction has the property of nonexpansiveness.Source: §A.2 · p. 33

A.3 Derivatives

This material develops tools for derivatives and local analysis on the Stiefel manifold, then introduces parallel transport, Taylor expansion, and weak convexity.

A.3 Derivatives

  • Euclidean subgradients of a convex extension yield Riemannian subgradients by projection onto the Stiefel tangent space.The tangent-space projector also provides a route from Euclidean derivatives to Riemannian derivatives; the Hessian is used only theoretically, not computed in experiments.Source: §A.3 · p. 34

A.4 Parallel Transport and Taylor expansion

  • Parallel transport moves tangent vectors between points along a curve, and on the Stiefel manifold it is a linear isometry.The appendix introduces Taylor expansion of the Riemannian gradient along a geodesic between sufficiently close points.Source: §A.4 · p. 35

B Weakly convex functions

  • A function is τ-weakly convex when adding a suitable quadratic term makes it convex; convex functions are the special case τ = 0.The text states that differentiable τ-weakly convex functions satisfy a gradient inequality.Source: B Weakly convex functions · p. 35
Loading 2610.35691v1…