针对稀疏数据设计更鲁棒的非负矩阵分解方法,提升抗噪能力和计算效率。
Nonnegative Matrix Factorization in the Component-Wise L1 Norm for Sparse Data
- 采用分量级L1范数,增强对重尾噪声和异常值的鲁棒性。
- 提出加权L1-NMF模型,通过惩罚参数控制因子稀疏度,避免虚假零点导致过稀疏。
- 设计稀疏坐标下降算法sCD,复杂度与非零元素数成正比,适合大规模稀疏数据。
非负矩阵分解(NMF)将非负矩阵 $X$ 近似为两个非负因子 $W$ 与 $H$ 的乘积,其中 $W$ 有 $r$ 列,$H$ 有 $r$ 行。本文研究以分量级L1范数为误差度量的NMF(L1-NMF),该方法适用于受重尾噪声(如拉普拉斯噪声或椒盐噪声)污染或存在异常值的数据。首个贡献是证明即使在 $r=1$ 时,L1-NMF 仍为 NP-hard,而标准NMF使用最小二乘法则不然。第二个贡献表明,L1-NMF 对稀疏输入矩阵能强烈促进因子稀疏性,提高可解释性;但若数据含虚假零点,过稀疏解可能降低模型性能。第三个贡献提出一种更通用的L1-NMF模型——加权L1-NMF(wL1-NMF),通过向数据中零值对应的 $WH$ 项添加惩罚参数来调控稀疏度。第四个贡献是为wL1-NMF设计一种新型坐标下降(CD)方法,称为稀疏CD(sCD),其子问题通过加权中位数算法求解。据我们所知,sCD 是首个复杂度随数据非零元素数量增长的L1-NMF算法,使其在处理大规模稀疏数据时高效。我们在合成数据和真实世界数据上进行了广泛的数值实验,验证了新模型(wL1-NMF)和算法(sCD)的有效性。
原文摘要 · Abstract (English)
Nonnegative matrix factorization (NMF) approximates a nonnegative matrix, $X$, by the product of two nonnegative factors, $WH$, where $W$ has $r$ columns and $H$ has $r$ rows. In this paper, we consider NMF using the component-wise L1 norm as the error measure (L1-NMF), which is suited for data corrupted by heavy-tailed noise, such as Laplace noise or salt and pepper noise, or in the presence of outliers. Our first contribution is an NP-hardness proof for L1-NMF, even when $r=1$, in contrast to the standard NMF that uses least squares. Our second contribution is to show that L1-NMF strongly enforces sparsity in the factors for sparse input matrices, thereby favoring interpretability. However, if the data is affected by false zeros, too sparse solutions might degrade the model. Our third contribution is a new, more general, L1-NMF model for sparse data, dubbed weighted L1-NMF (wL1-NMF), where the sparsity of the factorization is controlled by adding a penalization parameter to the entries of $WH$ associated with zeros in the data. The fourth contribution is a new coordinate descent (CD) approach for wL1-NMF, denoted as sparse CD (sCD), where each subproblem is solved by a weighted median algorithm. To the best of our knowledge, sCD is the first algorithm for L1-NMF whose complexity scales with the number of nonzero entries in the data, making it efficient in handling large-scale, sparse data. We perform extensive numerical experiments on synthetic and real-world data to show the effectiveness of our new proposed model (wL1-NMF) and algorithm (sCD).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。