SESOP

SESOP_PACK: Matlab Tool for Sequential Subspace Optimization

Michael Zibulevsky

SESOP [1,4] is a method for large-scale smooth unconstrained optimization, which can be considered as a natural extension of the conjugate gradients. At each iteration, we search for a minimum of the objective function over a subspace spanned by the current gradient and by the directions of a few previous steps. We can also include into this subspace direction from the starting point to the current point, and the weighted sum of all previous gradients, following [Nemirovski, 1982]. This safeguard measure provides an optimal worst-case error decay of order 1/k^2 (for convex problems), where k is the iteration count. There is an important class of problems, where subspace optimization can be implemented extremely fast. This happens when the objective function is a combination of expensive linear mappings with cheap non-linear functions. This is a typical situation in such applications, as tomography, signal and image denoising with basis pursuit, pattern recognition with support vector machines, and many others.

SESOP-TN method [5] combines ideas of SESOP with those of the Truncated Newton (TN) method [2]. Replacing TN line search with subspace optimization, we allow Conjugate Gradient (CG) iterations to stay matched through consequent TN steps. This resolves the problem of TN sensitivity to an early break of the CG process. For example, when an objective function is quadratic, the SESOP-TN trajectory coincides with the trajectory of CG as applied directly to the objective. Standard TN lacks this property and converges more slowly. Numerical experiments illustrate the effectiveness of the method.

MATLAB CODE: The latest version 07.06.2010

Older: Version 10.05.2010 Version 08.08.2008 Version 04.02.2009

Implemented optimization methods (directory SESOPTN2)

  • Polak-Ribiere nonlinear Conjugate Gradients

  • Truncated Newton

  • SESOP: Sequential Subspace Optimization

  • SESOP-TN: Sequential Subspace Optimization combined with Truncated Newton [5]

∙ Methods for L1-L2 optimization [4,6], see directory Sesop_SPmagazine

1. PCD (Parallel Coordinate Descent); PCD-SESOP; PCD-CG

2. SSF (Separable Surrogate Functions); SSF-SESOP; SSF-CG

3. FISTA (Fast Iterative Soft-Thresholding)

Sub-directories in SESOPTN2

  • Sesop_Basic_BP - Basis Pursuit simple example

  • Sesop_PCD_BasisPursuit - Basis Pursuit via PCD-SESOP (parallel coordinate descent) [4]

  • Sesop_NeuralNet - Neural Net Training. Applications: Signal Denoising and Prediction

  • Sesop_SVM - Linear L1-L2 Support Vector Machine for Pattern Recognition, extension of [3]

∙ Sesop_SPmagazine - Compressive Sensing, Image Deblurring and Tomography via L1-L2 optimization [6]

My collaborators at various stages of the work on SESOP and its applications

  • Arkadi Nemirovski, Guy Narkiss, Michael Elad, Boaz Matalon, Joseph Shtok, Grigory Begelman, Eli Osherovich, Yehuda Pfeffer, Ehud Rivlin, Irad Yavneh

References:

  1. Guy Narkiss and Michael Zibulevsky (2005). "Sequential Subspace Optimization Method for Large-Scale Unconstrained Problems", Tech. Report CCIT No 559, EE Dept., Technion. pdf file

  2. Stephen G. Nash, “A Survey of Truncated-Newton Methods”, Journal of Computational and Applied Mathematics, 124 (2000), pp. 45-59.

  3. Guy Narkiss and Michael Zibulevsky (2005). "Support Vector Machine via Sequential Subspace Optimization", Tech. Report CCIT No 557, EE Dept., Technion. pdf file

  4. Michael Elad, Boaz Matalon, and Michael Zibulevsky, "Coordinate and Subspace Optimization Methods for Linear Least Squares with Non-Quadratic Regularization", Applied and Computational Harmonic Analysis, Vol. 23, pp. 346-367, November 2007. pdf file

  5. Michael Zibulevsky (2008), SESOP-TN: Combining Sequential Subspace Optimization with Truncated Newton method

6. Michael Zibulevsky and Michael Elad,"L1-L2 Optimization in Signal and Image Processing: Iterative Shrinkage and Beyond" , IEEE Signal Processing Magazine, to appear

Haifa, August 8, 2008 – February 25, 2010

*********************************************************************

APPENDIX:

Brief description of SESOP-TN algorithm

We minimize a function f(x), which has gradient g(x) and Hessian H(x). Note that the Hessian is not computed explicitly: just Hessian-vector products are used.

Iteration of SESOP-TN

1. TN step: solve Newton system Hd=-g approximately, using limited number of Conjugate Gradient (CG) steps.

2. Optimize f(x) over affine subspace spanned by:

  • Directions of several previous steps and gradients of f(x_k)

  • Direction of the TN step

  • Exit value of the gradient of the quadratic model minimized at TN step

  • Last CG direction of TN step

3. Goto Step 1 (TN), feeding the resulting subspace optimization step into CG starting condition.

The presented procedure allows resolving the typical TN problem, related to the early break of CG process. For example, when f(x) is quadratic, SESOP-TN trajectory is the same as one of CG applied to f(x). Standard TN would converge slower in this case.

Note that subspace optimization step 2 can be carried out very efficiently, if f(x)= f1(Ax)+f2(x), where Ax is computationally heavy, and f1(.) and f2(.) are inexpensive (see [1] for the details).