Linear Algebra and Convex Optimization

Vector spaces

1. Vector spaces: a set $V$ with addition and scalar multiplication
   • Basis: a minimal set of vectors $B$ where every element in $V$ is a linear combination of $B$
   • Dimension: the number of vectors in $B$
   • Inner product: $⟨\cdot ,\cdot ⟩:V\times V\to F$
     • Conjugate symmetry: $⟨u,v⟩=\overline{⟨v,u⟩}$
     • Linearity: $⟨ax+by,z⟩=a⟨x,z⟩+b⟨y,z⟩$
     • Positive definiteness: $⟨x,x⟩>0⟹x=0$
   • Norm: function from a vector space to non-negative reals
     • Positive definiteness: $||x||=0⟹x=0$
     • Triangle inequality: $||x+y||\le ||x||+||y||$
     • Absolute homogeneity: $||\alpha x||=||\alpha ||\cdot ||x||$
2. Common vector norms:
   • L-$p$: $||x|{|}_p=(\sum _i|x_i{|}^p{)}^{\frac{1}{p}}$
   • L-$\mathrm{\infty }$: $||x|{|}_{\mathrm{\infty }}=\underset{i}{max}|x_i|$
3. Useful formulas:
   • Cauchy-Schwarz: $|⟨u,v⟩{|}^2\le ⟨u,u⟩\cdot ⟨v,v⟩$
   • Vector angle: $\text{cos }\theta =\frac{x^{T}y}{||x|{|}_2||y|{|}_2}$
   • Cardinality (# nonzero elements): $\text{card}(x)\ge \frac{||x|{|}_1^2}{||x|{|}_2^2}$
   • $\frac{1}{\sqrt{n}}||x|{|}_2\le ||x|{|}_{\mathrm{\infty }}\le ||x|{|}_2\le ||x|{|}_1\le \sqrt{n}||x|{|}_2\le n||x|{|}_{\mathrm{\infty }}$

Matrix algebra

1. Common matrix norms:
   • $p$-norm: $||A|{|}_p=\underset{x}{max}\frac{||Ax|{|}_p}{||x|{|}_p}$
     • $p=1$: max absolute column sum
     • $p=2$ (spectral): ${\sigma }_{\text{max}}(A)$
     • $p=\mathrm{\infty }$: max absolute row sum
     • Sub-multiplicative property for $p$-norm: $||AB|{|}_p\le ||A|{|}_p||B|{|}_p$
   • Nuclear: $||A|{|}_{\ast }=\sum _i^r{\sigma }_i$
   • Frobenius: $||A|{|}_F=\sqrt{\text{tr}(A^{T}A)}=\sqrt{\sum _i{\sigma }_i^2}$
2. Norm relationships for $m\times n$ matrix $A$:
   • $\frac{1}{\sqrt{n}}||A|{|}_{\mathrm{\infty }}\le ||A|{|}_2\le \sqrt{m}||A|{|}_{\mathrm{\infty }}$
   • $\frac{1}{\sqrt{m}}||A|{|}_1\le ||A|{|}_2\le \sqrt{n}||A|{|}_1$
   • $||A|{|}_2\le ||A|{|}_F\le \sqrt{r}||A|{|}_2$
3. Common matrix properties:
   • Range: the span of the columns of $A$: $\{v|v=\sum _i{c}_i{a}_i,c_i\in \mathbb{R}\}$
   • Rank: number of linearly independent columns of $A$
   • Symmetry: a matrix $A$ is symmetric if $A=A^T$
     • Hermitian: complex generalization of symmetric
   • Positive-semidefinite: if $x^{T}Ax\ge 0$ for all $x$ (PD if strict)
   • Gain: $\underset{x}{max}\frac{||Ax||}{||x||}$
   • Trace (sum of diagonal elements): $\text{tr}(A)=\sum _i{\sigma }_i$
   • Determinant: $\text{det}(A)=\prod _i{\sigma }_i$
   • Spectral radius: $\rho (A)={\sigma }_1=\underset{i}{max}|{\lambda }_i(A)|$
   • Condition number: $\kappa (A)=\frac{{\sigma }_1}{{\sigma }_n}=||A|{|}_2||A^{-1}|{|}_2$
4. Fundamental Theorem of Linear Algebra:
   • $\text{Null}(A)\oplus \text{Range}(A^T)={\mathbb{R}}^n$
   • $\text{Null}(A^T)\oplus \text{Range}(A)={\mathbb{R}}^n$

Matrix calculus

1. Gradient for function $g$:
   • Scalar ($g:{\mathbb{R}}^n\to \mathbb{R}$): $(\mathrm{\nabla }g(x){)}_i=\frac{\partial g}{\partial x_i}(x)$ (dim $n\times 1$)
   • Hessian ($g:{\mathbb{R}}^n\to \mathbb{R}$): $({\mathrm{\nabla }}^{2}g(x){)}_{ij}=\frac{{\partial }^{2}g}{\partial x_i\partial x_j}(x)$ (dim $n\times n$)
   • Jacobian ($g:{\mathbb{R}}^n\to {\mathbb{R}}^m$): $(Dg(x){)}_{ij}=\frac{\partial g_i}{\partial x_j}$ (dim $m\times n$)
2. Quotient rule: for $h(x)=\frac{n(x)}{d(x)}$, $\mathrm{\nabla }h(x)=\frac{d(x)\mathrm{\nabla }n(x)-n(x)\mathrm{\nabla }d(x)}{(d(x){)}^2}$
3. Product rule: for $g(x)=v(x)s(x)$ ($v$: vector, $s$: scalar), $Dg(x)=Dv(x)s(x)+v(x)Ds(x)$
4. Taylor’s theorem: $f(x+\mathrm{\Delta }x)=f(x)+⟨\mathrm{\nabla }f(x),\mathrm{\Delta }x⟩+\frac{1}{2}(\mathrm{\Delta }x{)}^T{\mathrm{\nabla }}^{2}f(x)\mathrm{\Delta }x+\dots$
5. Common matrix derivatives:
   • For $g(a,n)=a^{T}Xb$:
     • ${\mathrm{\nabla }}_{X}g(a,b)=a{b}^T$
     • ${\mathrm{\nabla }}_{a}g(a,b)=Xb$
     • ${\mathrm{\nabla }}_{b}g(a,b)=X^{T}a$
   • For $g(X)=\text{tr}(X^{T}A)$:
     • $\mathrm{\nabla }g(X)=A$
   • For $g(X)=\text{tr}(X^{T}AX)$ where $A$ is symmetric:
     • $\mathrm{\nabla }g(X)=2AX$
     • ${\mathrm{\nabla }}^{2}g(X)=2A$
   • For $g(X)=\text{tr}({\mathrm{\Sigma }}^{-1}X)$ where $\mathrm{\Sigma }\succ 0$:
     • ${\mathrm{\nabla }}_{\mathrm{\Sigma }}g(X)=-{\mathrm{\Sigma }}^{-1}X{\mathrm{\Sigma }}^{-1}$
   • For $g(X)=\text{tr}(X\log X)$ where $X⪰0$:
     • $\mathrm{\nabla }g(X)=\log X+I$
   • For $g(X)=||AX-B|{|}_F^2$:
     • $\mathrm{\nabla }g(X)=2A^T(AX-B)$
     • ${\mathrm{\nabla }}^{2}g(X)=2A^{T}A$
   • For $g(X)=\log detX$ where $X\succ 0$:
     • $\mathrm{\nabla }g(X)=(X^{-1}{)}^T$
     • ${\mathrm{\nabla }}^{2}g(X)=-(X^{-1}{)}^{T}dX{X}^{-1}$
   • For $g(x)=f(Ax)$ where $f:{\mathbb{R}}^m\to \mathbb{R}$ and $A\in {\mathbb{R}}^{m\times n}$:
     • $\mathrm{\nabla }g(x)=A^T\mathrm{\nabla }f(Ax)$
     • ${\mathrm{\nabla }}^{2}g(x)=A^T{\mathrm{\nabla }}^{2}f(Ax)A$

Matrix decompositions

1. Eigendecomposition: $A=U\mathrm{\Lambda }{U}^T$
   • Eigenvalues are the elements of the diagonal matrix $\mathrm{\Lambda }$, satisfying $Au=\lambda u$
     • Characteristic equation: $\text{det}(\lambda I-A)=0$
     • Rayleigh quotient: $R(A)=\frac{x^{T}Ax}{x^{T}x}$ (used for variational definition)
   • Eigenvectors are the columns of $U$ (which is orthonormal, i.e. $U{U}^T=I$)
   • Inverse: $A^{-1}=U{\mathrm{\Lambda }}^{-1}{U}^T$
   • Spectral theorem: any symmetric matrix is diagonalizable
2. Singular value decomposition (SVD): $A=U\mathrm{\Sigma }{V}^T$
   • $v_i,{\sigma }_i$ are eigen-vector/values of $A^{T}A$, $u_i=\frac{1}{{\sigma }_i}A{v}_i$
     • $\text{rank}(A)=n\le m⟺A^{T}A$ is invertible
     • $\text{rank}(A)=m\le n⟺A{A}^T$ is invertible
   • Principal component analysis equivalent formulations:
     • Variance-maximizing directions: ${\text{argmax}}_u{u}^{T}Cu$
     • Least-squares min directions: $\text{argmin}\sum _i\underset{v_i}{min}||x_i-v_{i}u|{|}_2^2$
     • Rank-one approximation: ${\text{argmin}}_Y||X-Y|{|}_F$
3. Moore-Penrose pseudoinverse: $A^{†}=V{\mathrm{\Sigma }}^{-1}{U}^T$
   • $A^{†}=(A^{T}A{)}^{-1}{A}^T$ if $A$ full column rank (right inverse)
   • $A^{†}=A^T(A{A}^T{)}^{-1}$ if $A$ full row rank (left inverse)
   • If $A=U\mathrm{\Sigma }{V}^T$ is the SVD, then $A^{†}=V{\mathrm{\Sigma }}^{†}{U}^T$
4. LU decomposition: $A=LU$, $L$ lower triangular and $U$ upper triangular
   • LDL decomposition: if $A$ symmetric, $A=LD{L}^T$
   • Cholesky decomposition: iff $A$ is symmetric PD, $A=L{L}^T$ with $L$ lower triangular
5. QR decomposition: $A=QR$, $Q$ orthonormal and $R$ upper triangular
   • Gram-Schmidt: orthonormalize columns of $A$ to get $Q$, use inner products to fill in $R$
     • $\left[\begin{array}{cc}& \\ q_1=\frac{a_1}{||a_1||}& \widetilde{q_i}=a_i-\sum _{j<i}{a}_i^T-(a_i^T{q}_j)q_j& \dots \\ & \end{array}\right]\left[\begin{array}{ccc}||a_1||& a_2^T{q}_1& a_3^T{q}_1\\ 0& ||\widetilde{q_2}||& a_3^T{q}_2\\ 0& 0& ||\widetilde{q_3}||\end{array}\right]$
     • Modified G-S: can replace diagonal elements with zeros for rectangular $A$
   • More numerically stable than LU but more expensive
6. Schur complement: block matrix $\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]$ has Schur complement $D-C{A}^{-1}B$ (if $A$ invertible)
   • $\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]=\left[\begin{array}{cc}I& 0\\ C{A}^{-1}& I\end{array}\right]\left[\begin{array}{cc}A& 0\\ 0& D-C{A}^{-1}B\end{array}\right]\left[\begin{array}{cc}I& A^{-1}B\\ 0& I\end{array}\right]$
7. Block-triangular decomposition: decomposes a square matrix $A$ into block-triangular form
   • If $A=\left[\begin{array}{cccc}{A}_{11}& A_{12}& \cdots & A_{1m}\\ 0& A_{22}& \cdots & A_{2m}\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & A_{mm}\end{array}\right]$ with each $A_{ii}$ square, then $A$ is block-triangular
   • Diagonal blocks $A_{ii}$ can be further decomposed (e.g., LU, QR, SVD)
   • Permutation matrices can symmetrically reorder rows and columns to make $A$ block-triangular

Convexity

1. Convex set $C$: for $x,y\in C$, the line segment $tx+(1-t)y\in C$ for all $0\le t\le 1$
   • Hyperplanes, halfspaces, balls, norms, and polytopes are all convex
   • Convex hull: all coefficients $\ge 0$ and sum to $1$
   • Conic hull: all coefficients $\ge 0$ (removes unit constraint)
2. Convex function $f$: for $x,y$ in the domain, $f(tx+(1-t)y)\le tf(x)+(1-t)f(y)$
   • Affine functions, norms, and quadratic functions are all convex
   • Epigraph (area above line) of a convex function is a convex set
   • First-order condition: $f$ is convex iff $f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x)$
   • Second-order condition: $f$ is convex iff ${\mathrm{\nabla }}^{2}f(x)⪰0$ for all $x$
3. Composition rules:
   • Jensen’s inequality: for convex $f$, $f\left(\sum _{i=1}^n{p}_i{x}_i\right)\le \sum _{i=1}^n{p}_{i}f(x_i)$
   • Affine precomposition: $f(Ax+b)$ is convex for convex $f$ and affine $Ax+b$
   • Nonnegative weighted sum: $\alpha f+\beta g$ is convex for convex $f$, $g$ and $\alpha ,\beta \ge 0$
   • Pointwise maximum: $max\{f(x),g(x)\}$ is convex for convex $f$, $g$
   • Perspective: $tf(x/t)$ is convex for convex $f$ and $t>0$

Duality

1. Constrained optimization problem: $minf(x)$ s.t. $g_i(x)\le 0$ and $h_j(x)=0$
   • We assume the primal $f$ is convex, with constraints $g$ convex, $h$ affine
2. Dual problem: $\underset{\lambda \ge 0,\nu }{max}\underset{x}{min}L(x,\lambda ,\nu )$
   • Lagrangian: $L(x,\lambda ,\nu )=f(x)+\sum _i{\lambda }_i{g}_i(x)+\sum _j{\nu }_j{h}_j(x)$
   • Always concave, even if primal is not convex
   • Weak duality: dual optimum $\le$ primal optimum
   • Strong duality: dual optimum $=$ primal optimum if Slater’s condition holds (primal strictly feasible)
3. Slater’s condition: if the feasible region has an interior point, strong duality holds
   • Strictly feasible: $x$ is in the relative interior of the domain of $D$, and:
     • $g_i(x)<0$ for all $i$ (note strict inequality)
     • $h_j(x)=0$ for all $j$
4. KKT conditions:
   • Primal feasibility: $g_i(x)\le 0$, $h_j(x)=0$
   • Dual feasibility: ${\lambda }_i\ge 0$
   • Complementary slackness: ${\lambda }_i{g}_i(x)=0$
   • Stationarity: $\mathrm{\nabla }f(x)+\sum _i{\lambda }_i\mathrm{\nabla }{g}_i(x)+\sum _j{\nu }_j\mathrm{\nabla }{h}_j(x)=0$
   • If strong duality holds, then KKT is both necessary and sufficient for optimality

Linear programming

1. Standard form: $\underset{x}{min}{c}^{T}x$ subject to $Ax=b$, $x\ge 0$
   • Dual: $\underset{y,s}{max}{b}^{T}y$ subject to $A^{T}y+s=c$, $s\ge 0$
2. Simplex method: moves along vertices of feasible polyhedron until optimum reached
   • Reduced costs: ${\overline{c}}_j=c_j-y^T{A}_j$ where $y$ solves $y^T{A}_B=c_B^T$
   • Optimality condition: if all reduced costs $\ge 0$, current vertex is optimal
   • Bland’s rule: choose entering variable with smallest index among negative reduced costs
3. Interior point methods:
   • Central path: set of points $(x(\tau ),y(\tau ),s(\tau ))$ solving perturbed KKT:
     • $Ax=b$, $x\ge 0$
     • $A^{T}y+s=c$, $s\ge 0$
     • $x_i{s}_i=\tau$ for all $i$ (centralizing condition)
   • Path following methods: approximately follow central path as $\tau \to 0$
     • Short-step: take Newton step, reduce $\tau$ by fixed factor
     • Long-step: take damped Newton step, reduce $\tau$ adaptively

Applications

1. Least squares: $\underset{x}{min}||Ax-y|{|}_2^2$
   • Min-norm solution: $x^{\ast }=(A^{T}A{)}^{-1}{A}^{T}y$
   • Projection matrix: $A{A}^{†}$ using Moore-Penrose psuedoinverse
   • LASSO: $\underset{x}{min}||Ax-y|{|}_2^2+\lambda ||x|{|}_1$
   • Ridge / Tikhonov: $\underset{x}{min}||Ax-y|{|}_2^2+\lambda ||x|{|}_2^2$
     • $x^{\ast }=(A^{T}A+\lambda I{)}^{-1}{A}^{T}y$
   • Weighted: $\underset{x}{min}(Ax-y{)}^{T}W(Ax-y)$
     • $x^{\ast }=(A^{T}WA{)}^{-1}{A}^{T}Wy$
2. Gradient descent:
   • Unconstrained optimization: $\underset{x}{min}f(x)$ for differentiable $f$
     • Gradient descent: $x^{(k+1)}=x^{(k)}-t_k\mathrm{\nabla }f(x^{(k)})$
       • Step size $t_k$ typically chosen by line search or fixed
       • Converges if $f$ is $L$-smooth and $\mu$-strongly convex with $t_k\le \frac{2}{L+\mu }$
     • Newton’s method: $x^{(k+1)}=x^{(k)}-t_k({\mathrm{\nabla }}^{2}f(x^{(k)}){)}^{-1}\mathrm{\nabla }f(x^{(k)})$
       • Converges quadratically if ${\mathrm{\nabla }}^{2}f(x)$ is Lipschitz and initial point close enough to optimum
   • Constrained optimization: $\underset{x}{min}f(x)$ subject to $x\in C$
     • Projected gradient descent: $x^{(k+1)}={\text{Proj}}_C(x^{(k)}-t_k\mathrm{\nabla }f(x^{(k)}))$
       • Projection ${\text{Proj}}_C(y)=\arg \underset{x\in C}{min}||x-y|{|}_2^2$
     • Frank-Wolfe algorithm: $x^{(k+1)}=x^{(k)}+{\gamma }_k(s^{(k)}-x^{(k)})$ where $s^{(k)}=\arg \underset{s\in C}{min}⟨s,\mathrm{\nabla }f(x^{(k)})⟩$
       • Doesn’t require projection, good for structured constraint sets
       • Converges at rate $O(\frac{1}{k})$ if $f$ convex and $\mathrm{\nabla }f$ Lipschitz
3. Support vector machines
   • Hard-margin SVM: $\underset{w,b}{min}\frac{1}{2}||w|{|}^2$ subject to $y_i(w^T{x}_i+b)\ge 1$ for all $i$
     • Maximizes margin $\frac{2}{||w||}$ between hyperplanes $w^{T}x+b=1$ and $w^{T}x+b=-1$
   • Soft-margin SVM: $\underset{w,b,\xi }{min}\frac{1}{2}||w|{|}^2+C\sum _i{\xi }_i$ subject to $y_i(w^T{x}_i+b)\ge 1-{\xi }_i$, ${\xi }_i\ge 0$
     • Allows misclassifications with slack variables ${\xi }_i$, trade-off controlled by $C>0$
   • Kernel trick: replace dot products $x_i^T{x}_j$ with kernel $K(x_i,x_j)=\varphi (x_i{)}^T\varphi (x_j)$
     • Allows learning nonlinear decision boundaries in high-dimensional $\varphi (x)$ space
     • Common kernels:
       • Polynomial $K(x,z)=(1+x^{T}z{)}^d$
       • RBF $K(x,z)=\exp (-\frac{||x-z|{|}^2}{2{\sigma }^2})$