论文标题
局部搜索稀疏反身广义倒置的实验分析
Experimental analysis of local searches for sparse reflexive generalized inverses
论文作者
论文摘要
众所周知的M-P（Moore-Penrose）伪源用于几种线性代数应用。例如，计算线性方程式不一致系统的最小二乘解决方案。不管给定矩阵是否稀疏，其M-P假数都可能完全致密，可能会导致高计算负担和数值困难，尤其是当我们处理高维矩阵时。 M-p伪源是四个属性的唯一特征，但并非所有这些都需要满足某些应用程序。在这种情况下，Fampa和Lee（Oper。Res。Letters，46：605--610，2018）和Xu，Fampa，Lee和Ponte（出现优化的Siam J.）提出了本地搜索程序，以构建仅满足M-P属性的稀疏块结构化的广义逆，从而构建了稀疏的块结构化的广义逆。 （矢量）1-符号最小化用于诱导稀疏性并保持条目的幅度，并且理论结果限制了局部搜索溶液的1纳米与具有相应特性的概括性倒置的最小1-概念之间的距离。我们已经根据这两篇论文中提出的结果实施了几种本地搜索程序，并在这里对它们进行了实验分析，考虑到它们在随机生成的各个维度，等级和密度的随机矩阵中的应用。此外，我们对现实世界数据集进行了案例研究。
The well-known M-P (Moore-Penrose) pseudoinverse is used in several linear-algebra applications; for example, to compute least-squares solutions of inconsistent systems of linear equations. Irrespective of whether a given matrix is sparse, its M-P pseudoinverse can be completely dense, potentially leading to high computational burden and numerical difficulties, especially when we are dealing with high-dimensional matrices. The M-P pseudoinverse is uniquely characterized by four properties, but not all of them need to be satisfied for some applications. In this context, Fampa and Lee (Oper. Res. Letters, 46:605--610, 2018) and Xu, Fampa, Lee and Ponte (SIAM J. on Optimization, to appear) propose local-search procedures to construct sparse block-structured generalized inverses that satisfy only some of the M-P properties. (Vector) 1-norm minimization is used to induce sparsity and to keep the magnitude of the entries under control, and theoretical results limit the distance between the 1-norm of the solution of the local searches and the minimum 1-norm of generalized inverses with corresponding properties. We have implemented several local-search procedures based on results presented in these two papers and make here an experimental analysis of them, considering their application to randomly generated matrices of varied dimensions, ranks, and densities. Further, we carried out a case study on a real-world data set.
