# Registered Data

## [02392] Low-Rank Models in Data Science

**Session Date & Time**:- 02392 (1/3) : 2C (Aug.22, 13:20-15:00)
- 02392 (2/3) : 2D (Aug.22, 15:30-17:10)
- 02392 (3/3) : 2E (Aug.22, 17:40-19:20)

**Type**: Proposal of Minisymposium**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**Classification**:__15A83__,__65F55__,__65K10__,__90C26__**Speakers Info**:**Christian Kümmerle**(University of North Carolina at Charlotte)- Kiryung Lee (Ohio State University)
- Johannes Maly (Ludwig-Maximilians-Universität Munich)
- Tyler Maunu (Brandeis University)
- Palina Salanevich (Utrecht University)
- Dominik Stöger (KU Eichstätt-Ingolstadt)
- Namrata Vaswani (Iowa State University)
- Ke Wei (Fudan University)
- Richard Y. Zhang (University of Illinois at Urbana-Champaign)

**Talks in Minisymposium**:**[02769] Low-rank models in data science: Applications and optimization challenges****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.

**[03939] Bures-Wasserstein Methods in Matrix Recovery****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.

**[04277] Algorithmic approaches to recovering sparse and low-rank matrices****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.

**[04377] Tensor Completion via Tensor Train Based Low-Rank Quotient Geometry under a Preconditioned Metric****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.

**[04491] Tensor-Norm Approaches to Low-Rank Matrix Recovery by Convex Program****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.

**[04701] Multi-window Gabor phase retrieval****Author(s)**:**Palina Salanevich**(Utrecht University)

**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.

**[04975] Iteratively Reweighted Least Squares for Low-Rank Optimization: Optimality & Convergence Rates****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.

**[05442] Improved Global Guarantees for Low-Rank Models via Rank Overparameterization****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.

**[05455] Low Rank Matrix Recovery from Column-wise Projections: Fast and Communication-Efficient Solutions****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.