Reading List 2015.6.16

Semidefinite Relaxation of Quadratic Optimization Problems:
Main contribution of this work transform the QCQP problem into SDP problem by ignoring the rank 1 constraint as an approximation.

Subsampling Algorithms for Semidefinite Programming:
An algorithm to solve spectral norm minimization problem as below:

All matrix parameters are semidefinite.
Based on stochastic decent algorithm, this paper propose an stochastic approximation algorithm where the gradient is approximated using randomized matrix multiplication and randomized low-rank approximation.

Uniform Sampling for Matrix Approximation:
A uniform sampling methods to approximate leverage score.

Simple and Deterministic Matrix Sketching:
A streaming algorithm to maintain a sketch low dimension B so that $A^T A \approx B^T B$ and this algorithm is perfectly parallelizable.

Code Generation for Embedded Second-Order Cone Programming:
This article proposes a parser/generator which only needs to map the parameters to the structure of standard form and then can be solved by custom solver. This paper only gives results for second-order cone programming, lacking semidefinite programming.
QCML is a python toolbox for this kind of matrix stuffing.

Performance Analysis of Cooperative Wireless Networks with Unreliable Backhaul Links:
This paper propose a closed-form for sum of independent bernoulli-weighted exponential random variables which characterizes the outage performance.

Reading List 2015.6.3

A Pratical Guide to Randomized Matrix Computations with MATLAB Implementations

This is a very useful paper for whom wants to implements the randomized algorithm in MATLAB and is easy to follow and understand.
In this paper, several matrix sketching methods are first introduced. Then application of least square regression and rank k svd are introduced.
What confused me now is that for SPSD matrix sketching, it seems that for the methods of matrix inversion and eigenvalue decomposition given in the paper, the matrix needs to be SPSD. What if the matrix is not SPSD when I want to implement randomized algorithm to compute the inversion and eigenvalue decomposition?

Reading List 2015.6.2

"Sketching as a Tool for Numerical Linear Algrbra"

-Randomized algorithms:
random sampling, see reference:
1. Randomized algorithms for matrices and data.
2. Iterative row sampling. In FOCS, pages 127-136.
3. Uniform sampling for matrix approximation.

random projection, see reference:
1. Randomized algorithms for matrices and data.
2. Sketching as a Tool for Numerical Linear Algebra.

Some applications: least square regression, least absolute deviation regression, low rank approximation, graph sparsification. The first three applications is introduced in the video tutorial here.

This paper is very technical and not easy to understand. Anyway, sketching technic is a very useful tool in many areas.

ADMM

“Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers”

Solve this kind of problem:

where f and g are convex.

Precursors:
- Dual Ascent

- Dual Decomposition
  Related ideas appear in well known work by Dantzig and Wolfe [44] and Benders [13] on large-scale linear programming, as well as in Dantzig's seminal book [43]
  The general idea of dual decomposition appears to be originally due to Everett [69] and is explored in many early references [107, 84, 117, 14].
  Subgradient method to solve the dual problem by Shor [152].
  Good references on dual methods and decomposition include the book by Bertsekas [16, chapter 6] and the survey by Nedic and Ozdaglar [131].
  More generally, decentralized optimization.

- Augmented Lagrangians and the Method of Multipliers
  Augmented Lagrangian methods yield convergence without assumptions like strict convexity or finiteness of f.
  Augmented Lagrangians and the method of multipliers for constrained optimization were first proposed by Hestenes [97, 98] and Powell [138].

Alternating Direction Method of Multipliers:
unscaled form & scaled form.

Algorithms:

Scaled form:

Very useful algorithm, I need to spend more time on it to have a better understanding.

Reading List - 2015.5.31

1. Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding
A theoretical paper for scs solver in cvx.
The main contribution and final algorithm:

2. Graph Implementations for Nonsmoooth Convex Programs
A general idea of transform problems into graph implementation form and automate the transformation of a problem into standard form for a particular solver.
Main contribution and idea:

3. Randomized algorithms for matrices and data
A very technical paper and not easy to understand. The main idea is reduce the dimension of the matrix using either random sampling or random projection algorithms.
For a simple case of LS approximation, the idea is: