【泡泡一分钟】非凸秩/稀疏正则化和局部最小化(ICCV2017-32)

会员服务 ·

【泡泡一分钟】非凸秩/稀疏正则化和局部最小化(ICCV2017-32)

2018 年 6 月 6 日 泡泡机器人SLAM

每天一分钟，带你读遍机器人顶级会议文章

标题：Non-Convex Rank/Sparsity Regularization and Local Minima

作者：Carl Olsson, Marcus Carlsson, Fredrik Andersson, Viktor Larsson

来源：International Conference on Computer Vision (ICCV 2017)

播音员：格子

编译：杨雨生(35)

欢迎个人转发朋友圈；其他机构或自媒体如需转载，后台留言申请授权

摘要

本文研究的问题是，通过观察向量或者矩阵元素的线性组合，从而恢复一个低秩矩阵或者一个稀疏向量。

最新的方法采用L1范数或者核函数松弛的方法, 取代之前的非凸正则化方法。众所周知，如果所谓的有限等距性质（RIP）满足的话，这种方法几乎可以实现最优解。但另一方面，这种方法也存在收缩偏差（shrinking bias）现象，从而降低所求解的准确性。

本文中，我们研究一种可以避免这种偏差的可替代非凸正则化方法。由于当差别很大的时候，必然是高秩，我们的主要理论成果表明，如果RIP性质满足的话，可以很好的将静止点分离出来。因此，在初始值恰当的情况下，这种方法不会陷入一个局部最小值。我们的数值试验表明，即使是从一个随意初始值开始，这种方法也比标准的L1范数-或核范数-松弛方法更好的收敛。我们的试验结果同样可以用来验证我们方法的全局最优性。

Abstract

This paper considers the problem of recovering either a low rank matrix or a sparse vector from observations of linear combinations of the vector or matrix elements. Recent methods replace the non-convex regularization with L1 or nuclear norm relaxations. It is well known that this approach recovers near optimal solutions if a so called restricted isometry property (RIP) holds. On the other hand， it also has a shrinking bias which can degrade the solution. In this paper， we study an alternative non-convex regularization term that does not suffer from this bias. Our main theoretical results show that if a RIP holds then the stationary points are often well separated, in the sense that their differences must be of high cardinality/rank. Thus, with a suitable initial solution the approach is unlikely to fall into a bad local minimum. Our numerical tests show that the approach is likely to converge to a better solution than standard L1/nuclear-norm relaxation even when starting from trivial initializations. In many cases our results can also be used to verify global optimality of our method.

如果你对本文感兴趣，想要下载完整文章进行阅读，可以关注【泡泡机器人SLAM】公众号（paopaorobot_slam）。

欢迎来到泡泡论坛，这里有大牛为你解答关于SLAM的任何疑惑。

有想问的问题，或者想刷帖回答问题，泡泡论坛欢迎你！

泡泡网站：www.paopaorobot.org

泡泡论坛：http://paopaorobot.org/forums/