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.

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:

Reading List - 2015.3.18

“Fronthaul Compression for Cloud Radio Access Networks”

A survey of the work in the area of fronthaul compression with emphasis on advanced signal processing solutions based on network information theoretic concepts.

- Multiterminal compression
  Uplink: The key technique is distributed compression or Wyner-Ziv coding[10].
  Downlink: multivariate compression [9 Ch.9].
- Structured coding
  compute-and-forward[11]

• Uplink:

- Point-to-Point Fronthaul Compression

- Distributed Fronthaul Compression
  First proposed in [17].
  sequential decompression [9, Ch. 10] [18] [19].
  Wyner-Ziv compression.
  channel decoding algorithms: message passing or trellis search[10].
  optimization problem of this scheme: block-coordinate optimization approach and leverages a key result in [20].

- Compute-and-forword [11]
- Multihop Fronthaul Topology [22]

• Downlink

- Point-to-Point Fronthaul Compression
- Multivariate Fronthaul Compression
- Compute-and-forward [24]
- "dirty paper" nonlinear precoding [25]
- Performance Evaluation
  cell-edge throughput versus the average per-UE spectral efficiency [8, Fig.5].

Reading List 2015.3.14

“Gradient Descent for Unconstrained Smooth Minimization - Quanming Yao [1]”

1. Rudiments
- Taylor's Theorem
- Lipschitz Constant
- Convex and Strong Convex
- Hessian. Condition Number & Bound on Hessian
- Class of Differential Functions

2. Gradient Descent
- Gradient as General Descent Method:
  choose the step size to ensure convergence to a stationary point of f(x).
- Gradient Descent under Strong Convex
  convergent rate: 1-(1/k)
- Gradient Descent under Weak Convex
  convergent rate: A0/(cA0k + 1)

3. Message from Quadratic Programming
  first-order gradient descent: O(1/k) rate for weak convex; O(1-1/k)^k for strong convex.
- Heavy ball. Need to know function's parameter.
- Conjugate Gradient. Avoid the knowledge of function parameters.

4. Accelerated Gradient Descent
- Weak Convex
- Strong Convex

5. Newton Type Method

Proof of Lemma 1.2 in [1] referring to Lecture 2.

Very difficult for me to understand everything in the paper now.

Reading List 2015.3.12

“Alternative Distributed Algorithms for Network Utility Maximization”

Decomposition techniques: primal decomposition & dual decomposition methods

subproblems (separable) & master problem (update coupling variable)

Solve coupling variable: primal method
Solve coupling constraint: dual method

- Direct Primal and Direct Dual Decompositions
- Indirect Primal and Indirect Dual Decompositions (transform coupling constraint into coupling variable)
- Multilevel Primal and Dual Decompositions
  In problem (17): two sets of constraints (similar to my problem). dual-primal / dual-dual decomposition
- Gradient/Subgradient Methods
  choices of stepsize[33][34][36].
- Standard Dual-Based Algorithm for Basic NUM (Network Utility Maximization)

Application:
- Power-Constrained Rate Allocation
- QoS Rate Allocation
- Hybrid Rate-Based and Price-Based Rate Allocation
- Multipath-Routing Rate Allocation

Reading List 2015.3.11

“Distributed Methods for Constrained Nonconvex Multi-Agent  Optimization - Part I: Theory”

Comparison of some methods: 

1) Feasible Sequential Quadratic Programming (FSQP) methods [2];  --- maintain feasibility but centralized.

2) Parallel Variable Distribution (PVD) methods [3]-[5]; --- parallel but an amount of info exchange/knowledge & convergence only for convex or non convex but block separable constraints.

3) SCA algorithms [6]-[11].

    --- [6][7][11]: centralized; [8]-[10]: distributed methods but convex and separable constraints.

Reading List 2015.3.11 - Parallel variable distribution

• “Parallel variable distribution”

- Unconstrained parallel variable distribution;

- PVD with block separable constraints;

- PVD with general constraints: min f(x) such that g(x) <= 0;

  Handling inseparable constraints: exterior penalty[8], augmented Lagrangian methods[17], [3]. Avoid both of difficulties of above: the dual differentiable exact penalty function[10].

• “Parallel variable distribution for constrained optimization”

In parallel algorithms, an iteration consists of two steps: parallelization & synchronization[2].

Some methods: Block-Jacobi[2], updated conjugate subspaces[10], coordinate descent[21], parallel gradient distribution[14], PVD.

- Nonconvex separable constraints
- Convex inseparable constraints

• “On the Convergence of Constrained Parallel Variable Distribution Algorithms”

Also mentioned some methods: block Jacobi[2], coordinate descent[26], parallel gradient distribution algorithms[16].
Mainly prove the convergence of optimization problems with general convex constraints.