Appunti Scientific Computing - Parte I

T

A rank(A) = n A A

square non-singular matrix, admitting the computation of an inverse matrix.

Special kind of matrices

#sparse-matrix #density #sparsity

These kind of matrices are sparse matrices, implying that most entries are equal to 0,

and they can be stored, in memory, in more effective ways.

For a matrix it's possible to define two measures: density and sparsity.

If we consider a generic matrix and we call nnz the number of non-zero elements,

m ∗ n

we have that: nnz m ∗ n − nnz

d = , s = 1 − d =

m ∗ n m ∗ n

Toeplitz matrix

#toeplitz

It's a special kind of matrix with equal entries along the diagonals:

Orthogonal matrix

#orthogonal-matrix

A square matrix is orthogonal if both its rows and columns are orthogonal and

Q

orthonormal (of unit length). This leads to have that:

T T T −1

Q Q = I = QQ , Q = Q

An example is given by considering a rotation matrix in .

2

R

Now, consider instead a non-square matrix with orthogonal and orthonormal rows

W

and columns. As it is not a squared matrix, is not an orthogonal matrix. So:

W

T

W W = I

but, at the same time: T

WW ≠ I

and is the orthogonal projector into the range of (see Range of a matrix, 3.

T

WW W

Norms > Orthogonal Projections).

Properties of orthogonal matrices

1. They preserve length after multiplication, so: ;

∥Qx∥ = ∥x∥

2 2

2. The product between two orthogonal matrices is still an orthogonal matrix;

3. Invariance of the scalar product ( invariance of the angle between two vectors),

⇒

so: (see 1. Basic Operations > Matrix-vector product, 1. Basic

T T

(Qx) ⋅ (Qy) = x y

Operations > Scalar Product). Proof:

T T T T T

(Qx) ⋅ (Qy) = x Q Qy = x Iy = x y

4. The product between an orthogonal matrix and a vector is a rotation.

Norms

3. Norms

#linear-algebra #norms

Vector norms

Cosine similarity

Orthogonal Projections

Matrix norms

Vector norms

A function, to be considered as a norm, must satisfy these properties:

x ≠ 0 ⟺ ∥x∥ > 0; ∥0∥ = 0

∥cx∥ = |c| ⋅ ∥x∥

∥x + y∥ ≤ ∥x∥ + ∥y∥ (triangular inequality)

We have an infinite number of norms, but we will consider just:

1. 1-norm: ∥x∥ = ∑ |x |

1 i

2. 2-norm: 2 1/2

∥x∥ = (∑ x )

2 i

3. p-norm: p 1/p

∥x∥ = (∑ x )

p i

4. infinite-norm: ∥x∥ = max (|x |)

∞ i

i

The following image shows as the value of the norm decreases as the order of the norm

itself increases.

The set of vectors whose norm is less or equal than 1, defines the unit spehres.

Cosine similarity

#cosine-similarity

The 1. Basic Operations > Scalar Product can also be computed using the 2-norms:

T T

x y = y x = ∥x∥ ⋅ ∥y∥ ⋅ cos(α)

2 2

By this, we can see that two vectors and are orthogonal when their scalar product is

x y

null. So: T

x y = 0 ⟺ x ⊥ y

Also, we can use this property to see how much two vectors are different, just by

considering the cosine similarity: T

x y

cos(α) = ∥x∥ ⋅ ∥y∥

2 2

In this way, when the two vectors are orthogonal, they are the most different, implying

that they do not share any kind of informations. At the same time, when the cosine

similarity is equal to 1, it is implied the maximum similarity and, when it's equal to -1, it is

implied the maximum similarity but in the opposite direction.

Orthogonal Projections

The definition of the scalar product in terms of the norm can be used to easily compute

the length of the orthogonal projection: T

x y

→

oa = ∥x∥ ⋅ cos(α) =

2 ∥y∥ 2 →

This can be used to determine the vector as it is equal to lenght times the versor of

a oa

.

y

(Remind: a versor can be obtained by multiplying each component of the vector itself by

its norm). T

y x y

→

a = oa ∗ = y

2

∥y∥ ∥y∥

2 2

When we want to know the projection of a certain vector into the direction of a certain

x

versor then we need to compute:

y, T

a = yy x

where is a matrix (recall 1. Basic Operations > Outer product) called orthogonal

T

yy

projector.

Matrix norms

Norms can be computed also for matrices. For matrix, we can define the norms in terms

of a vector norm, i.e.: ∥A∥ = max ∥Ax∥

∥x∥=1

which means that the norm of the matrix is given by searching for the versor that

x

maximizes the norm of that product (recall that the 1. Basic Operations > Matrix-vector

product gives a vector in output).

Another way to compute the matrix norm is through the use of the Frobenius norm:

2

√

∥A∥ = ∑ ∑ |a |

F ij

Recap of Linear Systems

4. Linear system of equations

#linear-algebra #linear-systems #least-squares

Introduction

Overdetermined linear system of equations

Introduction n∗n

Ax = b, A ∈ R

A linear system of equations can be easily solved by means of factorization

LU

(gaussian elimination with partial pivoting). This implies that:

Ax = LUx = Pb, PA = LU

Lp = Pb, Ux = p

3

This method has a complexity of and it's guaranteed to give a small residual (=

n

O( )

3

).

b − Ax

Overdetermined linear system of equations

#norms #linear-systems #rank #range #least-squares

Consider that: m∗n n m

A ∈ R , x ∈ R , b ∈ R , m > n

As the number of known terms is higher than the number of the unknown terms, we talk

about overdetermined linear system.

In this situation, a solution for the linear system exists if and only if

Ax = b b ∈ R(A)

(first interpretation of 2. Matrix Properties > Range of a matrix). We are saying that to

obtain a solution we need to find a vector with witch is possible to define a space

x

where the vector lies. Since a solution rarely exists, we have to determine some kind

b

of pseudo solution. To get this pseudo solution, we can search for a vector such that

x

the residual is minimized. So:

min ∥r∥ = min ∥b − Ax∥ = min ∥Ax − b∥

x x x

The vector is called solution, in the chosen norm sense, of the ovedetermined

x

system 3. Norms. If the 2-norm is chosen, then we have a Least Square (LS) problem:

x = min ∥Ax − b∥

LS 2

x

The set of LS solutions is a convex set. For this reason, the set can be easily

X X

computed as: T T T

x ∈ X ⇒ A Ax = A b ⇒ A (Ax − b) = 0

where this equation means that we want to search for a residual that is orthogonal to any

column of the matrix .

A

The set admits only one solution when the rank of the matrix is equal to :

X A n

X = x ⟺ rank(A) = n

LS

is the orthogonal projection of the vector onto the range of the matrix (recall

Ax b A

LS

3. Norms > Orthogonal Projections).

If , it is implied that the inverse matrix can be computed. In this way, we simply

m = n

have that (recalling that ):

−1

A A = I −1 −1

A Ax = A b

However, when the system is overdetermined, the matrix cannot be squared and,

A

therefore, the inverse does not exist. However, we can still solve the problem just by

considering the pseudo-inverse: †

x = A b

LS

If , then the pseudo-inverse can be computed as (2. Matrix Properties >

rank(A) = n

Properties of rank matrix): † T −1 T

A = (A A) A

Then, the system can be rewritten as: †

Ax = AA b

LS

and, again, is the orthogonal projection of onto the range of and, by

Ax b A

LS

consequence, is the projector onto the range of .

†

AA A

Note that this problem can be solved by:

1. 5. QR Factorization

2. 6. SVD Factorization

The following image summarize the least squares pseudo-inverses considering the

regular equation and both QR and SVD factorization methods:

Factorization

QR Factorization

5. QR Factorization

#qr-factorization #orthogonal-matrix #triangular-matrix #null-space #range #rank

Introduction

Applications of QR factorization

​ Determined linear system through QR factorization

Overdetermined linear system through QR factorization

Householder reflector

Application of QR factorization to information retrieval system

Introduction

The goal is to rewrite a matrix as the product between two other matrices. So, we

A

want to do a factorization. In particular, we consider:

A = QR

where is orthogonal (2. Matrix Properties > Orthogonal matrix) and is upper

Q R

triangular.

with: m∗n m∗m m∗n

A ∈ R , Q ∈ R , R ∈ R

Consider the second interpretation of the 1. Basic Operations > Matrix-Matrix product.

So: a = Qr

j j

which means that is a basis for the range of and that the columns of are a linear

Q A A

combination of the columns of .

Q

QR factorization can also be applied in a reduced form. Consider the following image:

Here, we are considering only the first n columns (with ) and only them are the

m > n

orthogonal basis for the range of . In this way, the matrix becomes a triangular

A R

square matrix of size n.

Thanks to the property of the QR factorization, if , then it is also true that

rank(A) = r

. This implies that the last rows of are zero vectors.

rank(R ) = r n − r R

n n

So, by consequence, we can consider just the reduced QR factorization given by:

A = Q R

r r

Combining all these information, we have that if is the rank of the matrix , then the

r A

first columns of are the orthonormal basis for the range of , while the remaining

r Q A

columns are the orthogonal vectors of the null space of (see 2. Matrix Properties >

T

A

Null space).

Applications of QR factorization

Determined linear system through QR factorization

#linear-systems #least-squares

QR factorization can be used to solve linear systems (see 4. Linear system of

equations). Consider the simple case where is a square matrix, so:

A

Ax = b ⇒ QRx = b

and, by posing , we get that:

y = Rx T

Qy = b ⇒ y = Q b

Overdetermined linear system through QR factorization

Now, consider a more complex scenario, where the system is overdetermined (see 4.

Linear system of equations > Overdetermined linear system of equations). Even this

problem can be solved by means of QR factorization. As we are considering that the

matrix is full rank, we talk about LS full rank problem.

A

As we recall, the LS problem is defined as:

min ∥Ax − b∥ 2

x

but we can rewrite this expression just by multiplying the residual by :