- 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**

- “In maths you don't understand things. You just get used to them.''

**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**

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

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

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

Sufficient Descent Lemma of gradient descent on L-smooth function

Subdifferential and subgradient

Subgradient method

Proximal bundle method

Moreau-Yosida Envelope & Proximal map

Proximal gradient & convergence rate on β-smooth convex function

Solving L1-regularized least squares by reweighted least squares

Adaptive restarts

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 functionConvergence rate of

**gradient descent**on strongly-convex smooth functionConvergence rate of

**projected gradient method**on L-Lipschitz convex functionConvergence rate of

**Nesterov’s accelerated gradient method**on β-smooth convex functionConvergence rate of

**Nesterov’s accelerated gradient method**on α-strongly convex β-smooth functionConvergence of

**proximal gradient with Nesterov's acceleration / FISTA**

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

Principle of least action & Euler-Lagrange equation of motion

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

Properties of conjugate

Duality | KKT | Slater’s constraint qualifications

Fast primal-dual proximal gradient algorithm and preconditioning

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

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

Cubic regularization

Anderson Acceleration

Convergence of MM

BSUM (only convergence, no rate)

TiTAN

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

Greedy coordinate descent

Accelerating coordinate descents

Kurdyka-Łojasiewicz property

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

Background and Formulation

Algorithm

Nonnegative Least Squares (NNLS)

Nonnegative Matrix Factorization

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

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

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

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

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\|_*\)

General

Matrix Derivative

Functions of singular values

Johnson-Lindenstrauss Lemma & big matrices are approximately low rank

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

Poisson image editing