Fitting a matrix of a given rank to data in a least squares sense can be done
very effectively using 2nd order methods such as Levenberg-Marquardt by
explicitly optimizing over a bilinear parameterization of the matrix. In
contrast, when applying more general singular value penalties, such as weighted
nuclear norm priors, direct optimization over the elements of the matrix is
typically used. Due to non-differentiability of the resulting objective
function, first order sub-gradient or splitting methods are predominantly used.
While these offer rapid iterations it is well known that they become inefficent
near the minimum due to zig-zagging and in practice one is therefore often
forced to settle for an approximate solution.
In this paper we show that more accurate results can in many cases be
achieved with 2nd order methods. Our main result shows how to construct
bilinear formulations, for a general class of regularizers including weighted
nuclear norm penalties, that are provably equivalent to the original problems.
With these formulations the regularizing function becomes twice differentiable
and 2nd order methods can be applied. We show experimentally, on a number of
structure from motion problems, that our approach outperforms state-of-the-art
methods.

本文论述了如何在数据中拟合给定秩的矩阵以及如何比一阶梯度方法更多效地处理特殊矩阵约束，如加权核范数的惩罚，并在多项结构运动问题上实现优于现有方法的实验结果。

非刚性结构运动加权核范数的精确优化

Accurate Optimization of Weighted Nuclear Norm for Non-Rigid Structure  from Motion

Matrix completion, i.e., the exact and provable recovery of a low-rank matrix
from a small subset of its elements, is currently only known to be possible if
the matrix satisfies a restrictive structural constraint---known as {\em
incoherence}---on its row and column spaces. In these cases, the subset of
elements is sampled uniformly at random.
In this paper, we show that {\em any} rank-$ r $ $ n$-by-$ n $ matrix can be
exactly recovered from as few as $O(nr \log^2 n)$ randomly chosen elements,
provided this random choice is made according to a {\em specific biased
distribution}: the probability of any element being sampled should be
proportional to the sum of the leverage scores of the corresponding row, and
column. Perhaps equally important, we show that this specific form of sampling
is nearly necessary, in a natural precise sense; this implies that other
perhaps more intuitive sampling schemes fail.
We further establish three ways to use the above result for the setting when
leverage scores are not known \textit{a priori}: (a) a sampling strategy for
the case when only one of the row or column spaces are incoherent, (b) a
two-phase sampling procedure for general matrices that first samples to
estimate leverage scores followed by sampling for exact recovery, and (c) an
analysis showing the advantages of weighted nuclear/trace-norm minimization
over the vanilla un-weighted formulation for the case of non-uniform sampling.

本文提出了一种特定偏向分布的采样方式，利用该采样方式可以从少量采样的数据中精确恢复任何秩为 r 的 nxn 的矩阵（无需满足之前已有的结构限制要求），而且在没有先验信息下本文建立了三种使用该采样方式的方法，其中还包括分析了针对非均匀采样情形中，加权核范数 / 迹范数惩罚的优点。

可证明地补全任意低秩矩阵

Completing Any Low-rank Matrix, Provably

This paper is about iteratively reweighted basis-pursuit algorithms for
compressed sensing and matrix completion problems. In a first part, we give a
theoretical explanation of the fact that reweighted basis pursuit can improve a
lot upon basis pursuit for exact recovery in compressed sensing. We exhibit a
condition that links the accuracy of the weights to the RIP and incoherency
constants, which ensures exact recovery. In a second part, we introduce a new
algorithm for matrix completion, based on the idea of iterative reweighting.
Since a weighted nuclear "norm" is typically non-convex, it cannot be used
easily as an objective function. So, we define a new estimator based on a
fixed-point equation. We give empirical evidences of the fact that this new
algorithm leads to strong improvements over nuclear norm minimization on
simulated and real matrix completion problems.

本文研究了基于迭代加权最小二乘算法的压缩感知和矩阵补全问题。首先，我们给出了加权基追踪算法在确切恢复压缩感知信号方面比基追踪算法具有改进的理论解释。然后，我们提出了一种新的矩阵补全算法，该算法基于迭代加权的思想，并利用一个固定点方程定义了一个新的估计器，可以强化核范数的性能。本文在模拟和实际矩阵补全问题中，对该新算法作了实证检验，结果表明该算法在性能上具有很大的提高。