### Archive

Archive for July, 2012

## Optimisation on Manifolds — Lifting Iterative Algorithms from Euclidean Space to Manifolds

A natural question to ask in the theory of Optimisation on Manifolds is how the Newton method can be generalised to an iterative method on a manifold. Traditionally, the standard way was formulaic: because the Newton method involves a gradient, a Hessian, and vector space addition, generalise these concepts first then apply Newton’s formula.  This led to the Riemannian Newton method. Gradients, Hessians and vector addition are not intrinsic though; they are just one realisation of an iterative method that uses the first and second order derivatives to converge locally quadratically to a (non-degenerate) critical point.  The standard Newton formula in Euclidean space is designed to be optimal for quadratic cost functions, but a simple change of coordinates will change it to being optimal for another class of cost functions instead.

It turns out that changes of coordinates play a fundamental role in understanding how the Newton method, or any (memoryless) iterative method for that matter, can be lifted to manifolds. In A Framework for Generalising the Newton Method and Other Iterative Methods from Euclidean Space to Manifolds, it was essentially demonstrated that all generalised Newton methods can be understood as applying a different change of coordinates at each iteration, and local quadratic convergence can be assured if and only if the Newton method in Euclidean space is “robust” to these changes, meaning its radius of convergence can be uniformly bounded under all coordinate changes of interest.  The Newton method is indeed very robust, leading to a tremendous variety of possibilities for lifting it to manifolds which go well beyond the traditional class of Riemannian Newton methods.

It was also pointed out there is generally no reason to insist that the lift is uniquely defined globally.  It suffices to lift locally in response to where the iteration is currently at. Visually, one way to think of this is to re-centre at each step of the iteration: rather than move a point around a sphere searching for a critical point, keep applying rotations to the sphere endeavouring to bring a critical point to the North pole.  More generally, arbitrary transformations of the manifold, or of the ambient space containing the manifold, can be used for re-centring at a distinguished point, and the Newton method need only be lifted to a region containing the distinguished point.  (A special case is “rolling without slipping”, but there a Riemannian metric is present, which results in the local lifts fitting together globally. This need not be the case for more general re-centring techniques, and may possibly lead to more efficient algorithms that use simpler lifts.)

Many competing factors come into play when designing a Newton method for a particular problem. Hopefully the framework will prove useful, but it is far from being a panacea.  It raises more questions than it answers.

## Collaborative Paper Writing using Git and Drop Box / Google Drive

Distributed version control software (git, mercurial, …) provides a safe and convenient means for people to collaborate on projects, including the writing of academic papers using latex.  Although there are various ways of setting up an online repository, perhaps the fastest way to start is by using Drop Box or Google Drive (or equivalent) to share a repository for a specific project.

Warning: If two people ‘push’ to the repository at the same time then corruption may occur. Therefore, pushes should be infrequent and/or coordinated via email.  (Although ending up in this situation is best avoided, it is possible to recover by recreating the shared repository from the local repositories.)

Note: A long hypen (—) actually means two hyphens next to each other, which is the standard way of specifying ‘long options’ on the command line.

The following instructions are valid for linux or Mac, using a recent version of git (tested with git version 1.7.11.1).

### Installing and Configuring Git

Installing git is straightforward; just go to the download page.  To configure git, at a minimum, run:

git config —global user.name “Jonathan Manton”

#### Optional

To change the default ‘merge’ program to vimdiff, run:

git config —global merge.tool vimdiff

To automatically ignore certain files globally, create the file (any filename will do) ~/.gitignore_global and place in it something like:

*.o
*.so
*.bak

Next, run:

git config —global core.excludesfile ~/.gitignore_global

Note that it is “excludesfile” and not “excludefiles”! You will not receive an error if you type the wrong name because all git config –global does is insert entries into the file ~/.gitconfig (this file can be edited by hand if you prefer).

### Creating the Shared Repository

(Only the person creating the shared repository need read this section.) Create a new directory in Drop Box or Google Drive, and change directory into it:

cd ~/Dropbox
mkdir NewPaper.git
cd NewPaper.git

Initialise the git repository:

git init —bare

Move to where you would like to have your local copy of the paper (not on Dropbox!) then clone the repository and change directory into it:

cd ~/Desktop
git clone ~/Dropbox/NewPaper.git
cd NewPaper

Do not worry about the warning that we have cloned an empty repository. We are about to populate it before sharing with our collaborators.

Create a .gitignore file with the following contents:

*.pdf
*.bbl
*.aux
*.log

Create skeleton files for the project (e.g. a tex file and a bib file).  Run pdflatex and check everything works.  Then:

git status
[check that the files produced by pdflatex are ignored (modify .gitignore if this is not the case) and the files that you want are showing up as Untracked files.]

Add the files to git then commit:

git commit
[An editor will open up; type in a message describing this commit, e.g. “Skeleton files”.]

Finally, these changes need to be ‘pushed’ to the shared repository:

git push origin master

The directory NewPaper.git on Drop Box or Google Drive should now be shared with your collaborators so that it shows up on their computers.

### Creating a Local Repository

Each person will work in their own local repository.  The workflow is described in the next section. This section states how to create a local repository.  (The person who created the shared repository, as described in the previous section, already has a local repository, namely ~/Desktop/NewPaper, and can skip this section.)

cd ~/Desktop
git clone ~/Dropbox/NewPaper.git
cd NewPaper

### Collaborative Workflow

The following is the same for both the person who created the repository as above, and for the other collaborators who have shared access to the Drop Box / Google Drive folder containing the repository.

Henceforth, it is assumed there is a directory called ~/Desktop/NewPaper that contains the local git repository.  (Because this local repository was created using ‘git clone’, it knows the location of the shared repository.)

The basic philosophy is that the shared repository ~/Dropbox/NewPaper.git should always contain a version that compiles correctly. Therefore, each collaborator should work in their own local repository, and only ‘push’ changes to the shared ~/Dropbox/NewPaper repository that are ready for sharing. (This is known as the “centralised workflow”. Alternative workflows may be preferable in more complex situations.) Furthermore, since two people pushing at the same time can corrupt the shared repository (a consequence of using Drop Box instead of a proper git repository), pushes should be infrequent and/or coordinated by email.

First check everything is ok:

cd ~/Desktop/NewPaper
ls
git status
git log

If you haven’t touched the repository for a while (and you have not made any modifications since the last commit), it is always a good idea to get the latest changes from the shared repository:

git pull

Then you can start editing files freely, and running pdflatex to compile.  It is a good idea to frequently commit, to allow you to go back to an earlier version should something go wrong.  Committing does not affect the shared repository.

git commit -a
[In the text editor which will open up, enter a description of the changes you made.]

If you have created a new file (e.g. my_figure.pdf that will be included in the latex document) that you wish to add to the repository, then just prior to committing (e.g. after you have included the figure in the latex file and ran pdflatex to check it all works), type:

git commit -a

The interesting bit comes when you go to push your version to the shared repository.  You can try:

git push

If you are lucky, it will work.  Otherwise, someone pushed before you, and there are effectively two branches (versions) that must be merged.  Provided you have been working on a different part of the latex file from your collaborators, the changes can be merged automatically.  Try:

git pull

Note that here, we are basically using ‘git pull’ as a shortcut for ‘git fetch’ followed by ‘git merge’.  If it worked, we are done, otherwise there are two options. Either edit the files that have conflicts (the output of ‘git pull’ will state which files they are) and fix them manually, or run ‘git mergetool’. At this point, it is best to consult the documentation on basic merge conflicts.

In essense then, the workflow is cyclic: ‘git pull’ followed by the editing of files and one or more ‘git commit -a’, then finally ‘git push’ (followed by ‘git pull’ and ‘git push’ again if a merge was required).  At any point, ‘git status’ and ‘git log’ can be run.

Categories: Software