In this talk we present p-order methods for unconstrained minimization of convex functions that are p-times differentiable with Hölder continuous p-th derivatives. We establish worst-case complexity bounds for methods with and without acceleration. Some of these methods are "universal", that is, they do not require prior knowledge of the constants that define the smoothness level of the objective function. A lower complexity bound for this problem class is also obtained. This is a joint work with Yurii Nesterov (Université Catholique de Louvain).
 

Since Weierstrass it has been known that there are functions that are continuous but nowhere differentiable.  A beautiful example (with probability 1) is any Brownian path.  Brownian paths can be constructed either in space, via Brownian bridge, or in Fourier space, via random Fourier series.

What about functions, which we call "smoothies", that are $C^\infty$ but nowhere analytic?  This case is less familiar but analogous, and again one can do the construction either in space or Fourier space.  We present the ideas and illustrate them with the new Chebfun $\tt{smoothie}$ command.  In the complex plane, the same idea gives functions analytic in the open unit disk and $C^\infty$ on the unit circle, which is a natural boundary.

Reconstruction of 3D images from a set of 2D X-ray projections is a standard inverse problem, particularly in medical imaging. Improvements in imaging technologies have enabled the development of a flat-panel X-ray source, comprised of an array of low-power emitters that are fired in quick succession. During a complete firing sequence, there may be shifts in the patient’s resting position which ultimately create artifacts in the final reconstruction. We present a method for correcting images with respect to unknown body motion, focusing on the case of simple rigid body motion. Image reconstructions are obtained by solving a sparse linear inverse problem, with respect to not only the underlying body but also the unknown velocity. Results find that reconstructions of a moving body can be much better than those obtained by measuring a stationary body, as long as the underlying motion is well approximated.

The standard rounding procedure in floating-point computations is round to nearest (RN). In this talk we consider an alternative rounding strategy called stochastic rounding (SR) which has the appealing property of being exact (actually exact!) in expectation. In the first part of the talk we discuss recent developments in probabilistic rounding error analysis and we show how rounding errors grow at an O(\sqrt{n}) rate rather than O(n) when SR is employed. This shows that Wilkinson's rule of thumb provably holds for this type of rounding. In the second part of the talk we consider the application of SR to parabolic PDEs admitting a steady state solution. We show that when the heat equation is solved in half precision RN fails to compute an accurate solution, while SR successfully solves the problem to decent accuracy.
 

We consider the problem of dynamically pricing multiple products on a network of resources, such as that faced by an airline selling tickets on its route network. For computational reasons this inherently stochastic problem is often approximated deterministically, however even the deterministic dynamic pricing problem can be impractical to solve. For this reason we have derived a novel iterative Quadratic Programming approximation to the deterministic dynamic pricing problem that is not only very fast to solve in practice but also exhibits a provably linear rate of convergence. This is joint work with Saksham Jain and Raphael Hauser.
 

Randomized SVD has become an extremely successful approach for efficiently computing a low-rank approximation of matrices. In particular the paper by Halko, Martinsson (who is speaking twice this week), and Tropp (SIREV 2011) contains extensive analysis, and made it a very popular method. 
The complexity for $m\times n$ matrices is $O(Nr+(m+n)r^2)$ where $N$ is the cost of a (fast) matrix-vector multiplication; which becomes $O(mn\log n+(m+n)r^2)$ for dense matrices. This work uses classical results in numerical linear algebra to reduce the computational cost to $O(Nr)$ without sacrificing numerical stability. The cost is essentially optimal for many classes of matrices, including $O(mn\log n)$ for dense matrices. The method can also be adapted for updating, downdating and perturbing the matrix, and is especially efficient relative to previous algorithms for such purposes.  

Robust principal component analysis and low-rank matrix completion are extensions of PCA that allow for outliers and missing entries, respectively. Solving these problems requires a low coherence between the low-rank matrix and the canonical basis. However, in both problems the well-posedness issue is even more fundamental; in some cases, both Robust PCA and matrix completion can fail to have any solutions due to the fact that the set of low-rank plus sparse matrices is not closed. Another consequence of this fact is that the lower restricted isometry property (RIP) bound cannot be satisfied for some low-rank plus sparse matrices unless further restrictions are imposed on the constituents. By restricting the energy of one of the components, we close the set and are able to derive the RIP over the set of low rank plus sparse matrices and operators satisfying concentration of measure inequalities. We show that the RIP of an operator implies exact recovery of a low-rank plus sparse matrix is possible with computationally tractable algorithms such as convex relaxations or line-search methods. We propose two efficient iterative methods called Normalized Iterative Hard Thresholding (NIHT) and Normalized Alternative Hard Thresholding (NAHT) that provably recover a low-rank plus sparse matrix from subsampled measurements taken by an operator satisfying the RIP.