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