摘要翻译:
仿射秩最小化问题是求满足给定线性等式约束系统的最小秩矩阵。这些问题已经出现在包括系统辨识和控制、欧几里德嵌入和协同过滤等不同领域的文献中。一般仿射秩最小化问题是NP难问题,但一般的仿射秩最小化问题通常可以用专门的算法求解。本文证明了如果定义约束的线性变换具有一定的约束等距性,则通过求解凸优化问题,即核范数在给定仿射空间上的极小化,可以恢复最小秩解。我们给出了几个方程的随机系综,其中限制等距性质以压倒性概率成立。在我们的分析中使用的技术在压缩感知框架中有很强的相似性。我们讨论了仿射秩最小化如何推广这个已有的概念,并勾勒出一个从基数最小化到秩最小化的相关概念的字典。
---
英文标题:
《Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear
Norm Minimization》
---
作者:
Benjamin Recht and Maryam Fazel and Pablo A. Parrilo
---
最新提交年份:
2007
---
分类信息:
一级分类:Mathematics 数学
二级分类:Optimization and Control 优化与控制
分类描述:Operations research, linear programming, control theory, systems theory, optimal control, game theory
运筹学,线性规划,控制论,系统论,最优控制,博弈论
--
一级分类:Mathematics 数学
二级分类:Statistics Theory 统计理论
分类描述:Applied, computational and theoretical statistics: e.g. statistical inference, regression, time series, multivariate analysis, data analysis, Markov chain Monte Carlo, design of experiments, case studies
应用统计、计算统计和理论统计:例如统计推断、回归、时间序列、多元分析、数据分析、马尔可夫链蒙特卡罗、实验设计、案例研究
--
一级分类:Statistics 统计学
二级分类:Statistics Theory 统计理论
分类描述:stat.TH is an alias for math.ST. Asymptotics, Bayesian Inference, Decision Theory, Estimation, Foundations, Inference, Testing.
Stat.Th是Math.St的别名。渐近,贝叶斯推论,决策理论,估计,基础,推论,检验。
--
---
英文摘要:
The affine rank minimization problem consists of finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems have appeared in the literature of a diverse set of fields including system identification and control, Euclidean embedding, and collaborative filtering. Although specific instances can often be solved with specialized algorithms, the general affine rank minimization problem is NP-hard. In this paper, we show that if a certain restricted isometry property holds for the linear transformation defining the constraints, the minimum rank solution can be recovered by solving a convex optimization problem, namely the minimization of the nuclear norm over the given affine space. We present several random ensembles of equations where the restricted isometry property holds with overwhelming probability. The techniques used in our analysis have strong parallels in the compressed sensing framework. We discuss how affine rank minimization generalizes this pre-existing concept and outline a dictionary relating concepts from cardinality minimization to those of rank minimization.
---
PDF链接:
https://arxiv.org/pdf/706.4138