Large-scale finite-dimensional optimization problems sometimes admit solutions that can be well approximated by low-rank matrices and tensors. In this talk, we will exploit this low-rank approximation property by solving the optimization problem directly over the set of low rank matrices and tensors. In particular, we introduce a new multilevel algorithm, where the optimization variable is constrained to the Riemannian manifold of fixed-rank matrices, allowing to keep the ranks (and thus the computational complexity) fixed throughout the iterations. This is a joint work with Bart Vandereycken.
We consider the task of approximating the eigenspace belonging to the lowest eigenvalues of a self adjoint operator on a space of matrices, with the condition that it is spanned by low rank matrices that share a common row space of small dimension. Such a problem arises for example in the DMRG algorithm in quantum chemistry. We propose a Riemannian optimization method based on trace minimization that takes orthogonality and low rank constraints into account simultaneously, and shows better numerical results in certain scenarios compared to other current methods.
Blind deconvolution is an ill-posed problem aiming to recover a convolution kernel and an activation signal from their convolution. We focus on the short and sparse variant, where the convolution kernel is short and the activation signal is sparsely and randomly supported. This variant models convolutional signals in several important application scenarios. The observation is invariant up to some mutual scaling and shift of the convolutional pairs. This scaled-shift symmetry is intrinsic to the convolution operator and imposes challenges for reliable algorithm design. We normalize the convolution kernel to have unit Frobenius norm and then cast the blind deconvolution problem as a nonconvex optimization problem over the sphere. We demonstrate that (i) under conditions, every local optimum is close to some shift truncation of the ground truth, and (ii) for a generic filter of length k, when the sparsity of activation signal satisfies θ < k^{3/4} and number of measurements m > poly(k), provable recovery of the ground truth signals can be obtained.