Efficient Proximal Mapping Computation for Low-Rank Inducing Norms
本文提出一个框架，将低秩诱导酉不变范数的近端映射计算简化为嵌套二分搜索，每次迭代只需解一个更简单的问题，并展示了低秩诱导Frobenius范数和谱范数的解析解。
Abstract Low-rank inducing unitarily invariant norms have been introduced to convexify problems with a low-rank/sparsity constraint. The most well-known member of this family is the so-called nuclear norm. To solve optimization problems involving such norms with proximal splitting methods, efficient ways of evaluating the proximal mapping of the low-rank inducing norms are needed. This is known for the nuclear norm, but not for most other members of the low-rank inducing family. This work supplies a framework that reduces the proximal mapping evaluation into a nested binary search, in which each iteration requires the solution of a much simpler problem. The simpler problem can often be solved analytically as demonstrated for the so-called low-rank inducing Frobenius and spectral norms. The framework also allows to compute the proximal mapping of increasing convex functions composed with these norms as well as projections onto their epigraphs.