...menustart
- 18.Determinants
- 19. Formular for Determinant
- 20. APPLICATIONS OF DETERMINANTS
- 21. EigenValues - EigenVectors
- 22. Diagonalizing
- 23.
- 24.
- 25.
...menuend
Up to now we paid a lot of attention to rectangular matrices.
Now, concentrating on square matrices. Determinants and Eigen values are big, big chunk of 18.06.
Every square matrix has a number associated with , called its determinant.
- det A = 0 , means A is singular.
- det A !=0 , means A is invertible.
Determinant is signed.
3 base properties:
- det I = 1.
- Exchanging rows reverse sign of det.
- The determinant depends linearly on one row. (single row linearity)
-
|a+a' b+b'| =|a b| + |a' b'| |c d | |c d| |c d | -
|ka kb| = k |a b| | c d| |c d|- det2A = 2ⁿ detA
- det(A+B) ≠ detA + detB
-
p4 ~ p10
- p4: property 2 also said , dup rows => det=0
- p5: elimination ( - k rowi from rowj ) doesn't change det.
- 数学上，减去的这部分 使用p3 可以分离出去，这部分的det 为0.
- 集合上，平行四边形,底不变发生切变，面积不变
- p6: zero row => det=0.
- p3b, in case a=0,b=0 , K·det=det => det=0.
- p7: triangular matrix, det = product of pivots
- p8: If A is singular, then det A = 0. If A is invertible, then det A ≠ 0.
- p9: det AB = detA * detB (very valuable property)
- detA⁻¹
- p10: detAᵀ = detA
- 行列式，所有行的性质，对列同样有效
- use property 3 to break down each row
- [a b c] = [a 0 0] + [0 b 0] + [0 0 c]
- the determinant of A can be expanded into nⁿ terms
- a lot terms has 0 det, they can be removed.
- The nonzero terms have to come in different columns and rows.
Cofactor is a way of breaking up above big formula that connects the nxn determinant to a determinant one smaller.
- The determinant of A is a combination of any row i times its cofactors.
- det A by cofactors: det A = aᵢ₁Cᵢ₁ + aᵢ₂Cᵢ₂ + ... + aᵢ𝑛Cᵢ𝑛. (10)
- The cofactor is the determinant of Mᵢⱼ , with the correct sign:
- delete row i and column j: Cᵢⱼ = (-1)ⁱ⁺ʲ detMᵢⱼ. (11)
ACᵀ = (detA) I
The critical question is: Why do we get zeros off the diagonal?
The answer is: we are actually computing the determinant of a new matrix which has equal rows.
What do I get in Cᵀb ? What's the first entry of Cᵀb ?
Somehow I multiply cofactors by the entries of b, anytime I'm multiplying cofactors by numbers, I think, I'm getting the determinant of something. Let's call the matrix B , whose determinant comes out of Cᵀb .
So x₁ = detB₁/detA , x₂ = detB₂/detA , ...
4C: Cramer's rule: The jth component of x = A⁻¹b is the ratio
Actually, Cramer's Rule is a disastrous way to go, because compute these determinants takes like approximately forever.
But having a formula allows you to do algebra instead of algorithms. They're nice formulas, but I just don't want you to use them.
已知三角形的三个顶点：
(x1,y1),(x2,y2),(x3,y3),求面积:
解：
|x1 y1 1|
S= 1/2 det |x2 y2 1|
|x3 y3 1|
如果有个顶点是原点,比如(x1,y1)=(0,0)
S = 1/2 det|x2,y2|
|x3,y3|
There are certain vectors where Ax comes out parallel to x. And those are the eigenvectors. Ax=λx.
If A is singular, λ=0 is an eigenvalue.
Now the question is how do we find these x-s and λ.
Projection Matrix
Any x in projection plane Ax=x , λ=1
Any x ⟂ plane, Ax=0 , λ=0.
Permutation Matrix
A =
0 1
1 0
x = [1;1] , λ=1
x = [-1;1] , λ=-1. In fact, the trace tells you right away what the other eigenvalue is.
How to solve Ax=λx ?
(A-Iλ)x = 0. A-Iλ has to be singular.
The idea will be to find λ first. I'll find n λ's. A λ could be repeated, A repeated λ is source of all trouble in 18.06.
Fact: sum of λ's = a₁₁+a₂₂+ ... + ann.
Symmetric Matrix Example
A =
3 1
1 3
det(A-λI) = |3-λ 1| = (3-λ)²-1
|1 3-λ|
= λ²-6λ+8
This example is great. 6 is the trace ,and 8 is the determinant.
λ₁=4, λ₂=2 .
A-4I =
-1 1
1 -1
x₁= [1;1]
A-2I =
1 1
1 1
x₂= [-1;1]
What's the relateion between the Permutation example and Symmetric example ?
Simple but useful observation: if I add n·I to a matrix, its eigenvectors don't change, and its eigen values are n bigger.
Why does it happen ?
Suppose I have a matrix A, and Ax=λx. I add 3I to that matrix.
(A+3I)x = λx + 3x = (λ+3)x
Rotation matrix Q
Q =
0 -1
1 0
90° rotation.
trace = 0 = λ₁+λ₂ , det = 1 = λ₁λ₂. λ²=-1.
What I'm leading up to with this example is that something is gonna go wrong, because what vector can come out parallel to itself after a 90° rotation?
λ₁=i, λ₂=-i.
If a matrix was symmetric, it wouldn't happen ( complex number λ ). So if we stick to matrices that are symmetric , or close to symmetri, then the eigenvalues will stay real. But if we move far away from symmetric , for this example it's anti-symmetric , the bad thing will happen.
Here's one more bad thing that could happen.
A =
3 1
0 3
This is a triangular matrix. It's really useful to know you can read the eigenvalues off, they're right on the diagonal.
λ₁ = λ₂ = 3.
(A-λI)x = |0 1|x = 0
|0 0|
x₁=[1;0] , x₂= NO 2nd independent x
This is a degenerate matrix. It's only got one line of eigenvectors instead of two. It's this possibility of a repeated eigenvalue opens this further possiblity of a shortage of eigenvectors.
S⁻¹AS = Λ
Suppose we have n independent eigenvectors of A , put them in columns of S.
S is the eigenvector matrix.
⎡ | | | ⎤ ⎡ | | | ⎤
AS = ⎢ x₁ x₂ ... xn ⎥ = ⎢λ₁x₁ λ₂x₂ ... λnxn ⎥.
⎢ | | | ⎥ ⎢ | | | ⎥
⎣ | | | ⎦ ⎣ | | | ⎦
Each time A multiply eigenvectors , the eigen value comes out.
⎡ | | | ⎤ ⎡ | | | ⎤ ⎡λ₁ ⎤
AS = ⎢λ₁x₁ λ₂x₂ ... λnxn⎥ = ⎢ x₁ x₂ ... xn ⎥ ⎢ λ₂ ⎥.
⎢ | | | ⎥ ⎢ | | | ⎥ ⎢ ... ⎥
⎣ | | | ⎦ ⎣ | | | ⎦ ⎣ λn⎦
If I want a number to multiply x, then I can do it by puting xᵢ in column i (I get S back again), and multiply by a diagonal matrix.
AS = SΛ.
Provided my assumption of n independent eigenvectors, I multiply S⁻¹ on the left , I got
S⁻¹AS=Λ.
if I multiply S⁻¹ on the right , I got
A=SΛS⁻¹.
Can I just begin to use that ? For example how about A² ? What's eigenvectors and eigenvalues of A² ?
If Ax = λx
A²x = λAx = λ²x.
So the eigenvalues of A² are λ², and the eigenvector is the same x as A.
This is one way to do it .
Now let me see that also from formula A=SΛS⁻¹.
A²x = SΛS⁻¹·SΛS⁻¹x = SΛ²S⁻¹. It's telling me the same thing that I just learned here, but in a matrix form. It's telling me that the S is the same, the eigenvectors are the same; but the eigenvalues are squared.
Aᵏ = SΛᵏS⁻¹ .
Eigenvalues and eigenvectors give a great way to understand the powers of a matrix.
Theorem: Aᵏ→0 as k→∞ if all |λᵢ|<1 .
So far I'm operationg on one assumption: I had a full set of n independent eigenvectors. If we don't have n independent eigenvectors can not diagonalize the matrix, S⁻¹ can not make sense.
A is sure to have n independent eigenvectors (and be diagonalizable) if all the λ's are different (no repeated λ).
If I have repeated λ's , I may or may not have n independent eigenvectors (think about the Identity matrix).
Start with given vector u₀ , uk+1 = Auk, calculate u₁₀₀
u₁=Au₀, uk=Aᵏu₀
The next section is gonna to solve systems of differential equations. I'm going to have derivatives.
write u₀ as the combination of eigenvectors:
u₀ = c₁x₁ +c₂x₂ + ... +cnxn
Now multiply by A :
Au₀ = c₁λ₁x₁ +c₂λ₂x₂ + ... +cnλnxn
u₁₀₀ = A¹⁰⁰u₀ = c₁λ₁¹⁰⁰x₁ +c₂λ₂¹⁰⁰x₂ + ... +cnλn¹⁰⁰xn = Λ¹⁰⁰Sc
Fibonacci Example: Fk+2 = Fk+1 + Fk
0,1,1,2,3,5,8,13, ...
Fk+2 = Fk+1 + Fk
Right now what I've got is a single equation, not a system, and it's second-order, with second derivatives. I want to get first derivatives. The way to do it is to introduce uk will be a vector:
This is my unknown.
So I'm going to get a 2x2 system, first order, instead of a scalar system, second order:
This is my system.
And what's my one step equation?
What's the eigenvalues and eigenvectors of this matrix ?
λ₁ = -0.61803, λ₂ = 1.61803 .
How fast are those Fibonacci numbers increasing ? What's controlling the growth of these Fibonacci numbers? It's the eigenvalues.
And which eigenvalue is controlling that growth? The big one.
Since u₀ = [1;0] , c₁x₁+c₂x₂ = [1;0].
F₁₀₀ ≈ c₁·(1.61803)¹⁰⁰. ( the other terms involves c₂ is ignored since it is very slow. )
- eigenvalue λ
- nxn matrix has n eigenvalues
- eigenvalue is allowed to be 0 ( i.e. projection matrix )
- sum of λ's equals the trace of matrix,
- product of λ's equals determinant of matrix.
- singular matrix must have 0 λ.
- number of 0 λ's = dimension of null space.
- repeated λ MAY or may NOT result in missing eigenvectors
- eigenvalue could be complex number.
- Symmetric matrix's eigenvalues are all real.
- eigenvector
- Eigenvectors of sysmmetric matrix are orthogonal. (doesn't all eigenvectors orthogonal )
- A matrix may have no eigenvectors. ( ? any example ? )
This section is about how to solve a system of first order, first derivative, constant coefficient linear equations. And if we do it right, it turns directly into linear algebra. The key idea is the sulutions to contant coefficient linear equations are exponentials.
And the result, one thing we will find it's completely parallel to powers of a matrix.
Example
u(0) = [1;0]
du₁/dt = -u₁+2u₂
du₂/dt = u₁-2u₂
-> A = ⎡ -1 2 ⎤ ⎣ 1 -2 ⎦
So it starts u at time 0, everything starts at u₁. And as time goes on, du₂/dt weill be positive because of that u₁ term, so flow will move into the u₂ component and it will go out of the u₁ component.
So we'll just follow that movement as time goes forward by looking at the eigenvalues and eigenvectors of that matrix.
λ₁ = 0, λ₂ = -3.
The eigen values are telling me something. λ₂ = -3 , this eigen value is going to disappear, e⁻³ᵗ. λ₁ = 0, e⁰ᵗ=1.
So I'm expecting that this solution'll have 2 parts, e⁰ᵗ and e⁻³ᵗ parts. and as time goes on, the second part'll disappear and the first part will be a steady status. ( 因为这是微分方程，所以0是steady status??? )
x₁=[2;1] , x₂=[1;-1]
Solution: u(t) = c₁eλ₁x₁ + c₂eλ₂x₂
TODO 看书。
TODO
A =
0.10000 0.01000 0.30000
0.20000 0.99000 0.30000
0.70000 0.00000 0.40000property:
- all entreis >= 0
- all columns add to 1.
The powers of Markov matrix are all Markov matrices.
Steady State: λ = 1.
Key points:
- λ = 1 is an eigenvalue
- all other |λᵢ| < 1
Remember: uk = Aᵏu₀ = c₁λ₁ᵏx₁ +c₂λ₂ᵏx₂ + ... +cnλnᵏxn
Those terms which has |λᵢ| < 1 goes to 0.
since all columns of A markov matrix add to 1, then A-I must be singular ( all columns of A-I add to 0 ) . That is , one of the eigenvalues must be 1.
Eigenvalus of Aᵀ are the same as eigenvalues of A. because det(A-λI) = det(Aᵀ-λI). (Determinant's property 10.)
application :
uk+1 = Auk , A is Markov Matrix
The populations in California and Massachusetts.
Every year, 90% people of California stays, and 10% moves to Massachusetts, while 80% people of Massachusetts stays , and 20% moves to California.
u = |u_cal |
|u_mass|
A =
0.90000 0.20000
0.10000 0.80000
after many many yeas later, where are those peoples ?
We can easily get the 2 eigenvalues : λ₁=1, λ₂=0.7.
and the eigenvector for the steady status is x₁=[2;1]. Now we can jump to infinity right now, finally , the California will have 2/3 total peoples, while Mass has 1/3 of all.
To verify:
let u₀ = [0;1000],
since u₀ = c₁x₁ +c₂x₂ = c₁[2;1] +c₂[-1;1] , we get c₁ = 1000/3.
Ak+1u₀ = c₁·1k+1[2;1] = [666.67 ; 333.33]
Projections with orthonormal basis
for any v ,
v = x₁q₁+ x₂q₂+ ... + xnqn
how to calculate x₁ quickly ? multiplied by q₁ᵀ on both side
q₁ᵀv = x₁.
This result can be achieved from the maxtix view .
Qx = v. x=Q⁻¹v = Qᵀv => x₁=q₁ᵀv
Fourier Series
f(x) =a₀ + a₁cosx + b₁sinx + a2cos2x + b₂cos2x + ...
This one's infinite, but the key property of things being orthogonal is still true for sin and cos. So it is the propery that makes Fourier series work.
Joseph Fourier realized that, hey, I could could work in function space.
Instead of a vector v, I could have a function f(x) . Instead of orthornal vectors q₁,q₂,..., I could have orthogonal functions, but infinitely many of them.
So the basis are functions , 1, cosx, sinx, cos2x, sin2x, ... , and they are orthogonal.
What does it means "funtions are orthogonal" ?
fᵀg = ∫₀2π f(x)g(x)dx = 0.
How do I get a₁? I take the inner product of everything with cos(x).
A = Aᵀ
Eignvalues / Eigenvectors
What's special about the eigenvectors ?
- The eigenvalues are REAL.
- The eigenvectors are (can be chosen) PERPENDICULAR
Usual case : A = SΛS⁻¹ Symmetric case: A = QΛQ⁻¹ = QΛQᵀ , one of the most famous theorem.
Why real eigenvalues ?
TODO
If A is a real matrix , A has real eigenvalues and perpendicular eigenvectors means A = Aᵀ.
If A is a complex matrix , it meas A = A̅ᵀ.
A = QΛQᵀ = λ₁q₁q₁ᵀ + λ₂q₂q₂ᵀ + ...
here all q are orthonoraml , and qqᵀ is a projection matrix.
Every symmetric matrix is a combination of perpendicular projection matrices.
Symmetric matrix has another property: #positive pivots == #positive eigenvalues.
Start: Positive Definite Matrices
It's symmtrix.
- All eigenvalues are positive.
- All the pivots are positive.
- all the subdeterminant is positive. (including the determinant)
The Fourier Matrix is the most important complex matrix. It's the matrix that we need in Fourier transform.
And the really special thing is the fast Fourier transform (FFT). It's being used in a thousand places. How do I mulitply fast by that matrix?
Normally, multiplications by nxn matrix would be O(n²). The FFT's idea reduces this n² down to nlog₂n.
zᵀz is no good. Doing that inner productio won't give me the right thing.
Because the length square should be positive, but complex number may make it 0 or negative.
What I really want is z̅ᵀz = |z|².
Here is a symbol to do both: zᴴz. H stands for Hermite.
Inner product of complex vector: y̅ᵀx.
Symmetric Aᵀ=A is no good if A is complex.
right version: A̅ᵀ=A. The diagonal should be real, and the other entries should be conjugate. Hermitian matrix : Aᴴ=A
A =
2 3 + 1i
3 - 1i 5 Unitary matrix: like an orthogonal matrix, nxn matrix with orthonormal columns, perpendicular unit columns, perpendicularity is computed by conjugate. Fourier matrix happens to be one of these guys.
- the 1st column fills with 1
- the 2nd column is 1, w, w², ... wⁿ⁻¹
- the 3rd column is the power of 2nd column: 1,w²,w⁴,...,w²⁽ⁿ⁻¹⁾
- more columns ...
- the last colun is 1,wⁿ⁻¹, w²⁽ⁿ⁻¹⁾, ..., w⁽ⁿ⁻¹⁾⁽ⁿ⁻¹⁾
This is a symmetric matrix , not in perfect way, and
(Fn)ij = wⁱʲ , i,j=0,...,n-1
Here, w is a special number.
wⁿ=1.
w = ei2π/n = cos 2π/n + i·sin 2π/n
w is no the unit circle of complex plane. for example ,if n = 6, then w lands on unit circle ( 1/6 circle, 60 degree ).
Where is w² ? the angle is doubled ( 2/6 circle, 120 degree )
if n =4 , wn = eiπ/2 = i .
F₄ =
1 1 1 1
1 i i² i³
1 i² i⁴ i⁶
1 1³ i⁶ i⁹
=
1 1 1 1
1 i -1 -i
1 -1 1 -1
1 -i -1 iThis matrix is so remarkable. It's the 4x4 matrix that comes into the 4 point Fourier transform. The inverse matrix will be a nice matrix also.
Those columns are orthogonal ( PS. you should take 1 column's conjugate ). They're not quite orthonormal. But I can fix it easily, they all have length 2.
F₄ = 1/2 *
1 1 1 1
1 i -1 -i
1 -1 1 -1
1 -i -1 iNow I can inverse it right away: F₄ᴴ.
So what's good? What property is it that leads to the FFT ?
Here is the idea. F₆ has a neat connection to F₃, half as big. There's a connection of F₈ to F₄. There's a connection of F₆₄ to F₃₂.
(w₆₄)² = w₃₂.
F₆₄ 也有类似上面的 F₆=DF₃P 的分解，这样就可以 64² 降低为 2(32)²+32.
D is powers of w
D =
1
w
w²
...
wⁿ⁻¹Q: what is the P ? How does recursive idea use here ?
64² -> 2(32)²+32 -> 2( 2(16)²+16 ) + 32
When I do the recursion more and more times, I get simpler and simpler factors in the middle, eventually I'll be down to 2 point or 1 point Fourier transforms. Finally I get to 6x32, that's my final count.
Conclusion: the FFT multiplies by nxn matrix, but it does it not in n² steps, but in 1/2·nlogn steps.
Now, all matrices are symmetric. my question is , is it postive definite.
- all eigen values are positive
- all determinate of submatrices are postive.
- all pivots are positive.
*xᵀAx > 0
Graphics of f(x,y) = x⃗ᵀAx⃗ = ax²+2bxy+cy²
saddle point, imagine the graph something like human legs.
A = QΛQᵀ (how to connect them ? )
If A,B are pos def , so is A+B. xᵀ(A+B)x > 0.
xᵀAᵀAx = (Ax)ᵀAx = |Ax|² >= 0.
One comment about numerial things: with a positive definte matrix, you never have to do row exchanges, you never run into unsuitably small numbers or zeroes in the pivot postion.
nxn matrices A and B are simular means : for some invertible M, B = M⁻¹AM.
Example:
S⁻¹AS = Λ , A is similar to Λ.
like, I'm putting these matrices into families, all the matrices in the family are similar to each other. The outstanding member of the family is the diagonal guy (i.e. Λ) .
suppose
A =
2 1
1 2Λ =
3 0
0 1 M =
1 4
0 1
B = M⁻¹AM =
-2 -15
1 6A,Λ,B are all similar matrices. They all have something in common. And that is they have the same eigenvalues. ( and same number of eigenvectors. )
proof:
Ax=λx (B=M⁻¹AM)
AMM⁻¹x = λx
M⁻¹AMM⁻¹x = λM⁻¹x
BM⁻¹x = λM⁻¹x , let b=M⁻¹x
Bb = λbEigenvector of B is M⁻¹(eigenvector of A).
I now have to get into the less happy possibility that the 2 eigenvalues could be the same.
BAD CASE
for example, λ₁=λ₂=4.
There are 2 families :
-
A = 4 0 0 4
- since M⁻¹AM = A
-
A = 4 1 0 4
- those matrices has only 1 eigenvector.
- more members of family
B = 5 1 -1 3
A = UΣVᵀ
- It is the final and best factorization of a matrix.
- ∑ diagonal matrix
- U,V orthogonal matrix
A can be any matrix. Any matrix has this SVD.
One thing we'll bring together is the very good family:
-
symmtric , postive , definte matrix.
- A = QΛQᵀ. Because they were symmetic , their eigenvectors were orthogonal.
- This is the SVD in case our matrix is symmetric postive definte.
-
A = SΛSᵀ.
- This is my usual one. My usual one is the eigenvectors and eigenvalues. This is no good in general because usually S isn't orthogonal.
- In the symmetric case , the eigenvectors are orthogonal, so my ordinary S has become Q. And
- In the positive definite case , the ordinary Λ become positive Λ.
What am I looking for now?
Av₁=u₁. v₁ in row space gets taken over to u₁ in column space.
In SVD, what I'm looking for is an orthogonal basis in row space that gets knocked over into an orthogonal space in columm space.
I'm not only going to make these orthogonal, but also make them orthonormal.
σ₁u₁=Av₁
σ₂u₂=Av₂
AV = UΣ
So, this is my goal, to find an orthonormal basis in the row space(V), and an orthonormal basis in the column space(U).
A = U∑V⁻¹ = U∑Vᵀ
Now I have 2 orthogonal matrices here, And I don't want to find them both at once. So I want to cook up some expression that will make the Us disappear and leave me only the V.
It's the same combination that keeps showing up whenever we have a general rectangular matrix:
AᵀA = V∑ᵀUᵀU∑Vᵀ = V∑²Vᵀ
Now Us are out of the picture now. I'm only having to choose the Vs, and what are these Vs? And what are these ∑s ?
They're the eigenvectors and eigenvalues for the matrix AᵀA.
How I going to find the Us ? One way would be to look at AAᵀ.
So the overall picture is , the Vs are the eigenvectors of AᵀA , and Us are the eigenvectors of AAᵀ. The σs are the positive square roots of eigenvalue of AᵀA ?
Example
A =
4 4
-3 3
AᵀA =
25 7
7 25v₁ = [1/√2;1/√2] , v₂ = [1/√2, -1/√2]
σ₁ = 32 , σ₂ = 18
So
V =
1/√2 1/√2
1/√2 -1/√2
∑ =
√32 0
0 √18AAᵀ =
32 0
0 18u₁ = [1;0] , u₂ = [0;-1]
The eigenvalues are the same as AᵀA.
T(v+w) = T(v)+T(w)
T(cv) = cT(v)
In linear transformation, zero vector can not move. T(0) = 0 .
Example: Matrix multiplication
T(v) = Av
This idea of a linear transformation is like kind of the abstract description of matrix multiplication. And what's our goal here? Our goal is to understand linear transformations, and the way to understand them is to find a matrix that lies behind them. That's really the idea.
Information needed to know T(v) for all inputs:
If I know what the transformation does to every vector in a basis, then I know everything.
Construct matrix A that represents linear Transformation T.
JPEG , it changes the basis
standard basis:
[1;0;0...;0], [0;1;0...;0], [0;0;0...;1]
better basis:
[1;1;1,...;1] , very useful for solid image(i.e. a black image)
[1;1;1,...-1;-1;-1] , half dark , half light
[1;-1;1;-1;...1;-1;1;-1] , checkerboard
Those basis are all part of the
Fourier basis (8x8 is better)
signal
|
lossless | change basis
↓
coeffs c
|
lossy | compress
↓
coeffs ĉ (many zeros)
|
|
↓
x̂ = ∑ĉᵢvᵢ
What will happen at the compression step?
One thing we could do is just throw away the small coefficients. That is called thresholding.
Probably, there is enough of this vector of all 1s we very seldom throw that away. Usually,its coefficient will be large.
But the coefficient of something like the 'checkerboard' that quickly alternative vector, there's probably very little of that in any smooth signal.
x̂: this sum doesn;t have 64 terms any more. Probably it has about 2 or 3 terms. That's the kind of compression you are looking for.
let's call the input signal p , what is the coefficients c ? c = M⁻¹p
This shows the critical point. A good basis has a nice,fast inverse.
- Properties of good basis
- fast Fourier basis has FFT.
- Few is enough.
- A few basis vectors are enough to reproduce the image.
JPEG 2000 will include Wavelet basis.
珍妮弗's story
The very best basis is the eigenvector basis.
λ₁ 0 0
0 λ₂ 0
0 0 0
...
0 0 λn
So that's the perfect basis, that's the basis we'd love to have for image processing.
But to find the eigenvectors of our pixel matrix would be too expensive. So we do something cheaper and close which is to choose a good basis like wavelets.
2-sided inverse : AA⁻¹ = I = A⁻¹A
Left Inverse: If A is full column rank(r=n) rectangle matix , (AᵀA) is a good matrix, (AᵀA)⁻¹Aᵀ is A's left inverse.
A rectangular matrix can't have a 2-sided inverse.
If I multiply the left inverse on the wrong side A(AᵀA)⁻¹Aᵀ , it is a projection matrix. It is the projection onto the column space. It's trying to be the identity matrix which is an impossible job.
Right Inverse: r=m , (AAᵀ) is good matrix. Aᵀ(AAᵀ)⁻¹ is A's right inverse.
If I multiply the right inverse on the wrong side, Aᵀ(AAᵀ)⁻¹A is a projection matrix too, it is the projection on the row space.
Ax = b , row space, column space one to one mapping.
If x≠y both in row space, then Ax ≠ Ay.
Proof: since x,y in row sapce, x-y is also in row space. Suppose Ax=Ay , then A(x-y) = 0. That is, x-y also in nullspace. x-y should be the zero vector, that is x=y.
From the row space to the column space, it we limited it to those 2 spaces , and then its inverse, called pseudo-inverse. A matrix A is really a nice,invertible mapping from row space to columns space.
Find the Pseudo Inverse A⁺
- Start from SVD : A=U∑Vᵀ
- ∑∑⁺ , (mxm), trying to be I, projection on column space
- ∑⁺∑ , (nxn), trying to be I, projection on row space
- A⁺ = V∑⁺Uᵀ