  We investigate the problem of recovering a partially observed high-rank
matrix whose columns obey a nonlinear structure such as a union of subspaces,
an algebraic variety or grouped in clusters. The recovery problem is formulated
as the rank minimization of a nonlinear feature map applied to the original
matrix, which is then further approximated by a constrained non-convex
optimization problem involving the Grassmann manifold. We propose two sets of
algorithms, one arising from Riemannian optimization and the other as an
alternating minimization scheme, both of which include first- and second-order
variants.
  Both sets of algorithms have theoretical guarantees. In particular, for the
alternating minimization, we establish global convergence and worst-case
complexity bounds. Additionally, using the Kurdyka-Lojasiewicz property, we
show that the alternating minimization converges to a unique limit point.
  We provide extensive numerical results for the recovery of union of subspaces
and clustering under entry sampling and dense Gaussian sampling. Our methods
are competitive with existing approaches and, in particular, high accuracy is
achieved in the recovery using Riemannian second-order methods.
