CS-573 Optimization Methods Lecture Notes Fall 2024 PDF

CS-573 Optimization Methods Lecture 2: Linear Algebra primer Grigorios Tsagkatakis Fall 2024 CS-573 Optimization Methods 1 Mathematical structures Fall 2024 CS-573 Optimization Methods 2 Mathematical structures Fall 2024...

CS-573 Optimization Methods Lecture 2: Linear Algebra primer Grigorios Tsagkatakis Fall 2024 CS-573 Optimization Methods 1 Mathematical structures Fall 2024 CS-573 Optimization Methods 2 Mathematical structures Fall 2024 CS-573 Optimization Methods 3  Vectors A column vector where A row vector where denotes the transpose operation Fall 2024 CS-573 Optimization Methods 4 Examples Fall 2024 CS-573 Optimization Methods 5 Examples Fall 2024 CS-573 Optimization Methods 6 Examples Fall 2024 CS-573 Optimization Methods 7 Examples Fall 2024 CS-573 Optimization Methods 8 Linear combinations Fall 2024 CS-573 Optimization Methods 9 Example Fall 2024 CS-573 Optimization Methods 10 Vector spaces Fall 2024 CS-573 Optimization Methods 11 Subspaces and span Fall 2024 CS-573 Optimization Methods 12 Norms Fall 2024 CS-573 Optimization Methods 13 Norms L2 norm, also known as Euclidean norm L1 norm Infinite norm (or max norm) Frobenius norm (Matrix norm) Fall 2024 CS-573 Optimization Methods 14 Inner product between vector Fall 2024 CS-573 Optimization Methods 15 Inner product spaces Fall 2024 CS-573 Optimization Methods 16 Angle between vectors Fall 2024 CS-573 Optimization Methods 17 Applications of inner products Cosine Similarity: Used in information retrieval and text mining, cosine similarity measures the cosine of the angle between two non-zero vectors. It's a measure of similarity between two vectors, with a value between - 1 and 1. The formula for cosine similarity is based on the inner product: 𝑎𝑏 𝑠𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑡𝑦 = 𝑎 𝑏 https://colab.research.google.com/drive/1v3baNZCfDxasNsue1zKM7 d2qo7Vwqtku?usp=sharing Fall 2024 CS-573 Optimization Methods 18 Linear dependence Linearly dependent vectors in a plane in R2. Fall 2024 CS-573 Optimization Methods 19 Example Fall 2024 CS-573 Optimization Methods 20 Linear independence Linearly independent vectors in R3. Fall 2024 CS-573 Optimization Methods 21 Basis Fall 2024 CS-573 Optimization Methods 23 Orthonormal vectors Fall 2024 CS-573 Optimization Methods 24 Examples of orthonormal bases Fall 2024 CS-573 Optimization Methods 25 Orthonormal expansion Fall 2024 CS-573 Optimization Methods 26 Orthogonal vectors Fall 2024 CS-573 Optimization Methods 28 Orthogonal complement Fall 2024 CS-573 Optimization Methods 29 Projections Fall 2024 CS-573 Optimization Methods 30 Projections Fall 2024 CS-573 Optimization Methods 31 Orthogonal projection Fall 2024 CS-573 Optimization Methods 32 Flop counts Fall 2024 CS-573 Optimization Methods 34 Complexity of vector addition, inner product Fall 2024 CS-573 Optimization Methods 35 Superposition and linear functions Fall 2024 CS-573 Optimization Methods 36 The inner product function Fall 2024 CS-573 Optimization Methods 37...and all linear functions are inner products Fall 2024 CS-573 Optimization Methods 38 Affine functions Fall 2024 CS-573 Optimization Methods 39 Linear versus affine functions Fall 2024 CS-573 Optimization Methods 40 Mathematical structures Fall 2024 CS-573 Optimization Methods 41  Matrix A matrix is an array of numbers with size 𝑚 ↓ by 𝑛 →, i.e. m rows and n columns. If , we say that is square. Fall 2024 CS-573 Optimization Methods 42 Examples of data matrices Fall 2024 CS-573 Optimization Methods 43  Basic Matrix Operations Addition Can only add a matrix with matching dimensions, or a scalar. Scaling Fall 2024 CS-573 Optimization Methods 44 Matrix Operations Matrix Multiplication Properties distributive associative Powers We can refer to the matrix product AA as A2, and AAA as A3, etc. Only square matrices can be multiplied that way Transpose Fall 2024 CS-573 Optimization Methods 45 Matrix Operations Trace Invariant to a lot of transformations Properties: 𝑡𝑟𝑎𝑐𝑒 𝐴 = 𝑡𝑟𝑎𝑐𝑒 𝑃−1 𝐴𝑃 , 𝑤ℎ𝑒𝑟𝑒 𝑃 𝑖𝑠 𝑖𝑛𝑣𝑒𝑟𝑡𝑖𝑏𝑙𝑒 Fall 2024 CS-573 Optimization Methods 46 Special matrices Identity matrix I Diagonal matrix Symmetric matrix Skew-symmetric matrix Fall 2024 CS-573 Optimization Methods 47 Matrix-vector product function Fall 2024 CS-573 Optimization Methods 48 Examples Fall 2024 CS-573 Optimization Methods 49 Hadamard Product For two matrices, 𝐀, 𝐁, of the same dimension, 𝑚 × 𝑛 the Hadamard product, 𝐀 ∘ 𝐁, is a matrix, of the same dimension as the operands, with elements given by 𝐀∘𝐁 𝑖,𝑗 = 𝐀 𝑖,𝑗 ∙ 𝐁 𝑖,𝑗 For example the Hadamard product for a 3 × 3 matrix 𝐀 with a 3 × 3 matrix 𝐁 is: 𝐴11 𝐴12 𝐴13 𝐵11 𝐵12 𝐵13 𝐴11 𝐵11 𝐴12 𝐵12 𝐴13 𝐵13 𝐴21 𝐴22 𝐴23 ∘ 𝐵21 𝐵22 𝐵23 = 𝐴21 𝐵21 𝐴22 𝐵22 𝐴23 𝐵23 𝐴31 𝐴32 𝐴33 𝐵31 𝐵32 𝐵33 𝐴31 𝐵31 𝐴32 𝐵32 𝐴33 𝐵33 Fall 2024 CS-573 Optimization Methods 50 Kronecker Product If 𝐀 is an 𝑚 × 𝑛 matrix and 𝐁 is a 𝑝 × 𝑞 matrix, then the Kronecker product 𝐀 ⊗ 𝐁 is the 𝑚𝑝 × 𝑛𝑞 block matrix: 𝐴11 𝐁 ⋯ 𝐴1𝑛 𝐁 𝐀⊗𝐁= ⋮ ⋱ ⋮ 𝐴𝑚1 𝐁 ⋯ 𝐴𝑚𝑛 𝐁 For example, the Kronecker product for a 2 × 2 matrix 𝐀 with a 2 × 3 matrix 𝐁 is: 𝐴11 𝐵11 𝐴11 𝐵12 𝐴11 𝐵13 𝐴12 𝐵11 𝐴12 𝐵12 𝐴12 𝐵13 𝐴 𝐵 𝐴11 𝐵22 𝐴11 𝐵23 𝐴12 𝐵21 𝐴12 𝐵22 𝐴12 𝐵23 𝐀 ⊗ 𝐁 = 11 21 𝐴21 𝐵11 𝐴21 𝐵12 𝐴21 𝐵13 𝐴22 𝐵11 𝐴22 𝐵12 𝐴22 𝐵13 𝐴21 𝐵21 𝐴21 𝐵22 𝐴21 𝐵23 𝐴22 𝐵21 𝐴22 𝐵22 𝐴22 𝐵23 Fall 2024 CS-573 Optimization Methods 51 Matrix-vector product function Fall 2024 CS-573 Optimization Methods 52 Examples Fall 2024 CS-573 Optimization Methods 53 Range, rank, and nullspace Fall 2024 CS-573 Optimization Methods 54 Determinants Fall 2024 CS-573 Optimization Methods 56 Determinants Fall 2024 CS-573 Optimization Methods 57 Matrices as linear maps Fall 2024 CS-573 Optimization Methods 58 Inverse problems Formulation Objective, given 𝑦 and knowledge about 𝐴, recover 𝑥 Fall 2024 CS-573 Optimization Methods 59 Types of inverse problems Deblurring/deconvolution MRI reconstruction Source localization Astrophysics Climate modeling Fall 2024 CS-573 Optimization Methods 60 Types of inverse problems Fall 2024 CS-573 Optimization Methods 61 Types of inverse problems Fall 2024 CS-573 Optimization Methods 62 Types of inverse problems Fall 2024 CS-573 Optimization Methods 63 Matrix Inverse Fall 2024 CS-573 Optimization Methods 64 System of linear equations Fall 2024 CS-573 Optimization Methods 65 Systems of linear equations Fall 2024 CS-573 Optimization Methods 66 Systems of linear equations Fall 2024 CS-573 Optimization Methods 67 Left inverse Fall 2024 CS-573 Optimization Methods 68 Left inverse and column independence Fall 2024 CS-573 Optimization Methods 69 Solving linear equations with a left inverse Fall 2024 CS-573 Optimization Methods 70 Right inverse Fall 2024 CS-573 Optimization Methods 71 Solving linear equations with a right inverse Fall 2024 CS-573 Optimization Methods 72 Generalized inverse Fall 2024 CS-573 Optimization Methods 73 Solution of system Inverse of a matrix Solution of systems of linear equations (A-1 exists) Fall 2024 CS-573 Optimization Methods 74 Invertible matrices Fall 2024 CS-573 Optimization Methods 75 Pseudo-inverse of a tall matrix Fall 2024 CS-573 Optimization Methods 76 Pseudo-inverse of a wide matrix Fall 2024 CS-573 Optimization Methods 77 Least squares problem Fall 2024 CS-573 Optimization Methods 78 Least squares problem Fall 2024 CS-573 Optimization Methods 79 Least squares problem – column interpretation Fall 2024 CS-573 Optimization Methods 80 Least squares problem – row interpretation Fall 2024 CS-573 Optimization Methods 81 Solution of least squares problem Fall 2024 CS-573 Optimization Methods 82