6.3 Truncated SVD and filtering

Truncated SVD is a powerful tool in the realm of Singular Value Decomposition. It approximates matrices using only the largest singular values and vectors, striking a balance between data fidelity and noise reduction.

This technique finds applications in noise reduction, data compression, and solving ill-posed inverse problems. By filtering out small singular values, it effectively reduces dimensionality and extracts key features from complex datasets.

Truncated SVD: Concept and Properties

Fundamentals of Truncated SVD

Top images from around the web for Fundamentals of Truncated SVD

• 

  Sparse Time–Frequency Representation for the Transient Signal Based on Low-Rank and Sparse ... View original

  Is this image relevant?

• 

  Singulární rozklad – Wikipedie View original

  Is this image relevant?

• 

  Sparse Time–Frequency Representation for the Transient Signal Based on Low-Rank and Sparse ... View original

  Is this image relevant?

• 

  Singulární rozklad – Wikipedie View original

  Is this image relevant?

1 of 2

Top images from around the web for Fundamentals of Truncated SVD

• 

  Sparse Time–Frequency Representation for the Transient Signal Based on Low-Rank and Sparse ... View original

  Is this image relevant?

• 

  Singulární rozklad – Wikipedie View original

  Is this image relevant?

• 

  Sparse Time–Frequency Representation for the Transient Signal Based on Low-Rank and Sparse ... View original

  Is this image relevant?

• 

  Singulární rozklad – Wikipedie View original

  Is this image relevant?

1 of 2

• Truncated Singular Value Decomposition (TSVD) approximates a matrix using only the largest singular values and their corresponding singular vectors
• Derived from full SVD $A = UΣV^T$ by retaining first k singular values and vectors $A_k = U_kΣ_kV_k^T$
• Truncation parameter k determines rank of approximation and controls trade-off between data fidelity and noise reduction
• Filters out small singular values associated with noise or less significant features in data
• Quantifies error using Frobenius norm equal to sum of squares of discarded singular values
• Possesses optimal low-rank approximation property (Eckart-Young theorem)
• Preserves orthogonality of truncated singular vectors

Mathematical Representation and Error Analysis

• TSVD mathematical formulation $A_k = \sum_{i=1}^k \sigma_i u_i v_i^T$
  • $\sigma_i$ singular values
  • $u_i$ left singular vectors
  • $v_i$ right singular vectors
• Error introduced by truncation $||A - A_k||_F = \sqrt{\sum_{i=k+1}^n \sigma_i^2}$
• Relative error in Frobenius norm $\frac{||A - A_k||_F}{||A||_F} = \sqrt{\frac{\sum_{i=k+1}^n \sigma_i^2}{\sum_{i=1}^n \sigma_i^2}}$
• Singular value decay rate impacts approximation quality (faster decay leads to better low-rank approximations)

Applications and Interpretations

• Dimensionality reduction technique used in various fields (image processing, data compression)
• Noise reduction method in signal processing and data analysis
• Feature extraction tool in machine learning and pattern recognition
• Spectral analysis technique for identifying dominant modes in dynamical systems
• Regularization method for ill-posed inverse problems (seismic imaging, medical tomography)
• Data visualization aid for high-dimensional datasets (principal component analysis)

Noise Reduction and Data Compression with Truncated SVD

Noise Reduction in Inverse Problems

• TSVD solves ill-posed inverse problems by regularizing solution and reducing noise impact
• Acts as low-pass filter attenuating high-frequency components often associated with noise
• Truncated pseudoinverse $A_k^+ = V_kΣ_k^{-1}U_k^T$ computes regularized solutions to inverse problems
• Particularly effective for problems where signal-to-noise ratio decreases with increasing singular value index
• Application examples include image deblurring and electromagnetic source localization

Data Compression Techniques

• Represents large datasets using reduced number of singular values and vectors
• Compression ratio depends on choice of truncation parameter k
• Reconstruction quality trade-off with compression ratio
• Useful for storing and transmitting large datasets efficiently (satellite imagery, medical scans)
• Compression process:
  1. Compute SVD of original data matrix
  2. Select k largest singular values and corresponding vectors
  3. Store compressed representation $U_k$, $Σ_k$, and $V_k^T$
  4. Reconstruct data using $A_k = U_kΣ_kV_k^T$

Performance Metrics and Considerations

• Measures compression effectiveness using metrics (compression ratio, reconstruction error)
• Compression ratio calculated as $CR = \frac{\text{size of original data}}{\text{size of compressed data}}$
• Reconstruction error quantified using mean squared error (MSE) or peak signal-to-noise ratio (PSNR)
• Balances compression ratio with acceptable reconstruction quality
• Considers computational complexity of SVD for large datasets
• Evaluates impact of truncation on specific features or patterns in data

Optimal Truncation Level for SVD

L-curve Method

• Plots norm of regularized solution against norm of residual for different truncation levels
• Optimal k often found at corner of L-shaped curve
• Implementation steps:
  1. Compute SVD of system matrix
  2. Calculate solution norm and residual norm for various k values
  3. Plot solution norm vs. residual norm on log-log scale
  4. Identify corner of L-shaped curve
• Advantages include visual interpretation and automatic parameter selection
• Limitations include sensitivity to noise and ambiguity in corner definition

Generalized Cross-Validation (GCV)

• Selects truncation level minimizing GCV function estimating predictive error of model
• GCV function defined as $GCV(k) = \frac{n||Ax_k - b||^2}{(n - k)^2}$
  • n number of data points
  • $x_k$ TSVD solution with truncation level k
• Implementation steps:
  1. Compute SVD of system matrix
  2. Calculate GCV function for range of k values
  3. Select k minimizing GCV function
• Advantages include automatic parameter selection and theoretical justification
• Limitations include computational cost for large problems and potential for multiple local minima

Discrete Picard Condition (DPC)

• Determines appropriate truncation level by examining decay rate of Fourier coefficients relative to singular values
• Picard plot visualizes relationship between singular values and corresponding Fourier coefficients
• Implementation steps:
  1. Compute SVD of system matrix
  2. Calculate Fourier coefficients $|u_i^T b|$
  3. Plot singular values and Fourier coefficients vs. index
  4. Identify point where Fourier coefficients begin to level off
• Advantages include insight into problem's inherent ill-posedness
• Limitations include subjective interpretation and sensitivity to noise in data

Truncated SVD vs Other Filtering Techniques

Comparison with Tikhonov Regularization

• TSVD applies hard threshold while Tikhonov uses smooth filter factor
• TSVD filter factors binary (0 or 1) whereas Tikhonov uses continuous filter factors based on regularization parameter
• Tikhonov regularization often produces smoother solutions than TSVD
• TSVD can result in step-like artifacts due to hard truncation
• Tikhonov filter factors $f_i = \frac{\sigma_i^2}{\sigma_i^2 + \alpha^2}$ where α regularization parameter
• TSVD generally computationally less complex especially for large-scale problems
• Tikhonov regularization more flexible in incorporating prior information about solution

Comparison with Wiener Filtering

• Wiener filtering optimal in mean square error sense for stationary processes
• TSVD optimal for low-rank approximations
• TSVD generally easier to interpret and implement compared to Wiener filtering
• Wiener filtering requires knowledge or estimation of signal and noise spectra
• Wiener filter transfer function $H(f) = \frac{S_x(f)}{S_x(f) + S_n(f)}$ where $S_x(f)$ and $S_n(f)$ signal and noise power spectra
• TSVD more suitable for non-stationary signals or when spectral information unavailable
• Wiener filtering can adapt to varying noise levels across frequency spectrum

Hybrid and Advanced Techniques

• Hybrid methods combine TSVD with other techniques leveraging strengths of multiple filtering approaches
• Tikhonov-TSVD combines smooth regularization of Tikhonov with truncation of TSVD
• Iterative methods (LSQR, CGLS) can be combined with TSVD for improved computational efficiency
• Adaptive truncation methods adjust truncation level based on local properties of data
• Multi-parameter regularization incorporates multiple regularization terms with TSVD
• Nonlinear extensions of TSVD (kernel TSVD) handle nonlinear inverse problems
• Bayesian approaches incorporate prior information and uncertainty quantification in TSVD framework