Andersen Ang | Papers | Talks | Notes | Misc.

• My notes since my PhD study (2017). Email me if you catch a mistake/typo.
• I update this page often, refresh browser to avoid showing the old page.
  
• Some quotes
  • “In maths you don't understand things. You just get used to them.'' John von Neumann
  • “I learned very early the difference between knowing the name of something and knowing something” Richard Feynman

Course / Tutorial

• COMP1215 Foundations of Computer Science 2023-2024 Uni. Southampton
  A short introduction to combinatorics & combinatorial analysis
  A short introduction to probability & statistics
  A short introduction to graph theory
  Short notes on statistics
  Key concepts and book
  Madbook

• CO327 Deterministic OR Models 2022-spring, Uni. Waterloo

• On Gradient descent solving quadratic problems | video

Continuous Optimization

Convex analysis / Foundation

• Convex, strongly conve, Lipschitz, Lipschitz gradient, Lipschitz Hessian, lower semicontinuous function

• 1st-order Taylor approximation of convex function and Bregman divergence

• Sandwich theorem for β-smooth function

• Monotonictiy of gradient of strongly-convex smooth function

• 1st-order optimality condition for constrained optimization

• Common glossaries in optimization

• Coercive function

• proj operator is firmly non-expensive & obtuse angle criterion

• Augmented objective function & methods for constrained optimization

• \(\textrm{epi} f\), \(f \square g\) and \(f \square \frac{1}{2}\| \,\cdot\,\|^2\)

• Prox of norm, Moreau's decomposition, conjugate of norm = indicator function of dual norm

• Characterizing subdifferential of norm \( \partial \| x\| = \big\{ v ~|~ \langle v,x\rangle = \| x\| , \|v\|_* \leq 1 \big\} \)

• Projection onto nonnegative orthant, rectangular box and polyhedron | L2 ball | L1 ball | simplex | nonnegative unimodal vector, intersection of convex sets | L-Lipschitz matrix | Spectraplex

• Linear Optimization

• Solving piece-wise linear equation

1st-order method

Gradient descent

• Gradient descent

• Gradient descent step as minimizer of local quadratic model

• Sufficient Descent Lemma of gradient descent on L-smooth function

• Solving least squares by Landweber iteration

• Subdifferential and subgradient

• Subgradient method

• Proximal bundle method

• Condtional Gradient (Frank-Wolfe Algorithm): introduction

• Polyak’s Heavy Ball Method on quadratic problem

Proximal map

• Moreau-Yosida Envelope & Proximal map

• Proximal point method

• Proximal gradient & convergence rate on β-smooth convex function

• Sufficient decrease property of proximal gradient operator

• L1-regularized Least Squares

• Derivation of the soft thresholding operator

• Solving L1-regularized least squares by reweighted least squares

• Adaptive restarts

Convergence rate

• Convergence rates in optimization

• Nesterov's optimal convergence rate of 1st-order method on convex smooth functions

• Nesterov's Estimate Sequence, part 1: what is it & how to make one

• Nesterov's Estimate Sequence, part 2: optimal 1st-order scheme

• Convergence rate of gradient descent on convex smooth function

• Convergence rate of gradient descent on strongly-convex smooth function

• Convergence rate of projected gradient method on L-Lipschitz convex function

• Convergence rate of Nesterov’s accelerated gradient method on β-smooth convex function

• Convergence rate of Nesterov’s accelerated gradient method on α-strongly convex β-smooth function

• Convergence rate of proximal gradient method / ISTA

• Convergence of proximal gradient with Nesterov's acceleration / FISTA

Mirror Descent

• Motivation of mirror descent 1: Gradient vector lives in the dual space

• Motivation of mirror descent 2: a geometry example

• Mirror descent algorithm

Gradient flow

• Gradient flow gives gradient update, proximal point update, extra-gradient update and 4th order Runge-Kutta update

• Convergence of gradient flow in continuous time

• Convergence analysis of 1st-order method on a quadratic programming problem using dynamic system

• Convergence of 4th-order Runge-Kutta update on least square problem

• Deriving ODE model of Nesterov's accelerated gradient

• Principle of least action & Euler-Lagrange equation of motion

Primal-dual method

• Lagrangian Mutiplier

• What is conjugate: \(\displaystyle \max_{x} \langle y,x\rangle - f(x)\)?

• Properties of conjugate

• Deriving the dual problem using conjugate

• Duality | KKT | Slater’s constraint qualifications

• Fast dual proximal gradient method

• Fast primal-dual proximal gradient algorithm and preconditioning

• How ADMM was developed

• Convergence of ADMM

• \(\frac{1}{\sqrt{k}}\) convergence rate of ADMM

• \(\frac{1}{k}\) ergodic convergence rate of ADMM

Monotone Operator Theory

• Where does operator splitting come from

• Fixed point of average of non-expansive operator

Multiple-point / Quasi-Newton methods

• Convergence of a proximal quasi-Newton's method

• Cubic regularization

• Sol to line search of Anderson Acceleration subproblem

• Anderson Acceleration

• Functions that has Lipschitz Hessian

Randomized methods

• Big finite sum

• Confusing naming in the stochastic methods

• Stochastic Gradient Method (SG)

Majorization Minimization

• MM: the technique of surrogate

• Solving total variation norm regularised least square by MM

• Convergence of MM

• BSUM (only convergence, no rate)

• TiTAN

Coordinate Descents

• Coordinate Descent - an introduction

• Solving nonegative least sqaures with L1-regularization

• Convergence of randomized block coordinate gradient descent on β-smooth convex function

• Greedy coordinate descent

• Accelerating coordinate descents

Nonconvex Optimizations

• Polyak-Łojasiewicz inequality

• Proximal Polyak-Łojasiewicz inequality

• Kurdyka-Łojasiewicz property

• Proximal Alternating Linearized Method (PALM)

• Convergence of PALM on nonconvex problem, part 1 : generated sequence is non-increasing and the trajectory has finite length

• Convergence of PALM on non-convex problem, part 2 : generated sequence converges to a critical point

• Inertial Proximal Alternating Linearized Method (iPALM)

• Xu-Yin's Block Coordinate Descent Method for Regularized Multiconvex Optimization, hand written

Trust-region methods

• Convergence of TRM on unconstrained smooth optimization

Total Variation

• Background and Formulation

  • Continuous total variation in infinite dimensional space

  • Discrete total variation in finite dimensional space

• Algorithm

  • Solving total variation norm regularised least square by Proximal gradient method with ADMM

  • Solving total variation norm regularised least square by MM

Nonnegative Matrix Factorization

• Nonnegative Least Squares (NNLS)

  • NNLS, its geometry and its KKT

  • Penalty method is not effective for NNLS – using softmax

  • Penalty method is not effective for NNLS – using iteratively reweighed least squares

  • NNLS by Projected Gradient Descent: acceleration and restart NNLS PGD mfile NNLS PGD mfile 2

  • NNLS by Multiplicative Update NNLS MU mfile

  • NNLS by ADMM

  • Nonnegative Unimodal Least Squares

• Nonnegative Matrix Factorization

  • Step-by-step expansion of \(\|A−BC\|_F^2\)

  • If A and its inverse are both nonnegative, then A is the permutation of a positive diagonal matrix

  • No scaling ambiguity in Symmetric NMF (hand written)

  • Basic cone geometry and algebra for NMF

  • AB is nonnegative if \(\text{cone}(A^T) \subset \text{cone}_∗(B)\)

  • NMF and the Multiplicative Update algorithm

  • Convergence analysis of the Multiplicative Update NMF algorithm

  • NMF via Projected Gradients | PGD algorithm mfile | APG algorithm mfile

  • NMF via HALS: column-wise exact block coordinate descent | HALS mfile

  • NMF with Regularization

  • Multi-grid NMF

  • Separable NMF: the separability assumption in NMF

  • Uniqueness of solution of minimum volume (N)MF

  • Rank-1 NMF is not NP-Hard and closed-form sol

  • KL divergence is not Lipschitz smooth

Matrix Completion & Nuclear norm

• Matrix Rank Minimization problems

• Introduction to Matrix Completion

• Nuclear norm is tight convex relaxation of rank function only within the unit ball

• Proving nuclear norm is a norm

• Characterization of nuclear Norm : nuclear norm is the dual norm of the spectral norm

• Understanding the uniqueness of the sol. of the nuclear norm minimization

• Singular value thresholding solves \(\min_{X} \frac{1}{2} \| X−Y \|_F^2 + \tau \|X\|_*\)

• Singular value thresholding solves \(\min_{X} \frac{1}{2} \| X−Y \|_F^2 + \tau \|X\|_*\), by von Neumann trace inequality

• MC algorithm: Majorization-Minimization

Linear Algebra & Matrix Theory

• General

  • On the rank of the matrix equation X=YQ

  • \(\| X \|_2 \leq \sqrt{n} \max_{k} \| X(:,k)\|_2\)

  • \(\| X \|_2 \leq \| X \|_F\)

  • Matrix Factorization in vectorized format | mfile

  • Column-wise representation of determinant of gram matrix

  • Operator norm of rank-1 perturbation \(\| I + k uv^T\|\)

  • \(\text{tr}(A^2) \geq \frac{\text{tr}(A)^2}{n},\text{tr}(A^2)\leq (\text{tr}A)^2\)

  • Get rid of the Hadamard product in \(\| \omega \circ (Ax-B) \|\)

  • Quaternion

• Matrix Derivative

  • Matrix derivatives, Single Entry Matrix and derivatives of log- det

  • Matrix derivative on scalar function of matrix variable

  • Matrix derivative on matrix function of matrix variable

• Functions of singular values

  • Functions of singular values

  • Subgradient of functions of singular values

  • \(\det X, \text{logdet} X , \text{logdet} X^TX\)

  • \(\text{logdet}(A^TA+\delta I) \leq \text{logdet}(B^TB+\delta I)+ \text{tr}((B^TB+\delta I)^{-1}A^TA)+\text{const.}\)

  • \(\text{tr}(I−A^{-1}) \leq \text{logdet}A \leq \text{tr}(A−I)\)

Compressive Sensing

• Generating uniform unit random vectors in \(R_n\)

• Johnson-Lindenstrauss Lemma & big matrices are approximately low rank

• min \(‖x‖_0\) subject to Ax=b

• Uniqueness of sol. of spares recovery problem : Kruskal rank & incoherence

• Mutual Coherence & the Welch Bound

• Orthogonal Matching Pursuit

Scientific Computing

• Review numerical 2D Poisson Equation

• Elastic obstacle problem

• Poisson image editing

• MGOPT direction is a descent direction

Miscellaneous

Machine Learning & Signal Processing

• Error computation in matrix factorization problems

• Hyperspectral unmixing and NMF

• Short Time Fourier Transform

Multilinear Algebra & Tensors

• ABC of tensors

• Canonical Polyadic Decomposition: basic notations

Clifford Algebra

• Clifford algebra in \(\mathbb{R}^2\)