Richard Y. Zhang

Simple Alternating Minimization Provably Solves Complete Dictionary Learning

  • lianggy
  • Gavin Zhang
  • Salar Fattahi
  • Richard Y. Zhang
    • Categories Optimization in Data Science

    This paper focuses on complete dictionary learning problem, where the goal is to reparametrize a set of given signals as linear combinations of atoms from a learned dictionary. There are two main challenges faced by theoretical and practical studies of dictionary learning: the lack of theoretical guarantees for practically-used heuristic algorithms, and their poor scalability … Read more

    Preconditioned Gradient Descent for Overparameterized Nonconvex Burer–Monteiro Factorization with Global Optimality Certification

  • Gavin Zhang
  • Salar Fattahi
  • Richard Y. Zhang
    • Categories Nonlinear Optimization Tags , ,

    We consider using gradient descent to minimize the nonconvex function $f(X)=\phi(XX^{T})$ over an $n\times r$ factor matrix $X$, in which $\phi$ is an underlying smooth convex cost function defined over $n\times n$ matrices. While only a second-order stationary point $X$ can be provably found in reasonable time, if $X$ is additionally \emph{rank deficient}, then its … Read more