Singular value decomposition: Difference between revisions

Revision as of 22:14, 1 June 2025

Latest revision as of 10:22, 27 August 2025

(7 intermediate revisions by 5 users not shown)

Line 171:

== SVD and spectral decomposition ==

=== Singular values, singular vectors, and their relation to the SVD ===

A non-negative real number {{tmath|\sigma}} is a '''[[singular value]]''' for {{tmath|\mathbf M}} if and only if there exist [[unit-length vectorsvector]]s {{tmath|\mathbf u}} in {{tmath|K^m}} and {{tmath|\mathbf v}} in {{tmath|K^n}} such that

<math display=block>\begin{align}

Line 230:

===Solving homogeneous linear equations===

A set of [[homogeneous linear equation]]s can be written as {{tmath|\mathbf A \mathbf x {{=}} \mathbf 0}} for a matrix {{tmath|\mathbf A}}, vector {{tmath|\mathbf x}}, and [[zero vector]] {{tmath|\mathbf x.0}}. A typical situation is that {{tmath|\mathbf A}} is known and a non-zero {{tmath|\mathbf x}} is to be determined which satisfies the equation. Such an {{tmath|\mathbf x}} belongs to {{tmath|\mathbf A}}'s [[Kernel (matrix)|null space]] and is sometimes called a (right) null vector of {{tmath|\mathbf A.}} The vector {{tmath|\mathbf x}} can be characterized as a right-singular vector corresponding to a singular value of {{tmath|\mathbf A}} that is zero. This observation means that if {{tmath|\mathbf A}} is a [[square matrix]] and has no vanishing singular value, the equation has no non-zero {{tmath|\mathbf x}} as a solution. It also means that if there are several vanishing singular values, any linear combination of the corresponding right-singular vectors is a valid solution. Analogously to the definition of a (right) null vector, a non-zero {{tmath|\mathbf x}} satisfying {{tmath|\mathbf x^* \mathbf A {{=}} \mathbf 0}} with {{tmath|\mathbf x^*}} denoting the conjugate transpose of {{tmath|\mathbf x,}} is called a left null vector of {{tmath|\mathbf A.}}

===Total least squares minimization===

Line 249:

where <math>\tilde{\mathbf \Sigma}</math> is the same matrix as <math>\mathbf \Sigma</math> except that it contains only the {{tmath|r}} largest singular values (the other singular values are replaced by zero). This is known as the '''[[Low-rank approximation|Eckart–Young theorem]]''', as it was proved by those two authors in 1936 (although it was later found to have been known to earlier authors; see {{harvnb|Stewart|1993}}).

=== Image compression ===

[[File:Svd compression.jpg|thumb|Singular-value decomposition (SVD) image compression of a 1996 Chevrolet Corvette photograph. The original RGB image (upper-left) is compared with rank 1, 10, and 100 reconstructions.|292x292px]]One practical consequence of the low-rank approximation given by SVD is that a [[greyscale image]] represented as an <math>m \times n</math> matrix <math>\mathbf{A}</math>, can be efficiently represented by keeping the first <math>k</math> singular values and corresponding vectors. The truncated decomposition

<math>\mathbf{A}_k = \sum_{j=1}^k \sigma_j\mathbf{u}_j \mathbf{v}_j^T </math>

Line 274:

===Nearest orthogonal matrix===

It is possible to use the SVD of a square matrix {{tmath|\mathbf A}} to determine the [[orthogonal matrix]] {{tmath|\mathbf OQ}} closest to {{tmath|\mathbf A.}} The closeness of fit is measured by the [[Frobenius norm]] of {{tmath|\mathbf OQ - \mathbf A.}} The solution is the product {{tmath|\mathbf U \mathbf V^*.}}<ref>[http://www.wou.edu/~beavers/Talks/Willamette1106.pdf The Singular Value Decomposition in Symmetric (Lowdin) Orthogonalization and Data Compression]</ref> This intuitively makes sense because an orthogonal matrix would have the decomposition {{tmath|\mathbf U \mathbf I \mathbf V^*}} where {{tmath|\mathbf I}} is the identity matrix, so that if {{tmath|\mathbf A {{=}} \mathbf U \mathbf \Sigma \mathbf V^*}} then the product {{tmath|\mathbf A {{=}} \mathbf U \mathbf V^*}} amounts to replacing the singular values with ones. Equivalently, the solution is the unitary matrix {{tmath|\mathbf R {{=}} \mathbf U \mathbf V^*}} of the Polar Decomposition <math>\mathbf M = \mathbf R \mathbf P = \mathbf P' \mathbf R</math> in either order of stretch and rotation, as described above.

A similar problem, with interesting applications in [[shape analysis (digital geometry)|shape analysis]], is the [[orthogonal Procrustes problem]], which consists of finding an orthogonal matrix {{tmath|\mathbf OQ}} which most closely maps {{tmath|\mathbf A}} to {{tmath|\mathbf B.}} Specifically,

<math display=block>

\mathbf{O} Q = \underset\Omega\operatorname{argmin} \|\mathbf{A}\boldsymbol{\Omega} - \mathbf{B}\|_F \quad\text{subject to}\quad \boldsymbol{\Omega}^\operatorname{T}\boldsymbol{\Omega} = \mathbf{I},

</math>

Line 302:

===Signal processing===

The SVD and pseudoinverse have been successfully applied to [[signal processing]],<ref>{{cite journal |last=Sahidullah |first=Md. |author2=Kinnunen, Tomi |title=Local spectral variability features for speaker verification |journal=Digital Signal Processing |date=March 2016 |volume=50 |pages=1–11 |doi=10.1016/j.dsp.2015.10.011 |bibcode=2016DSP....50....1S |url= https://erepo.uef.fi/handle/123456789/4375}}<!--https://erepo.uef.fi/handle/123456789/4375--></ref> [[image processing]]<ref name="Mademlis2018">{{cite book |last1=Mademlis |first1=Ioannis |last2=Tefas |first2=Anastasios |last3=Pitas |first3=Ioannis |title=2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) |chapter=Regularized SVD-Based Video Frame Saliency for Unsupervised Activity Video Summarization |url=https://ieeexplore.ieee.org/document/8462274 |year=2018 |pages=2691–2695 |publisher=IEEE |doi=10.1109/ICASSP.2018.8462274 |isbn=978-1-5386-4658-8 |s2cid=52286352 |access-date=19 January 2023}}</ref> and [[big data]] (e.g., in genomic signal processing).<ref>

{{Cite journal

| author = O. Alter, P. O. Brown and D. Botstein

Line 405:

In [[astrodynamics]], the SVD and its variants are used as an option to determine suitable maneuver directions for transfer trajectory design<ref name=muralidharan2023stretching>{{Cite journal|title=Stretching directions in cislunar space: Applications for departures and transfer design|first1=Vivek|last1=Muralidharan|first2=Kathleen|last2=Howell|journal =Astrodynamics | volume = 7 | issue = 2| pages = 153–178 | date = 2023 | doi = 10.1007/s42064-022-0147-z | bibcode = 2023AsDyn...7..153M|s2cid=252637213 }}</ref> and [[orbital station-keeping]].<ref name=Muralidharan2021>{{Cite journal|title=Leveraging stretching directions for stationkeeping in Earth-Moon halo orbits |first1=Vivek|last1=Muralidharan|first2=Kathleen|last2=Howell|journal =[[Advances in Space Research]] | volume = 69 | issue = 1| pages = 620–646 | date = 2022 | doi = 10.1016/j.asr.2021.10.028 | bibcode = 2022AdSpR..69..620M|s2cid=239490016 }}</ref>

The SVD can be used to measure the similarity between real-valued matrices.<ref name=albers2025>{{Cite journal|title=Assessing the Similarity of Real Matrices with Arbitrary Shape|first1=Jasper|last1=Albers|first2=Anno|last2=Kurth|first3=Robin|last3=Gutzen|first4=Aitor|last4=Morales-Gregorio|first5=Michael|last5=Denker|first6=Sonja|last6=Gruen|first7=Sacha|last7=van Albada|first8=Markus|last8=Diesmann|journal=PRX Life| issue = 32| pagesarticle-number = 023005 | date = 2025 |volume=3 | doi = 10.1103/PRXLife.3.023005 |arxiv=2403.17687 |bibcode=2025PRXL....3b3005A }}</ref> By measuring the angles between the singular vectors, the inherent two-dimensional structure of matrices is accounted for. This method was shown to outperform [[cosine similarity]] and [[Frobenius norm]] in most cases, including brain activity measurements from [[neuroscience]] experiments.

== Proof of existence ==

Line 417:

By the [[extreme value theorem]], this continuous function attains a maximum at some {{tmath|\mathbf u}} when restricted to the unit sphere <math>\{\|\mathbf x\| = 1\}.</math> By the [[Lagrange multipliers]] theorem, {{tmath|\mathbf u}} necessarily satisfies

<math display=block>\nabla \mathbf{u}^\operatorname{T} \mathbf{M} \mathbf{u} - \lambda \cdot \nabla \mathbf{u}^\operatorname{T} \mathbf{u} = \mathbf{0}</math>

for some real number {{tmath|\lambda.}} The nabla symbol, {{tmath|\nabla}}, is the [[del]] operator (differentiation with respect to {{nobr|{{tmath|\mathbf x}}).}} Using the symmetry of {{tmath|\mathbf M}} we obtain

Line 700:

In applications that require an approximation to the [[Moore–Penrose inverse]] of the matrix {{tmath|\mathbf M,}} the smallest singular values of {{tmath|\mathbf M}} are of interest, which are more challenging to compute compared to the largest ones.

Truncated SVD is employed in [[latent semantic indexing]].<ref>{{cite journal | last1 = Chicco | first1 = D | last2 = Masseroli | first2 = M | year = 2015 | title = Software suite for gene and protein annotation prediction and similarity search | journal = IEEE/ACM Transactions on Computational Biology and Bioinformatics | volume = 12 | issue = 4 | pages = 837–843 | doi=10.1109/TCBB.2014.2382127 | pmid = 26357324 | bibcode = 2015ITCBB..12..837C | hdl = 11311/959408 | s2cid = 14714823 | url = https://doi.org/10.1109/TCBB.2014.2382127 | hdl-access = free }}

</ref>

Line 858:

* {{Citation | last1 = Banerjee | first1 = Sudipto | last2 = Roy | first2 = Anindya | date = 2014 | title = Linear Algebra and Matrix Analysis for Statistics | series = Texts in Statistical Science | publisher = Chapman and Hall/CRC | edition = 1st | isbn = 978-1420095388}}

* {{Cite book | last1=Bisgard | first1 = James | year = 2021 | title = Analysis and Linear Algebra: The Singular Value Decomposition and Applications | series = Student Mathematical Library | publisher = AMS | edition = 1st | isbn = 978-1-4704-6332-8}}

* {{cite journal | last1 = Chicco | first1 = D | last2 = Masseroli | first2 = M | year = 2015 | title = Software suite for gene and protein annotation prediction and similarity search | journal = IEEE/ACM Transactions on Computational Biology and Bioinformatics | volume = 12 | issue = 4 | pages = 837–843 | doi=10.1109/TCBB.2014.2382127 | pmid = 26357324 | bibcode = 2015ITCBB..12..837C | hdl = 11311/959408 | s2cid = 14714823 | url = https://doi.org/10.1109/TCBB.2014.2382127 | hdl-access = free }}

* {{Cite book | last2=Bau III | first2=David | last1=Trefethen | first1=Lloyd N. | author1-link = Lloyd N. Trefethen | title=Numerical linear algebra | publisher=Society for Industrial and Applied Mathematics | ___location=Philadelphia | isbn=978-0-89871-361-9 | year=1997 }}

* {{Cite journal | last1=Demmel | first1=James | author1-link = James Demmel | last2=Kahan | first2=William | author2-link=William Kahan | title=Accurate singular values of bidiagonal matrices | doi=10.1137/0911052 | year=1990 | journal= SIAM Journal on Scientific and Statistical Computing| volume=11 | issue=5 | pages=873–912 | citeseerx=10.1.1.48.3740 }}