基于均值的Toeplitz矩阵填充的子空间算法

本文提出一种基于均值的Toeplitz矩阵填充的子空间算法.通过在左奇异向量空间中对已知元素的最小二乘逼近,形成了新的可行矩阵;并利用对角线上的均值化使得迭代后的矩阵保持Toeplitz结构,从而减少了奇异向量空间的分解时间.理论上,证明了在一定条件下该算法收敛于一个低秩的Toeplitz矩阵.通过不同已知率的矩阵填充数值实验展示了Toeplitz矩阵填充的新算法比阈值增广Lagrange乘子算法在时间上和精度上更有效.     

规范权Bergman空间上Toeplitz算子的本性范数

设1

ω~p上非紧Toeplitz算子T_μ的本性范数等于其到紧Toeplitz算子集合的距离.更进一步,本文给出了此距离可以用无限个紧Toeplitz算子刻画.     

一四元数矩阵方程组的最佳逼近解

利用四元数矩阵的广义Frobenius范数和弱圈积,建立一个关于四元数矩阵的实函数并简洁表征其极小值.再用四元数矩阵的奇异值分解和广义Frobenius范数的性质,讨论四元数矩阵方程组[AX,XB]=[C,D]的最小二乘解,得到了解的具体表达式.最后在该方程组的解集合中导出了与给定矩阵的最佳逼近解的表达式.     

Toeplitz矩阵填充的保结构算法

本文以奇异值阈值方法为基础,运用二次规划技术,提出一种新的Toeplitz矩阵填充的保结构算法,算法保证每次迭代产生的填充矩阵是可行的Toeplitz矩阵;同时运用核范数的次梯度和正交理论给出算法收敛性分析;最后通过数值实验以及简单的图像修复证明新的算法比阈值的增广Lagrange乘子算法更有效.     

四元数Sylvester方程的Toeplitz约束解及其最佳逼近

本文研究了四元数体上Sylvester方程具有Toeplitz矩阵约束解及其最佳逼近问题.利用四元数矩阵的实分解和矩阵Kronecker积,获得四元数Sylvester方程AX-XB=C具有Toeplitz矩阵解的充要条件及其通解表达式.同时在Toeplitz解集合中,得到与预先给定的四元数Toeplitz矩阵有极小Frobenius范数的最佳逼近解.     

四元数矩阵方程AX-YB=C的最佳逼近解

本利用四元数矩阵的广义Frobenius范数建立一个关于四元数矩阵的实函数，并讨论了它的极值问题．然后在四元数矩阵方程AX-YB=C的解集合中导出了与给定矩阵的最佳逼近解的表达式．     

Toeplitz方程组极小范数最小二乘解的快速算法

给出了求以m×n阶Toeplitz矩阵为系数阵的线性方程组极小范数最小二乘解的快速算法.     

四元数矩阵方程AX+YA=C的两种最佳逼近解

利用四元数矩阵的广义Frobenius范数建立一个关于四元数矩阵的实函数,并讨论了它的极值问题,然后在四元数矩阵方程AX YA=C的一般解和自共轭解集合中分别导出了与给定相同类型矩阵的最佳逼近解的表达式.     

矩阵填充的子空间逼近法

本文提出了一种矩阵填充的子空间逼近法.该算法以奇异值分解的子空间逼近为基础,运用二次规划技术产生子空间中最接近的可行矩阵,从而获得较好的可行矩阵.该算法通过阈值的奇异值个数逐步减少达到子空间的降秩,最后得到最优低秩矩阵.本文证明了在一定条件下子空间逼近法是收敛的.通过与增广Lagrange乘子算法和正交秩1矩阵逼近法进行随机实验对比,本文所提方法在CPU时间和低秩性上均更有效.     

Toeplitz矩阵填充的 $\ell$-步修正增广拉格朗日乘子算法[英文]

基于 Toeplitz矩阵填充(TMC)的修正增广拉格朗日乘子(MALM)算法, 本文给出此算法的一种加速策略, 提出Toeplitz矩阵填充的 $\ell$-步修正增广拉格朗日乘子算法. 该方法通过削减原 MALM算法中每一步迭代的频繁数据传输, 提高算法的运行效率. 同时也证明了新算法的收敛性. 最后以数值实验表明 $\ell$-步修正增广拉格朗日乘子算法比原 MALM算法更有效.     

核范数和谱范数下广义Sylvester方程最小二乘问题的有效算法

本文从数值角度讨论Schatten q-范数下的广义Sylvester方程约束最小二乘问题min x∈s‖N∑i=1A_iXB_i—C‖_q,其中S为闭凸约束集合,Schatten q-范数定义为‖M‖_q~q=∑_(i=1)~nσ_i~q(M),其中σ_i(M)为M∈R~(n×n)的奇异值.该问题的几类特殊情形在图像处理、控制论等领域有广泛的应用.q=2即Frobenius范数下该问题已被充分研究,故本文着重讨论q=1,+∞,即核范数和谱范数下该问题的数值求解.采用的数值方法是非精确标准容易执行的部分非精确交替方向法,并结合奇异值阈值算法,Moreau-Yosida正则化算法,谱投影算法和LSQR算法等求解相应子问题.给出算法的收敛性证明,并用数值算例验证其高效可行性.     

A mean value algorithm for Toeplitz matrix completion

In this paper, we propose a new mean value algorithm for the Toeplitz matrix completion based on the singular value thresholding (SVT) algorithm. The completion matrices generated by the new algorithm keep a feasible Toeplitz structure. Meanwhile, we prove the convergence of the new algorithm under some reasonal conditions. Finally, we show the new algorithm is much more effective than the ALM (augmented Lagrange multiplier) algorithm through numerical experiments and image inpainting.     

用随机奇异值分解算法求解矩阵恢复问题

本文研究了大型低秩矩阵恢复问题.利用随机奇异值分解（RSVD）算法,对稀疏矩阵做奇异值分解.该算法与Lanczos方法相比,在误差精度一致的同时运算时间大大降低,且该算法对相对低秩矩阵也有效.     

矩阵方程AXB+CYD=E的M对称解的迭代算法

在共轭梯度思想的启发下,结合线性投影算子,给出迭代算法求解了线性矩阵方程AXB+CYD=E的M对称解[X,Y]及其最佳逼近.当矩阵方程AXB+CYD=E有M对称解时,应用迭代算法,在有限的误差范围内,对任意初始M对称矩阵对[X_,Y_1],经过有限步迭代可得到矩阵方程的M对称解;选取合适的初始迭代矩阵,还可得到极小范数M对称解.而且,对任意给定的矩阵对[X,Y],矩阵方程AXB+CYD=E的最佳逼近可以通过迭代求解新的矩阵方程AXB+CYD=E的极小范数M对称解得到.文中的数值例子证实了该算法的有效性.     

矩阵方程AX=B,XC=D的定秩解

本文研究了一类矩阵方程组解的秩的范围.利用矩阵的奇异值分解以及Frobenius范数的特征,得到了解的极值秩以及解的通式,并就这些问题的特殊情况进行了讨论,得到了一些结果.     

Fixed point and Bregman iterative methods for matrix rank minimization

The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm, which we call FPCA (Fixed Point Continuation with Approximate SVD), that can solve very large matrix rank minimization problems (the code can be downloaded from http://www.columbia.edu/~sm2756/FPCA.htm for non-commercial use). Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3. For example, our algorithm can recover 1000 × 1000 matrices of rank 50 with a relative error of 10^?5 in about 3?min by sampling only 20% of the elements. We know of no other method that achieves as good recoverability. Numerical experiments on online recommendation, DNA microarray data set and image inpainting problems demonstrate the effectiveness of our algorithms.     

Convergence of Fixed-Point Continuation Algorithms for Matrix Rank Minimization

The matrix rank minimization problem has applications in many fields, such as system identification, optimal control, low-dimensional embedding, etc. As this problem is NP-hard in general, its convex relaxation, the nuclear norm minimization problem, is often solved instead. Recently, Ma, Goldfarb and Chen proposed a fixed-point continuation algorithm for solving the nuclear norm minimization problem (Math. Program., doi:, 2009). By incorporating an approximate singular value decomposition technique in this algorithm, the solution to the matrix rank minimization problem is usually obtained. In this paper, we study the convergence/recoverability properties of the fixed-point continuation algorithm and its variants for matrix rank minimization. Heuristics for determining the rank of the matrix when its true rank is not known are also proposed. Some of these algorithms are closely related to greedy algorithms in compressed sensing. Numerical results for these algorithms for solving affinely constrained matrix rank minimization problems are reported.     

低秩张量填充的加速随机临近梯度算法

本文提出了一种求解低秩张量填充问题的加速随机临近梯度算法.张量填充模型可以松弛为平均组合形式的无约束优化问题,在迭代过程中,随机选取该组合中的某一函数进行变量更新,有效减少了张量展开、矩阵折叠及奇异值分解带来的较大的计算花费.本文证明了算法的收敛率为$O (1/k^{2})$.最后,随机生成的和真实的张量填充实验结果表明新算法在CPU时间上优于现有的三种算法.