Matrix Operations and Properties Quiz

CS-573 Optimization Methods - Lecture 2: Linear Algebra Primer

• Course: CS-573 Optimization Methods
• Lecture: 2 - Linear Algebra Primer
• Instructor: Grigorios Tsagkatakis
• Academic Year: Fall 2024

Mathematical Structures

• Scalar: A single number (e.g., 5)
• Vector: An ordered list of numbers (e.g., [5, 3, 8])
• Matrix: A rectangular array of numbers arranged in rows and columns (e.g., a 2x3 matrix)
• 3rd-order Tensor: A 3-dimensional array
• 4th-order Tensor: A 4-dimensional array
• One-way: a single aspect of a dataset (e.g., height)
• 2-way: two aspects of a dataset (e.g., sex and height)
• 3-way: three aspects (e.g., sex, height, weight)
• Multiway Analysis (High-order tensors): using datasets wtih more than 2 aspects
• Univariate: single numerical variable
• Multivariant: handling datasets with multiple numerical variables

Vectors

• Column vector: A vector written vertically (e.g., [v₁, v₂, ..., v_n]^T) where v_i are elements.
• Row vector: A vector written horizontally (e.g., [v₁,v₂,...,v_n]) which is just the transpose of a column vector.
• Transpose: The operation of changing a row vector to a column vector (denoted by ^T).

Examples

• Example 1 (Bag-of-words): Representing text documents by counting word frequencies. e.g., "A vector is a vector, of elements" counts words that occur within the text
• Example 2 (Time series): A sequence of numerical values at different points in time and is shown as a vector e.g., A sequence of closing prices of a stock market index at times k=1 to k=T, which creates a T-dimentional vector
• Example 3 (Images): Representing an image as a vector by arranging the pixel values in an ordered way.

Linear Combinations

• Linear combinations are formed by summing a set of vectors weighted by scalars. e.g., β₁a₁ + ...+ β_ma_m.
• The coefficients β_i are the weights to be applied.

Vector Spaces

• A vector space consists of vectors and operations such as vector addition and scalar multiplication that satisfy certain properties. These spaces can be defined for tuples of real numbers, as well as single-variable polynomials.

Subspaces and Span

• A subspace V of a vector space X contains all the linear combinations of its vectors.
• The span of a set of vectors (S) is the subspace that is generated by all the possible linear combinations of vectors from set S.

Norms

• A norm is a function that satisfies specific properties, such as non-negativity, triangle inequality and homogeneity.
• Common norms include L₂ (Euclidean), L₁, and infinite norm.
• The Frobenius norm is a matrix norm.

Inner Product between Vectors

• The inner product (or dot product) of two vectors gives a single number, the magnitudes of the two vectors and cosine of the angle between them. e.g., a ^T b = a₁b₁ + a₂b₂+...+ a_nb_n
• This concept relates vector magnitudes and angles between two vectors.

Inner Product Spaces

• An inner product defines how vectors in a space relate to each other via an inner product operator. e.g., (x , y)
• The inner product defines a norm, allowing for a measurement of the length/magnitude of a vector e.g., ||x|| =√(x, x)

Angle between Vectors

• The cosine of the angle θ between two vectors x and y is given by cos(θ) = (x^Ty) / (||x|| ||y||)
• Orthogonal vectors have an angle of 90° between them, and their inner product is zero.

Applications of Inner Products

• Cosine Similarity is a measure of similarity between two non-zero vectors, commonly used in information retrieval and text mining. It's based on the inner product of the two vectors.

Linear Dependence and Independence

• A set of vectors is linearly dependent if one vector can be expressed as a linear combination of the other vectors from the same set.
• A set of vectors that is dependent can be solved if a system can be formed with the same set.
• A set of vectors is linearly independent if one vector can't be expressed as a linear combination of the other vectors from the same set.

Basis

• A basis of a vector space is a minimal set of vectors that can generate all vectors in that space, using linear combinations.
• A vector in a subspace can be written as a linear combination of the basis vectors from the subspace.

Orthonormal Vectors

• A set or collection of vectors from a vector space are orthonormal if each vector is mutually orthogonal and has unit length.

Orthonormal Expansion

• If {a1, a2,..., an } is an orthonormal basis, any n-vector x can be expressed as a linear combination of the basis vectors (orthonormal expansion).

Orthogonal Complement

• The orthogonal complement S^⊥ of a subspace S in an inner product space X is the set of all vectors that are orthogonal to every vector in S.

Projections

• The projection of a vector x onto a given set S, denoted π_S(x) , is the point in S that is closest to x.

Theorem 2 (Projection Theorem)

• For any vector x ∈ X and subspace S⊆X , there exists a unique vector x* ∈ S which is closest to x.
• The vector x* is the projection operator for x.

Orthogonal Projections

• The orthogonal projection of a vector onto a vector or subspace in an inner product space, can be obtained by projecting the vector onto the vector or subspace.

Flop Counts

• Flop counts are used to measure the rate at which the operations of addition and multiplication of vectors, and matrices occur.
• The number of arithmetic operations an algorithm takes with respect to the dimensions of the input, is the order of the complexity of the algorithm.
• Computer speed can vary by a factor of 100.

Superposition and Linear Functions

• A function f that maps elements in a vector space to numbers is linear if it satisfies the superposition/distributive property for the operation x and y, and scalar multiples (a and β). e.g., f(ax + βy)=af(x) + βf(y).

The Inner Product Function

• The inner product function f in an n-dimensional space is linear and consists of a weighted sum of the entries in x

Affine Functions

• An affine function is a function that is linear plus a constant (b).
• The functions obey the linearity property with an added constant term: f(x) = Ax + b.

Matrix Operations (Addition, Scaling, Multiplication)

• Matrices can be added, scaled, and multiplied, with special rules and caveats about the type of matrices, and size.
• Matrix Multiplication includes important rules about the dimensions of the operands and the resulting matrices

Matrix Operations (Trace, Properties)

• Trace(A) is the sum of the diagonal elements of square matrix A
• Properties like tr(AB)=tr(BA) apply.

Special Matrices

• The properties of particular matrix types such as identity matrices, diagonal matrices, symmetric matrices, and skew-symmetric matrices are defined.

Matrix-vector Product Function

• The matrix vector product is a calculation that can be done by multiplying each row of the matrix by each column of the vector.
• Matrix-vector multiplication is computationally efficient.

Examples

• Examples of matrix operations, such as the matrix vector product and various mathematical operations (e.g. reversal, running sum) and how they can be represented as matrix operations.

Range, Rank, Nullspace

• These concepts define subsets of the column space that are important during projections.

Determinants

• The determinant is a value associated with a square matrix.
• Determinants can be calculated from the linear combination of the rows or columns of a matrix.
• Geometrically, the absolute value of the determinant of a transformation matrix can be viewed as the area/volume scaling caused by the transformation.

Matrices as Linear Maps

• Matrices can be viewed as linear functions, mapping vectors from a "input" space to an "output" space. e.g., This happens when y = Ax.

Inverse Problems

• Inverse Problems deal with finding parameters (e.g., x) based on output y in a system where the relationship between the input (e.g., x ) and output (e.g., y) is given by a linear map represented by a matrix A.

Types of Inverse Problems

• Deblurring, deconvoluting, MRI reconstruction, source localization, astrophysics, and climate modeling are some fields that use inverse problems.

Matrix Inverse

• The inverse of a matrix, A^-1 exists only if the determinant of A is nonzero.
• For square matrices, the inverse of a matrix can be obtained by a process of matrix inversion.
• This inverse matrix can be used to solve linear systems.

Systems of Linear Equations

• These concepts concern systems (sets) of linear equations in multiple variables which can be viewed as linear functions and related to the matrix multiplication concept
• Systems can have no solution, one solution, or multiple solutions e.g. depending on the coefficient matrix A and vector b).

Left Inverse

• If a matrix X exists to satisfy XA=I, then we call this the left inverse of A.

Right Inverse

• A right inverse of a matrix A is represented by the matrix X, such that AX = I.

Generalized Inverse

• The generalized inverse of a square or non-square matrix A, which exists when A is invertible, satisfies the property A†A = I is denoted by A†.

Least Squares Problem

• The least squared solution for a system Ax = b has a solution  that minimizes ||Ax-b||2, where x is an n-vector that minimizes the objective function.
• If the columns of A are linearly independent, the solution will be x = (A^TA)^-1A^Tb.

Test your knowledge on various types of matrices and their operations in this quiz. Explore concepts such as standard matrix multiplication, inverses, and the Hadamard product. Perfect for students studying linear algebra or advanced mathematics.