Exact deflation for accurate SVD computation of nonnegative bidiagonal products of arbitrary rank

Basic Information

• Paper ID: 2510.10502
• Title: Exact deflation for accurate SVD computation of nonnegative bidiagonal products of arbitrary rank
• Authors: Huang Rong (Hunan Normal University), Jungong Xue (Fudan University)
• Classification: math.NA, cs.NA (Numerical Analysis)
• Publication Date: October 12, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.10502

Abstract

Handling zero singular values presents significant challenges in numerical computation, as they can lead to numerous numerical difficulties. This paper proposes a method for computing the singular value decomposition (SVD) of products of nonnegative bidiagonal matrices of arbitrary rank, whether the factor matrices are full-rank or rank-deficient, square or rectangular. The key characteristic of the method is its ability to exactly eliminate all zero singular values with good complexity, unaffected by rank deficiency and ill-conditioning. Furthermore, it ensures high relative accuracy in computing nonzero singular values, regardless of how small these values are. The method also applies to accurately computing the SVD of arbitrary submatrices by extracting their representations from the original product.

Research Background and Motivation

Problem Background

1. Core Problem: Computing the singular value decomposition of matrix products or quotients is crucial in applications such as statistical realization, control theory, canonical correlation analysis, and source separation
2. Technical Challenges:
   • Existing algorithms, while backward stable and capable of computing SVD with high absolute accuracy, often struggle to accurately compute small singular values
   • When multiple matrices are involved, computing high relative accuracy SVD faces challenges
   • In rank-deficient cases, the presence of zero singular values leads to numerous numerical difficulties

Research Significance

1. Theoretical Value: Fills the theoretical gap in SVD computation for rank-deficient bidiagonal products
2. Practical Value: Provides a unified framework for SVD computation of structured matrices (Cauchy, Vandermonde, Bernstein-Vandermonde, etc.)
3. Numerical Stability: Resolves numerical instability issues of traditional methods in handling zero singular values

Limitations of Existing Methods

1. High-precision SVD algorithms are primarily designed for single full-rank matrices and cannot be directly applied to multi-matrix scenarios
2. When handling rank-deficient matrices, existing methods cannot accurately identify and eliminate zero singular values
3. For structured matrices with repeated nodes, there lacks a universal method for bidiagonal product representation

Core Contributions

1. Exact Elimination Method: Proposes an algorithm capable of exactly eliminating all zero singular values with complexity O(rS + max{n₀²r, n_K²r}), where r is the minimum dimension and S is the total number of nontrivial element pairs
2. High Relative Accuracy Computation: Ensures high relative accuracy in computing nonzero singular values, regardless of their magnitude
3. Submatrix Representation Extraction: Develops a universal method for extracting representations of arbitrary submatrices from the original bidiagonal product
4. Unified Framework: Provides a unified bidiagonal product representation and SVD computation framework for structured matrices with repeated nodes
5. Theoretical Guarantees: Provides complete error analysis proving the high relative accuracy property of the method

Methodology Details

Task Definition

Input: Nonnegative bidiagonal product A = B₁B₂...B_K ∈ ℝ^(n₀×n_K), where B_k ∈ ℝ^(n_(k-1)×n_k) are nonnegative lower or upper bidiagonal matrices Output: Complete SVD decomposition of A, exactly identifying zero singular values, computing nonzero singular values with high relative accuracy Constraints: Handle matrices of arbitrary rank, including rank-deficient and ill-conditioned cases

Core Algorithm Architecture

1. Representation Extraction Method (Section 3)

The paper introduces a compact representation of bidiagonal products:

A =: ({ḡᵢⱼ, gᵢⱼ}) ∈ ℝ^(n×m)

Through bidiagonal factorization form:

A = L_(n-1)...L₁DU₁...U_(m-1)

Key Operations:

• Update Operation: Representation update when adding zero rows/columns
• Downsampling Operation: Representation computation when deleting rows/columns, with cost O(min{t,m}) subtraction-free operations
• Penetration Operation: Computing representations of UA and LA, where U, L are bidiagonal matrices

2. Cyclic Elimination Algorithm (Section 4)

Based on minimum dimension r = min₀≤k≤K{nk}, decompose A = A₂A₁:

• A₁ = B_(T+1)...B_K ∈ ℝ^(r×n_K)
• A₂ = B₁...B_T ∈ ℝ^(n₀×r)

Four-Step Elimination Process:

1. Step One: Delete zero rows of A₁ (revealed by ḡᵢ₁ = 0) and corresponding columns of A₂
2. Step Two: Construct orthogonal transformations to eliminate zero rows of A₂
3. Step Three: Delete zero columns of A₂ and corresponding rows of A₁
4. Step Four: Construct orthogonal transformations to eliminate zero columns of A₁

Technical Innovations

1. Exact Elimination Mechanism

• Zero Detection: Directly identify zero rows/columns through zero elements in representation (e.g., ḡ_k1 = 0)
• Permutation Matrices: Use permutation matrices P to exactly extract zero structure
• Orthogonal Transformations: Construct Givens rotations to realize L⁻¹ = G·U⁻¹ decomposition

2. Subtraction-Free Operations

The entire algorithm avoids subtraction of numbers with the same sign, ensuring:

• Zero singular values are exactly eliminated
• Nonzero singular values maintain high relative accuracy

3. Complexity Optimization

Compared to direct method's O(min{n₀,n_K}·S + max{n₀²n_K, n_K²n₀}), the cyclic method achieves O(rS + max{n₀²r, n_K²r}), providing significant optimization when r ≪ min{n₀,n_K}.

Experimental Setup

Datasets

The paper tested four classes of structured matrices and submatrices of their products:

1. Cauchy Matrices: A = (1/(xᵢ + yⱼ)) ∈ ℝ^(ns₁×ms₂)
2. Vandermonde Matrices: A = (x^(⌈j/s₂⌉-1)ᵢ) ∈ ℝ^(ns₁×ms₂)
3. Cauchy-Vandermonde Matrices: Hybrid Cauchy and Vandermonde structure
4. Bernstein-Vandermonde Matrices: Vandermonde matrices based on Bernstein basis

Evaluation Metrics

• Relative Error: Rel. error(σ̂ᵢ) = |σ̂ᵢ - σᵢ|/σᵢ
• Zero Singular Value Identification: Exact count of identified zero singular values
• Reference Solution: "Exact" singular values computed using Mathematica 200-digit precision arithmetic

Comparison Methods

• MATLAB svd Command: Applied to explicitly computed matrix products
• Proposed Method: Directly applied to definition nodes of structured matrices

Implementation Details

• Platform: MATLAB 7.0 double precision arithmetic
• Test Cases: 4 numerical experiments covering different matrix types and dimensions

Experimental Results

Main Results

Example 1: Four-Matrix Product A = A₄A₃A₂A₁

• Matrix Size: 60×80 submatrix from larger product
• Zero Singular Values: Proposed method exactly identifies 10 zero singular values; svd command fails to identify them
• Relative Error: Proposed method maintains 10⁻¹⁵ magnitude; svd command achieves 10²⁵ magnitude error for small singular values

Example 2: Three-Matrix Product A = A₁A₁ᵀA₁

• Matrix Size: 50×60 Cauchy-Vandermonde matrix submatrix
• Zero Singular Values: Exactly returns 20 zero singular values
• Performance: Minimum singular value relative error maintained at 10⁻¹⁶ magnitude; svd command completely fails

Example 3: Vandermonde Matrix Cube

• Characteristics: Exactly identifies 15 zero singular values; svd command reports no zero values
• Accuracy: All 35 nonzero singular values achieve machine precision level

Example 4: Random Bidiagonal Product

• Setup: A = A₁A₁ᵀA₁, where A₁ is 90×50 random bidiagonal matrix
• Results: Exactly identifies 36 zero singular values; 14 nonzero singular values computed with high accuracy

Key Findings

1. Exact Elimination: Zero singular values are exactly identified and eliminated in all test cases
2. High Relative Accuracy: Nonzero singular value relative errors maintained at 10⁻¹⁶ to 10⁻¹⁴ magnitude
3. Significant Advantage: Compared to traditional svd command, achieves tens of orders of magnitude precision improvement in small singular value computation

Related Work

Main Research Directions

1. Structured Matrix SVD: High-precision algorithms for full-rank Cauchy, Vandermonde, and other matrices
2. Matrix Product SVD: SVD computation methods for products of two or three matrices
3. Bidiagonal Matrix Algorithms: High-precision SVD methods for single bidiagonal matrices

Positioning of This Work's Contribution

• Extended Scope: From full-rank to arbitrary rank, from single matrix to products
• Unified Framework: First to provide unified treatment for structured matrices with repeated nodes
• Theoretical Breakthrough: Resolves the open problem of SVD computation for rank-deficient TN matrices

Conclusions and Discussion

Main Conclusions

1. Successfully developed a complete algorithmic framework for SVD computation of nonnegative bidiagonal products of arbitrary rank
2. Achieved exact elimination of zero singular values and high relative accuracy computation of nonzero singular values
3. Provided a universal method for extracting representations of arbitrary submatrices
4. Established complete error analysis theory

Theoretical Guarantees

Theorem 1: For bidiagonal products with S nontrivial element pairs, the algorithm guarantees:

• All zero singular values are exactly eliminated
• Nonzero singular values satisfy: σ̂ᵢ = (1 + ηᵢ)σᵢ, where |ηᵢ| ≤ O(2Cμ)/(1-O(2Cμ))
• Complexity: C = rS + max{n₀²r, n_K²r}

Limitations

1. Applicable Scope: Primarily targets nonnegative bidiagonal products; not directly applicable to general matrices
2. Storage Requirements: Requires storing complete orthogonal transformation matrices; space complexity O(n₀³ + n_K³)
3. Implementation Complexity: Algorithm involves multiple delicate numerical operations; relatively complex to implement

Future Directions

1. Extension to more general structured matrix types
2. Development of parallel versions for large-scale problems
3. Investigation of optimized algorithms for sparse cases

In-Depth Evaluation

Strengths

1. Theoretical Completeness: Provides complete algorithmic framework and rigorous error analysis
2. Practical Value: Solves important problems in structured matrix computation
3. Numerical Stability: Ensures numerical stability through subtraction-free operations
4. Generality: Unified treatment of multiple structured matrix types

Weaknesses

1. Algorithm Complexity: While theoretically optimized, practical implementation remains complex
2. Applicability Restrictions: Primarily applicable to specific structured matrices; limited generality
3. Experimental Scale: Matrix sizes in numerical experiments are relatively small

Impact

1. Academic Contribution: Fills theoretical gap in SVD computation for rank-deficient structured matrices
2. Practical Value: Provides reliable numerical methods for scientific computing and engineering applications
3. Reproducibility: Detailed algorithm description with good reproducibility

Applicable Scenarios

1. Scientific Computing: Large-scale numerical computation involving structured matrices
2. Signal Processing: Signal analysis applications requiring high-precision SVD
3. Control Theory: Matrix decomposition problems in system analysis
4. Statistical Analysis: Statistical methods involving singular value decomposition

References

The paper cites 33 related references, primarily including:

• Series of works by Koev P. on exact computation for totally nonnegative matrices
• Classical literature by Demmel J. et al. on high relative accuracy SVD algorithms
• Research by Marco A., Martínez J.J. on bidiagonal decomposition of structured matrices
• Foundational literature in numerical linear algebra

Overall Assessment: This is a high-quality numerical analysis paper with significant contributions at both theoretical and practical levels. The algorithm design is ingenious, the theoretical analysis is rigorous, and numerical experiments sufficiently validate the method's effectiveness. It holds important academic value and practical significance for the field of structured matrix computation.