profile pic
⌘ '
raccourcis clavier
Search

linalg review

  • Étiquette

    • publié à

    • modifié à

    • durée

      3 min de lecture

    • source

      llms.txt

    See also matrix cookbook

    matrix representation of a system of linear equations

    x1+x2+x3=5x1−2x2−3x3=−12x1+x2−x3=3\begin{aligned} x_1 + x_2 + x_3 &= 5 \\ x_1 - 2x_2 - 3x_3 &= -1 \\ 2x_1 + x_2 - x_3 &= 3 \end{aligned}

    Equivalent matrix representation of Ax=bAx = b

    A=[1111−2−321−1]x=[x1x2x3]b=[5−13]∵A∈Rm×n,x∈Rn,b∈Rm\begin{aligned} A &= \begin{bmatrix} 1 & 1 & 1 \\ 1 & -2 & -3 \\ 2 & 1 & -1 \end{bmatrix} \\ x &= \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \\ b &= \begin{bmatrix} 5 \\ -1 \\ 3 \end{bmatrix} \end{aligned} \because A \in R^{m \times n}, x \in R^n, b \in R^m

    Transpose of a matrix

    A∈Rm×nA \in R^{m \times n} and AT∈Rn×mA^T \in R^{n \times m}

    dot product.

    ⟨x,y⟩=∑i=1nxiyi=∑i=1nxi⋅yi\begin{aligned} \langle x, y \rangle &= \sum_{i=1}^{n} x_i y_i \\ &= \sum_{i=1}^{n} x_i \cdot y_i \end{aligned}

    linear combination of columns

    Let A∈Rm×nA \in R^{m \times n}, X∈RnX \in R^n, Ax∈RnAx \in R^n

    Then Ax=∑i=1n⟨ai⟩xi∈RnAx = \sum_{i=1}^{n}{\langle a_i \rangle} x_i \in R^n

    inverse of a matrix

    The inverse of a square matrix A∈Rn×nA \in R^{n \times n} is a unique matrix denoted by A−1∈Rn×nA^{-1} \in \mathbb{R}^{n\times{n}}

    A−1A=I=AA−1A^{-1} A = I = A A^{-1}

    euclidean norm

    L2L_{2} norm:

    ∥x∥2=∑i=1nxi2=XTX\| x \|_{2} = \sqrt{\sum_{i=1}^{n}{x_i^2}} = X^TX

    L1 norm: ∥x∥1=∑i=1n∣xi∣\| x \|_{1} = \sum_{i=1}^{n}{|x_i|}

    L∞L_{\infty} norm: ∥x∥∞=max⁡i∣xi∣\| x \|_{\infty} = \max_{i}{|x_i|}

    p-norm: ∥x∥p=(∑i=1n∣xi∣p)1/p\| x \|_{p} = (\sum_{i=1}^{n}{|x_i|^p})^{1/p}

    Comparison

    ∥x∥∞≤∥x∥2≤∥x∥_1 \|x\|_{\infty} \leq \|x\|_{2} \leq \|x\|\_{1}

    One can prove this with Cauchy-Schwarz inequality

    linear dependence of vectors

    Given {x1,x2,…,xn}⊆Rd\{x_1, x_2, \ldots, x_n\} \subseteq \mathbb{R}^d and α1,α2,…,αn∈R\alpha_1, \alpha_2, \ldots, \alpha_n \in \mathbb{R}

    ∀i∈[n],∀{a1,a2,…,an}⊆Rd s.t. xi≠∑j=1najxj\forall i \in [ n ], \forall \{a_1, a_2, \ldots, a_n\} \subseteq \mathbb{R}^d \space s.t. \space x_i \neq \sum_{j=1}^{n}{a_j x_j}

    Span

    Given a set of vectors {x1,x2,…,xn}⊆Rd\{x_1, x_2, \ldots, x_n\} \subseteq \mathbb{R}^d, the span of the set is the set of all possible linear combinations of the vectors.

    span({x1,x2,…,xn})={y:y=∑i=1nαixi∣αi∈R}\text{span}(\{x_1, x_2, \ldots, x_n\}) = \{ y: y = \sum_{i=1}^{n}{\alpha_i x_i} \mid \alpha_i \in \mathbb{R} \}

    If x1,x2,…,xnx_{1}, x_{2}, \ldots, x_{n} are linearly independent, then the span of the set is the entire space Rd\mathbb{R}^d

    Rank

    For a matrix A∈Rm×nA \in \mathbb{R}^{m \times n}:

    • column rank: max number of linearly independent columns of AA
    • row rank: max number of linearly independent rows of AA

    If rank(A)≤m\text{rank}(A) \leq m, then the rows are linearly independent. If rank(A)≤n\text{rank}(A) \leq n, then the columns are linearly independent.

    rank of a matrix AA is the number of linearly independent columns of AA:

    • if AA is full rank, then rank(A)=min⁡(m,n)\text{rank}(A) = \min(m, n) (rank(A)≤min⁡(m,n)\text{rank}(A) \leq \min(m, n))
    • rank(A)=rank(AT)\text{rank}(A) = \text{rank}(A^T)

    solving linear system of equations

    If A∈RnA \in \mathbb{R}^{n} is invertible, there exists a solution:

    x=A−1bx = A^{-1}b

    Range and Projection

    Given a matrix A∈Rm×nA \in \mathbb{R}^{m \times n}, the range of AA, denoted by R(A)\mathcal{R}(A) is the span of columns of AA:

    R(A)={y∈Rm∣y=Ax∣x∈Rm}\mathcal{R}(A) = \{ y \in \mathbb{R}^m \mid y = Ax \mid x \in \mathbb{R}^m \}

    Projection of a vector y∈Rmy \in \mathbb{R}^m onto span({x1,⋯ ,xn})\text{span}(\{x_1, \cdots, x_n\}), xi∈Rmx_i \in \mathbb{R}^m is a vector in the span that is as close as possible to yy wrt l2l_2 norm

    Proj(y;{x1,⋯ ,xn})=arg min⁡v∈span({x1,⋯ ,xn})∥y−v∥2\text{Proj}(y; \{x_{1}, \cdots, x_n\}) = \argmin_{{v \in \text{span}(\{x_1, \cdots, x_n\})}} \| y - v \|_2

    Null space of AA

    is the set of all vectors that satisfies the following:

    N(A)={x∈Rn∣Ax=0}\mathcal{N}(A) = \{ x \in \mathbb{R}^n \mid Ax = 0 \}

    Vous pourriez aimer ce qui suit

  • Will to Truth
  • Fork and threads
  • Time response
  • Will
  • Nous
  • Non-linear Optimization
  • SQL and Relational Algebra
    • Cauchy-Schwarz
    useful for derive upper bounds, e.g when analysing the error or convergence rate of an algorithm format for all vectors v and v of an inner product space, we have \mid \langle u, v \rangle ...
    Vector space
    Not to be confused with vector field, but a vector space is a set whose vectors can be scaled by any given scalars A vector space have all basic properties of a set, including associative, ...
    sparse autoencoder
    abbrev: SAE see also: landspace Often contains one layers of MLP with few linear ReLU that is trained on a subset of datasets the main LLMs is trained on ...
    Supervised machine learning
    See also: book probability density function if X is a random variable, the probability density function (pdf) is a function f(x) such that: P(a \leq X \leq b) = \int_{a}^{b} f(x) dx ...
    State space representation
    See also sides time-domain technique \begin{align} \dot{x} &= Ax + Bu \\\ y &= Cx + Du \end{align} linearly independent State vector: x = [x_{1},x_{2},\ldots, x_{n}]^{T} ...