Abstract : Due to their simplicity and versality that ranges from genomics data to computational physics, recommender systems and unsupervised learning, low-rank matrix models have emerged as a powerful tool in data science. However, only few related computational problems admit closed-form solutions. Convex or non-convex potentially non-smooth optimization problems with different statistical properties can be used to overcome involving computational challenges.
This minisymposium intends to shed light on recent advances in structured numerical optimization for low-rank models and their statistical and information theoretical properties by bringing together experts from applied mathematics and engineering working these topics, providing a forum for future collaborations.
Organizer(s) : Christian Kümmerle, Johannes Maly, Dominik Stöger
02392 (1/3) : 2C @G306 [Chair: Christian Kümmerle]
[02769] Low-rank models in data science: Applications and optimization challenges
Format : Online Talk on Zoom
Author(s) :
Dominik Stöger (KU Eichstätt-Ingolstadt)
Abstract : Low-rank matrix models have emerged as a powerful tool in data science with applications ranging from recommender systems to computational physics. In this overview talk, we first highlight some applications where low-rank models arise. Next, we discuss which statistical and optimization challenges arise. Moreover, we highlight several advances which have been made in recent years to circumvent these issues.
[05455] Low Rank Matrix Recovery from Column-wise Projections: Fast and Communication-Efficient Solutions
Format : Online Talk on Zoom
Author(s) :
Namrata Vaswani (Iowa State University)
Abstract : We study the following lesser-known low rank (LR) recovery problem: recover an n × q rank-r matrix, $X^* = [ x^*_1 , x^*_2 ,..., x^*_q]$, with $r << min(n, q)$, from m independent linear projections of each of its $q$ columns, i.e., from $y_k := A_k x^*_k , k \in [q]$, when $y_k$ is an m-length vector with m < n . The matrices $A_k$ are known and mutually independent for different k. We introduce a novel gradient descent (GD) based solution called AltGD-Min. We show that, if the $A_k$'s are i.i.d. with i.i.d. Gaussian entries, and if the right singular vectors of $X^*$ satisfy the incoherence assumption, then \epsilon-accurate recovery of X* is possible with order $(n + q) r^2 log(1/\epsilon)$ total samples and order $mqnr log(1/\epsilon)$ time. Compared with existing work, this is the fastest solution, and in most practical settings, it also has the best sample complexity. For a federated implementation, it is also communication-efficient with a cost of only order $nr$ per node per iteration.
A simple extension of AltGD-Min also provably solves the LR Phase Retrieval problem, which is a magnitude-only measurements' extension of the above problem.
[04491] Tensor-Norm Approaches to Low-Rank Matrix Recovery by Convex Program
Format : Online Talk on Zoom
Author(s) :
Kiryung Lee (Ohio State University)
Abstract : Low-rank models have been shown effective for solving various inverse problems from classical system identification to modern matrix completion and sketching in signal processing and statistics. If each observation is a linear combination of a subset of matrix entries, the reconstruction is feasible only for a class of matrices incoherent to the measurement process. We propose an estimator that prefers a solution with low rankness and incoherence by a regularizer given by a pair of norms on the tensor product of two Banach spaces. The resulting optimization is cast as a convex semidefinite program and provides a near-optimal error matching the corresponding minimax bound in a low signal-to-noise ratio regime. We illustrate the efficacy of the estimator over selected applications in signal processing. We also present a scalable numerical optimization algorithm and study its empirical performance over large-scale synthesized data.
[04277] Algorithmic approaches to recovering sparse and low-rank matrices
Format : Talk at Waseda University
Author(s) :
Johannes Maly (Ludwig-Maximilians-Universität München)
Abstract : In this talk, I consider the problem of recovering an unknown sparse and low-rank matrix X from measurements gathered in a linear measurement process. I discuss the challenges that come with leveraging several structures simultaneously and present two new algorithmic strategies to efficiently approach the problem. Both strategies come with local convergence guarantees.
[03939] Bures-Wasserstein Methods in Matrix Recovery
Format : Online Talk on Zoom
Author(s) :
Tyler Maunu (Brandeis University)
Abstract : We revisit the problem of recovering a positive semidefinite matrix from a linear map using tools from optimal transport. More specifically, we connect a variational formulation of this problem to the computation of Wasserstein barycenters. This new perspective enables the development of efficient first-order geometric methods. Experiments demonstrate the advantages of our new methodology over existing methods. We also discuss extensions to recovery in other settings of restricted positive semidefinite matrices.
[05442] Improved Global Guarantees for Low-Rank Models via Rank Overparameterization
Format : Talk at Waseda University
Author(s) :
Richard Y Zhang (University of Illinois at Urbana-Champaign)
Abstract : We consider minimizing a twice-differentiable, $L$-smooth, and $\mu$-strongly
convex objective $\phi$ over an $n\times n$ positive semidefinite
matrix $M\succeq0$, under the assumption that the minimizer $M^{\star}$
has low rank $r^{\star}\ll n$. Following the Burer--Monteiro approach,
we instead minimize the nonconvex objective $f(X)=\phi(XX^{T})$ over
a factor matrix $X$ of size $n\times r$. This substantially reduces
the number of variables from $O(n^{2})$ to as few as $O(n)$ and
also enforces positive semidefiniteness for free, but at the cost
of giving up the convexity of the original problem. In this talk,
we prove that if the search rank $r\ge r^{\star}$ is overparameterized
by a \emph{constant factor} with respect to the true rank $r^{\star}$,
namely as in $r>\frac{1}{4}(L/\mu-1)^{2}r^{\star}$, then despite
nonconvexity, local optimization is guaranteed to globally converge
from any initial point to the global optimum. This significantly improves
upon a previous rank overparameterization threshold of $r\ge n$,
which is known to be sharp if $\phi$ is allowed to be nonsmooth and/or
non-strongly convex, but would increase the number of variables back
up to $O(n^{2})$. Conversely, without rank overparameterization,
we prove that such a global guarantee is possible if and only if $\phi$
is almost perfectly conditioned, with a condition number of $L/\mu<3$.
Therefore, we conclude that a small amount of overparameterization
can lead to large improvements in theoretical guarantees for the nonconvex
Burer--Monteiro factorization.
[04377] Tensor Completion via Tensor Train Based Low-Rank Quotient Geometry under a Preconditioned Metric
Format : Talk at Waseda University
Author(s) :
Ke Wei (Fudan University)
Abstract : Low-rank tensor completion problem is about recovering a tensor from partially observed entries. We consider this problem in the tensor train format and extend the preconditioned metric from the matrix case to the tensor case. The first-order and second-order quotient geometry of the manifold of fixed tensor train rank tensors under this metric is studied in detail. Algorithms, including Riemannian gradient descent, Riemannian conjugate gradient, and Riemannian Gauss-Newton, have been proposed for the tensor completion problem based on the quotient geometry. It has also been shown that the Riemannian Gauss-Newton method on the quotient geometry is equivalent to the Riemannian Gauss-Newton method on the embedded geometry with a specific retraction. Empirical evaluations on random instances as well as on function-related tensors show that the proposed algorithms are competitive with other existing algorithms in terms of completion ability, convergence performance, and completion quality.
[04975] Iteratively Reweighted Least Squares for Low-Rank Optimization: Optimality & Convergence Rates
Format : Talk at Waseda University
Author(s) :
Christian Kümmerle (University of North Carolina at Charlotte)
Abstract : Convex or non-convex matrix functions such as Schatten-p (quasi-)norms have been successfully used as surrogates of the rank objective. Iteratively Reweighted Least Squares (IRLS) has emerged as a suitable algorithmic framework to scalably optimize such rank surrogates. We review the formulation, optimality and empirical data-efficiency of MatrixIRLS. We show that the algorithm, which optimizes Schatten-type objectives, exhibits a local superlinear convergence rate with a large basin of attraction, and linear convergence rates in the convex case.
Abstract : Phase retrieval is the non-convex inverse problem of signal reconstruction from its intensity measurements that is motivated by practical applications. In the talk, we are going to focus on phase retrieval with multi-window Gabor frames, where the measurement vectors follow time-frequency structure natural for imaging and acoustics. We will propose an explicit construction of such frames and show that for them phase retrievability can be achieved with a close to optimal number of phaseless measurements.
