Singular value decomposition

Solo disponible en BuenasTareas
  • Páginas : 7 (1701 palabras )
  • Descarga(s) : 0
  • Publicado : 9 de octubre de 2010
Leer documento completo
Vista previa del texto
Image Compression using Singular Value Decomposition
Adam Abrahamsen and David Richards December 14, 2001
Abstract Do you store images on your computer? Do you need more room on your hard drive? Well, you could upgrade your hard drive. But, we would like to propose an alternative solution. Computer technology these days is most focused on storage space and speed. One way to help cure thisproblem is Singular Value Decomposition. We have put together this easy to read explanation of how to use Singular Value Decomposition to reduce the space required to store images. We assume that the reader has a basic knowledge of eigenvalues, eigenvectors, and matrix operations.
Introduction to SVD Mathematics Image Processing with . . . Using SVD in Matlab Conclusion

Home Page

Title Page1.

Introduction to SVD
Page 1 of 14

Singular Value Decomposition (SVD) is said to be a significant topic in linear algebra by many renowned mathematicians. SVD has many practical and theoretical values, other than image compression. One special feature of SVD is that it can be performed on any real (m,n) matrix. It factors A into three matrices U, S, V, such that, A = U SV T . Where U andV are orthogonal matrices and S is a diagonal matrix.

Go Back

2.

Mathematics

Full Screen

We have stated that the purpose of (SVD) is to factor matrix A into U SV T . The matrix U contains the left singular vectors, the matrix V contains the right singular vectors, and the diagonal matrix S contains the singular values. Where the singular values are arranged on the main diagonal insuch an order σ1 ≥ σ2 ≥ · · · ≥ σr > σr+1 = · · · = σp = 0,

Close

Quit

where r is the rank of matrix A, and where (p ) is the smaller of the dimensions m or n.

2.1.

Arbitrary Example

We begin the process of Singular Value Decomposition by selecting the matrix A which has m rows and n columns. Now, we need to factor A into three matrices U, S, V T . First we will find V . If youmultiply both sides of the equation A = U SV T by AT we get AT A = (U SV T )T (U SV T ) = V S T U T U SV T . Since U U = I this gives A A=VS V
T 2 T T

Introduction to SVD Mathematics Image Processing with . . . Using SVD in Matlab Conclusion

Now we need to diagonalize AT A. If you will notice, this is very similar to the diagonalization of matrix A into A = QΛQT . Except our symmetricmatrix is not A, it is AT A. To find V and S we need to find the eigenvalues and eigenvectors of AT A. The eigenvalues are the square of the elements of S (the singular values), and the eigenvectors are the columns of V (the right singular vectors). Eliminating V from the equation is very similar to eliminating U . Instead of multiplying on the left by AT we will multiply on the right by AT . Thisgives: AAT = (U SV T )(U SV T )T = U SV T V S T U T . Since V T V = I, this gives AAT = U S 2 U T Again we will find the eigenvectors, but this time for AAT . These are the columns of U (the left singular vectors). Since A is m × n, S is m × n and AT A produces an n × n matrix, and: AAT

Home Page

Title Page

Page 2 of 14

Go Back

Full Screen

Close

Quit

produces an m × m matrix, σ1        ..  T v1  .   .    .T   vr     .   .  . T 0 vn 

. σr .. .

A = u1

···

ur

···

um

Introduction to SVD Mathematics Image Processing with . . . Using SVD in Matlab

Where U is m × m, S is m × n, V is n × n.

2.2.
Let :

2×2 Example
A= AT A = = 2 −2 1 1 2 −2 1 1

Conclusion

Home Page

2 1 −2 1 5 −3 −3 5

Title PageSubtracting λ(I) from AT A 5 −3 1 −λ −3 5 0 Therefore,
Go Back

0 1

=0

Page 3 of 14

5−λ −3 Now find λ,

−3 =0 5−λ
Full Screen

(5 − λ)(5 − λ) − 9 = 0 ⇒ 25 − 10λ + λ2 − 9 = 0 ⇒ λ2 − 10λ + 16 = 0 ⇒ (λ − 8)(λ − 2) = 0
Close

Quit

Therefore our eigenvalues are 8 and 2. We construct the matrix S 2 by placing the eigenvalues along the main diagonal in decreasing order. 8 0 S2 = 0 2...
tracking img