Andersen Ang | Papers | Talks | Notes | Misc.

Some basic convex analysis

Optimization glossary

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

Sandwich theorem for β-smooth function

Gradient monotonictiy of strongly-convex smooth function

1st-order optimality for constrained optimization

Coercive function

Augmented objective function & methods for constrained optimization

Characterizing subdifferential of norm

proj operator is firmly non-expensive & obtuse angle criterion

Projection onto , box & polyhedron -ball -ball simplex nonnegative unimodal, -Lipschitz matrix Spectraplex, Convex Sets

Linear Optimization

Solving piece-wise linear equation

Gradient descent

GD step as minimizer of local quadratic model

Sufficient Descent Lemma of GD on L-smooth function

Solving least squares by Landweber iteration

Subdifferential & subgradient

Subgradient method

Proximal bundle method

Conditional Gradient (Frank-Wolfe): introduction

Polyak’s Heavy Ball Method on quadratic problem

, ,

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

Proximal point method

Proximal gradient & convergence rate on -smooth convex function

Sufficient decrease property of proximal gradient operator

-regularized Least Squares

Derivation of soft thresholding operator

Solving -regularized least squares by reweighed least squares

Adaptive restarts

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

Motivation of mirror descent 1: gradient lives in the dual space

Motivation of mirror descent 2: a geometry example

Mirror descent algorithm

Lagrangian Multiplier

What is conjugate ?

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

How ADMM was developed

Convergence of ADMM

convergence rate of ADMM

ergodic convergence rate of ADMM

Where does operator splitting come from

Fixed point of average of non-expansive operator

Convergence of a proximal quasi-Newton's method

Cubic regularization

Sol to line search of Anderson Acceleration subproblem

Anderson Acceleration

Functions with Lipschitz Hessian

Big finite sum

Confusing naming in stochastic methods

Stochastic Gradient Method (SG)

MM: technique of surrogate

Solving total variation norm regularized least squares by MM

Convergence of MM

BSUM (only convergence, no rate)

TiTAN

Coordinate Descent - introduction

Solving nonnegative least squares with -regularization

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

Greedy coordinate descent

Accelerating coordinate descents

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 Block Coordinate Descent for Regularized Multiconvex Optimization, hand written

Continuous TV in infinite dimensional space

Discrete TV in finite dimensional space

Solving TV norm regularized least square by Proximal gradient method with ADMM

Solving TV norm regularized least square by MM

NNLS, its geometry & 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 & restart | NNLS PGD mfile | NNLS PGD mfile 2

NNLS by multiplicative update | NNLS MU mfile

NNLS by ADMM

Nonnegative Unimodal Least Squares

Step-by-step expansion of

If A and its inverse are 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

NMF and multiplicative update

Convergence analysis of the multiplicative update

NMF via projected gradient |
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: separability assumption

Uniqueness of solution of minimum volume (N)MF

Rank-1 NMF is not NP-Hard & closed-form sol

KL divergence is not Lipschitz smooth

Matrix Rank Minimization

Introduction to Matrix Completion

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

Proving nuclear norm is a norm

Characterizing 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

Singular value thresholding solves by von Neumann trace inequality

MC algorithm: Majorization-Minimization

On the rank of matrix equation

Matrix Factorization in vectorized format mfile

Column-wise representation of determinant of gram matrix

Operator norm of rank-1 perturbation

Get rid of the Hadamard product in

Quaternion

Matrix derivatives, Single Entry Matrix and derivatives of logdet

Matrix derivative on scalar function of matrix variable

Matrix derivative on matrix function of matrix variable

Functions of singular values

Subgradient of functions of singular values

Generating uniform unit random vectors in

Johnson-Lindenstrauss Lemma & big matrices are approximately low rank

subject to

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

Mutual Coherence & the Welch Bound

Orthogonal Matching Pursuit

Review numerical 2D Poisson Equation

Elastic Obstacle Problem

Nonlinear elastic obstacle problem

Poisson image editing

MGOPT direction is a descent direction

Error computation in matrix factorization

Hyperspectral unmixing & NMF

Short-time Fourier transform

ABC of tensors

Canonical Polyadic Decomposition: basic notations