$\DeclareMathOperator{\arccosh}{arccosh} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator{\Exp}{Exp} \newcommand{\geo}[2]{\gamma_{\overset{\frown}{#1,#2}}} \newcommand{\geoS}{\gamma} \newcommand{\geoD}[2]{\gamma_} \newcommand{\geoL}[2]{\gamma(#2; #1)} \newcommand{\gradM}{\nabla_{\M}} \newcommand{\gradMComp}[1]{\nabla_{\M,#1}} \newcommand{\Grid}{\mathcal G} \DeclareMathOperator{\Log}{Log} \newcommand{\M}{\mathcal M} \newcommand{\N}{\mathcal N} \newcommand{\mat}[1]{\mathbf{#1}} \DeclareMathOperator{\prox}{prox} \newcommand{\PT}[3]{\mathrm{PT}_{#1\to#2}#3} \newcommand{\R}{\mathbb R} \newcommand{\SPD}[1]{\mathcal{P}(#1)} \DeclareMathOperator{\Tr}{Tr} \newcommand{\tT}{\mathrm{T}} \newcommand{\vect}[1]{\mathbf{#1}}$

# The subgradient descent algorithm on a manifold

Based on a manifold $\M$, a starting point $x^{(0)} = x$, and an element from the (sub)gradient (or descent) direction $\eta\in\partial F$ of a function $F\colon\M\to\R$ this function performs a subgradient descent algorithm %}

with step sizes $s_k$, $k=1,\ldots,$ where we keep track of the minimal value $x^{\mathrm{opt}}$. If $F$ is not single valued, this algorithm assumes, that it is meant as a parallel subgradient algorithm with respect to the last dimension(s) of $x$.

The implementation is based on the paper [1].

All functions involved are provided as anonymous functions: The subgradient subgradF is a function based on @(x), the step size is a function @(x,descentDir,iter,initial) based on the current iterate$x=x^{(k)}$, descent direction $\eta$, the iteration $k$ and an initial step size to start seaching with. This value is set to the last step size within the iterations. Finally the stoppingCriterion is a function based on @(x,xold,iter) that returns false as long as the algorithm should run, hence the algorithm stops if the stopping criterion is fulfilled for the first time.

### Optional Parameters

Debug
If set to an anonymous functional depending on @(x,xold,iter) this is called in each cycle, for example to produce text output or save iteration data to a file.
Record
If set to a functional @(x,iter) returning a column vector, and calling the cyclicProximalPoint with a second return value, this function records these column vectors in a matrix returned in the second return value recData.

### Matlab Documentation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
% compute a sub gradient descent on F using x as inital data and subgradF
% as the (sub)gradient. If F returns a number, the classical subgradient
% descent is performed; if it returs a vector or matrix; a parallel
% subgradient descent is computed, where the (last) data dimensions of x
% are handled in parallel.
%
%   Ferreira, O.P.; Oliverira, P.R.: Subgradient Algorithm on Riemannian
%       manifolds
%       Journal of Optimization Theory and Applications 97.1, 93-104, 1998.
%
% INPUT
%    M                : a manifold M
%    x                : initial data
%    F                : the function F for the different gradients in
%                       parallel or just a value for standard gradient
%                       descent
%    subgradF         : a function @(x) returning the gradient of F at x
%    stepSize         : a function @(x,eta,iter,initial) returning the
%                       stepsize at x with direction eta corresponding to
%                       a certain rule (e.g. Amijo) based on iterate point
%                       x, descent direction eta, iteration iter and
%                       initial stepsize initial.
%   stoppingCriterion : a function @(x,xold,iter) determining whether to
%                       stop or not
% OPTIONAL
%   Debug             : ([]) a function @ (x,xold,iter) producing debug
%                          output
%   Record            : (@(x,iter)) a function returning a column vector,
%                       if there's a second return value and this function
%                       is given, data is recorded in an array and returned
% ---
% MVIRT | R. Bergmann | 2018-03-15