Robust Principal Component Analysis Integrating Sparse and Low-Rank Priors

Principal Component Analysis (PCA) is a widely used technique for data analysis and dimensionality reduction, but its sensitivity to feature scale and outliers limits its applicability. Robust Principal Component Analysis (RPCA) addresses these limitations by decomposing data into a low-rank matrix capturing the underlying structure and a sparse matrix identifying outliers, enhancing robustness against noise and outliers. This paper introduces a novel RPCA variant, Robust PCA Integrating Sparse and Low-rank Priors (RPCA-SL). Each prior targets a specific aspect of the data’s underlying structure and their combination allows for a more nuanced and accurate separation of the main data components from outliers and noise. Then RPCA-SL is solved by employing a proximal gradient algorithm for improved anomaly detection and data decomposition. Experimental results on simulation and real data demonstrate significant advancements.

A SPARSE MATRIX TECHNIQUE FOR SIMULATING SEMICONDUCTOR DEVICES AND ITS ALGORITHMS

A novel sparse matrix technique for the numerical analysis of semiconductor devicesand its algorithms are presented.Storage scheme and calculation procedure of the sparse matrixare described in detail.The sparse matrix technique in the device simulation can decrease storagegreatly with less CPU time and its implementation is very easy.Some algorithms and calculationexamples to show the time and space characteristics of the sparse matrix are given.

Bounds for Polynomial’s Roots from Fiedler and Sparse Companion Matrices for Submultiplicative Matrix Norms

We use submultiplicative companion matrix norms to provide new bounds for roots for a given polynomial P(X) over the field C[X]. From a n×n Fiedler companion matrix C, sparse companion matrices and triangular Hessenberg matrices are introduced. Then, we identify a special triangular Hessenberg matrix Lr, supposed to provide a good estimation of the roots. By application of Gershgorin’s theorems to this special matrix in case of submultiplicative matrix norms, some estimations of bounds for roots are made. The obtained bounds have been compared to known ones from the literature precisely Cauchy’s bounds, Montel’s bounds and Carmichel-Mason’s bounds. According to the starting formel of Lr, we see that the more we have coefficients closed to zero with a norm less than 1, the more the Sparse method is useful.

Applying Analytical Derivative and Sparse Matrix Techniques to Large-Scale Process Optimization Problems

The performance of analytical derivative and sparse matrix techniques applied to a traditional dense sequential quadratic programming (SQP) is studied, and the strategy utilizing those techniques is also presented.Computational results on two typical chemical optimization problems demonstrate significant enhancement in efficiency, which shows this strategy is promising and suitable for large-scale process optimization problems.

Proximity point algorithm for low-rank matrix recovery from sparse noise corrupted data

The method of recovering a low-rank matrix with an unknown fraction whose entries are arbitrarily corrupted is known as the robust principal component analysis （RPCA）. This RPCA problem, under some conditions, can be exactly solved via convex optimization by minimizing a combination of the nuclear norm and the 11 norm. In this paper, an algorithm based on the Douglas-Rachford splitting method is proposed for solving the RPCA problem. First, the convex optimization problem is solved by canceling the constraint of the variables, and ~hen the proximity operators of the objective function are computed alternately. The new algorithm can exactly recover the low-rank and sparse components simultaneously, and it is proved to be convergent. Numerical simulations demonstrate the practical utility of the proposed algorithm.

Performance Prediction Based on Statistics of Sparse Matrix-Vector Multiplication on GPUs

As one of the most essential and important operations in linear algebra, the performance prediction of sparse matrix-vector multiplication (SpMV) on GPUs has got more and more attention in recent years. In 2012, Guo and Wang put forward a new idea to predict the performance of SpMV on GPUs. However, they didn’t consider the matrix structure completely, so the execution time predicted by their model tends to be inaccurate for general sparse matrix. To address this problem, we proposed two new similar models, which take into account the structure of the matrices and make the performance prediction model more accurate. In addition, we predict the execution time of SpMV for CSR-V, CSR-S, ELL and JAD sparse matrix storage formats by the new models on the CUDA platform. Our experimental results show that the accuracy of prediction by our models is 1.69 times better than Guo and Wang’s model on average for most general matrices.

Cache performance optimization of irregular sparse matrix multiplication on modern multi-core CPU and GPU

This paper focuses on how to optimize the cache performance of sparse matrix-matrix multiplication(SpGEMM).It classifies the cache misses into two categories;one is caused by the irregular distribution pattern of the multiplier-matrix,and the other is caused by the multiplicand.For each of them,the paper puts forward an optimization method respectively.The first hash based method removes cache misses of the 1 st category effectively,and improves the performance by a factor of 6 on an Intel 8-core CPU for the best cases.For cache misses of the 2nd category,it proposes a new cache replacement algorithm,which achieves a cache hit rate much higher than other historical knowledge based algorithms,and the algorithm is applicable on CELL and GPU.To further verify the effectiveness of our methods,we implement our algorithm on GPU,and the performance perfectly scales with the size of on-chip storage.

Randomized Latent Factor Model for High-dimensional and Sparse Matrices from Industrial Applications

Latent factor(LF) models are highly effective in extracting useful knowledge from High-Dimensional and Sparse(HiDS) matrices which are commonly seen in various industrial applications. An LF model usually adopts iterative optimizers,which may consume many iterations to achieve a local optima,resulting in considerable time cost. Hence, determining how to accelerate the training process for LF models has become a significant issue. To address this, this work proposes a randomized latent factor(RLF) model. It incorporates the principle of randomized learning techniques from neural networks into the LF analysis of HiDS matrices, thereby greatly alleviating computational burden. It also extends a standard learning process for randomized neural networks in context of LF analysis to make the resulting model represent an HiDS matrix correctly.Experimental results on three HiDS matrices from industrial applications demonstrate that compared with state-of-the-art LF models, RLF is able to achieve significantly higher computational efficiency and comparable prediction accuracy for missing data.I provides an important alternative approach to LF analysis of HiDS matrices, which is especially desired for industrial applications demanding highly efficient models.

Truncated sparse approximation property and truncated q-norm minimization

This paper considers approximately sparse signal and low-rank matrix’s recovery via truncated norm minimization minx∥xT∥q and minX∥XT∥Sq from noisy measurements.We first introduce truncated sparse approximation property,a more general robust null space property,and establish the stable recovery of signals and matrices under the truncated sparse approximation property.We also explore the relationship between the restricted isometry property and truncated sparse approximation property.And we also prove that if a measurement matrix A or linear map A satisfies truncated sparse approximation property of order k,then the first inequality in restricted isometry property of order k and of order 2k can hold for certain different constantsδk andδ2k,respectively.Last,we show that ifδs(k+|T^c|)<√(s-1)/s for some s≥4/3,then measurement matrix A and linear map A satisfy truncated sparse approximation property of order k.It should be pointed out that when Tc=Ф,our conclusion implies that sparse approximation property of order k is weaker than restricted isometry property of order sk.

Robust Latent Factor Analysis for Precise Representation of High-Dimensional and Sparse Data

High-dimensional and sparse(HiDS)matrices commonly arise in various industrial applications,e.g.,recommender systems(RSs),social networks,and wireless sensor networks.Since they contain rich information,how to accurately represent them is of great significance.A latent factor(LF)model is one of the most popular and successful ways to address this issue.Current LF models mostly adopt L2-norm-oriented Loss to represent an HiDS matrix,i.e.,they sum the errors between observed data and predicted ones with L2-norm.Yet L2-norm is sensitive to outlier data.Unfortunately,outlier data usually exist in such matrices.For example,an HiDS matrix from RSs commonly contains many outlier ratings due to some heedless/malicious users.To address this issue,this work proposes a smooth L1-norm-oriented latent factor(SL-LF)model.Its main idea is to adopt smooth L1-norm rather than L2-norm to form its Loss,making it have both strong robustness and high accuracy in predicting the missing data of an HiDS matrix.Experimental results on eight HiDS matrices generated by industrial applications verify that the proposed SL-LF model not only is robust to the outlier data but also has significantly higher prediction accuracy than state-of-the-art models when they are used to predict the missing data of HiDS matrices.

A NEW HIGH PERFORMANCE SPARSE STATIC SOLVER IN FINITE ELEMENT ANALYSIS WITH LOOP-UNROLLING

In the previous papers, a high performance sparse static solver with two-level unrolling based on a cell-sparse storage scheme was reported. Although the solver reaches quite a high efficiency for a big percentage of finite element analysis benchmark tests, the MFLOPS （million floating operations per second） of LDL^T factorization of benchmark tests vary on a Dell Pentium IV 850 MHz machine from 100 to 456 depending on the average size of the super-equations, i.e., on the average depth of unrolling. In this paper, a new sparse static solver with two-level unrolling that employs the concept of master-equations and searches for an appropriate depths of unrolling is proposed. The new solver provides higher MFLOPS for LDL^T factorization of benchmark tests, and therefore speeds up the solution process.

Biorthogonal Wavelet Based Algebraic Multigrid Preconditioners for Large Sparse Linear Systems

In this article algebraic multigrid as preconditioners are designed, with biorthogonal wavelets, as intergrid operators for the Krylov subspace iterative methods. Construction of hierarchy of matrices in algebraic multigrid context is based on lowpass filter version of Wavelet Transform. The robustness and efficiency of this new approach is tested by applying it to large sparse, unsymmetric and ill-conditioned matrices from Tim Davis collection of sparse matrices. Proposed preconditioners have potential in reducing cputime, operator complexity and storage space of algebraic multigrid V-cycle and meet the desired accuracy of solution compared with that of orthogonal wavelets.

A Fast LDL-factorization Approach for Large Sparse Positive Definite System and Its Application to One-to-one Marketing Optimization Computation

LDL-factorization is an efficient way of solving Ax = b for a large symmetric positive definite sparse matrix A. This paper presents a new method that further improves the efficiency of LDL-factorization. It is based on the theory of elimination trees for the factorization factor. It breaks the computations involved in LDL-factorization down into two stages： 1） the pattern of nonzero entries of the factor is predicted, and 2） the numerical values of the nonzero entries of the factor are computed. The factor is stored using the form of an elimination tree so as to reduce memory usage and avoid unnecessary numerical operations. The calculation results for some typical numerical examples demonstrate that this method provides a significantly higher calculation efficiency for the one-to-one marketing optimization algorithm.

管道超声相控阵全聚焦成像仿真及算法优化

针对厚壁管道内部缺陷识别困难、可视化差等问题,提出基于超声相控阵理论和全聚焦算法对厚壁管道内部缺陷进行图像重构。并针对全聚焦成像效率低的缺点,采用有限元法对外径为550 mm,壁厚为65 mm的厚壁管道超声相控阵全聚焦成像进行仿真,模拟缺陷检测过程和成像结果,并使用稀疏矩阵对算法进行优化。结果表明:在基本满足成像质量要求的情况下,采用激发中心频率为5 MHz,阵元宽度为0.5 mm,阵元间距为1 mm,阵元数量为32时,稀疏激发矩阵比全矩阵全聚焦成像效率提高了74.81%,有效提高了成像速度,满足全聚焦快速成像的需求。

阵元失效下稀疏阵列的二维DOA估计算法

本文针对二维稀疏阵列在阵元失效条件下,因数据缺失导致虚拟阵列连续性被破坏及自由度下降的问题,提出了一种二维DOA估计算法。首先基于二维差分共阵构建虚拟阵列,然后利用解耦原子范数最小化理论,以矩阵填充的形式恢复协方差矩阵数据,实现对虚拟阵列中丢失虚拟阵元的内插,最后采用SS-MUSIC算法进行多信源的二维DOA估计。所提方法弥补了物理阵元失效所造成的影响,恢复了原始虚拟阵列的完整孔径特性,保持了虚拟阵列的自由度,从而确保了较高精度的二维DOA估计性能。仿真实验结果表明,在相同阵元数量及阵元失效情况下,本文提出的算法相比已有方法能有效地估计更多信源,并在小快拍数和低信噪比条件下表现出更高的稳健性,最大限度地保留并利用了稀疏阵列在二维DOA估计中的自由度优势。

DRM:基于迭代归并策略的GPU并行SpMV存储格式

稀疏矩阵向量乘(SpMV)在线性系统的求解问题中具有重要意义,是科学计算和工程实践中的核心问题之一,其性能高度依赖于稀疏矩阵的非零分布。稀疏对角矩阵是一类特殊的稀疏矩阵,其非零元素按照对角线的形式密集排列。针对稀疏对角矩阵,在GPU平台上提出的多种存储格式虽然使SpMV性能有所提升,但仍存在零填充和负载不平衡的问题。针对上述问题,提出了一种DRM存储格式,利用基于固定阈值的矩阵划分策略和基于迭代归并的矩阵重构策略,实现了少量零填充和块间负载平衡。实验结果表明,在NVIDIA■ Tesla■ V100平台上,相比于DIA、HDC、HDIA和DIA-Adaptive格式,在时间性能方面,该存储格式分别取得了20.76,1.94,1.13和2.26倍加速;在浮点计算性能方面,分别提高了1.54,5.28,1.13和1.94倍。

基于改进型LBP译码的LDPC码稀疏校验矩阵重建

针对LDPC码稀疏校验矩阵重建问题,基于改进型LBP译码的思想提出了一种高误码率下的LDPC码稀疏校验矩阵重建算法。首先,从码字矩阵中随机抽取部分比特构建码字分析矩阵,并对其做高斯消元求对偶空间;其次,通过判定对偶空间向量是否稀疏,提高了后续疑似校验向量判定的效率;最后,在接收码字个数不足时,利用已知校验向量结合改进型LBP译码方法纠正错误码字,加快LDPC码稀疏校验矩阵的重建速度,提高重建性能。仿真结果表明,所提算法在高误码率0.0045的条件下,对于IEEE802.11n协议下的(648,324)LDPC码,相比于现有算法,稀疏校验矩阵重建率提升了52.16%,可达到92.28%。

基于自适应矩阵的核联合稀疏表示高光谱图像分类

针对高光谱图像丰富的空间信息和光谱信息未充分利用的问题,提出了基于自适应矩阵的核联合稀疏表示高光谱图像分类的方法。在特征表示阶段,定义了自适应矩阵特征,通过结合自适应邻域块策略与非线性相关熵度量构成的特征来描述原始光谱像素,充分融合了形状可变的空间信息与非线性光谱信息。在分类阶段,考虑自适应矩阵和高光谱图像非线性,采用对数欧式核函数,构建了核联合稀疏表示模型,以获得重构误差。同时利用字典空间信息构建了矩阵相关性,引入平衡参数实现了稀疏重构误差与矩阵相关性的联合分类。在两个数据集上的实验结果表明,该算法充分利用了高光谱图像的空间信息、光谱信息,能够有效提高分类精度。

TEB:GPU上矩阵分解重构的高效SpMV存储格式

稀疏矩阵向量乘法(SpMV)是科学与工程领域中一个至关重要的计算过程,CSR(compressed sparse row)格式是最常用的稀疏矩阵存储格式之一,在图形处理器(GPU)平台上实现并行SpMV的过程中,其只存储稀疏矩阵的非零元,避免零元素填充所带来的计算冗余,节约存储空间,但存在着负载不均衡的问题,浪费了计算资源。针对上述问题,对近年来效果良好的存储格式进行了研究,提出了一种逐行分解重组存储格式——TEB(threshold-exchangeorder block)格式。该格式采用启发式阈值选择算法确定合适分割阈值,并结合基于重排序的行归并算法,对稀疏矩阵进行重构分解,使得块与块之间非零元个数尽可能得相近,其次结合CUDA(computer unified device architecture)线程技术,提出了基于TEB存储格式的子块间并行SpMV算法,能够合理分配计算资源,解决负载不均衡问题,从而提高SpMV并行计算效率。为了验证TEB存储格式的有效性,在NVIDIA Tesla V100平台上进行实验,结果表明TEB相较于PBC(partition-block-CSR)、AMF-CSR(adaptive multi-row folding of CSR)、CSR-Scalar(compressed sparse row-scalar)和CSR5(compressed sparse row 5)存储格式,在SpMV的时间性能方面平均可提升3.23、5.83、2.33和2.21倍;在浮点计算性能方面,平均可提高3.36、5.95、2.29和2.13倍。

基于L_(2)灵敏度最小化的数字滤波器状态空间实现稀疏化方法

为解决传统数字滤波器在有限精度实现时因有限字长(Finite Word Length,FWL)效应导致滤波器性能下降的问题,提出一种L_(2)灵敏度最小化的数字滤波器状态空间实现稀疏化方法.推导前向差分算子数字滤波器结构传输函数及其等效状态空间实现,根据可控及可观格莱姆矩阵得到基于相似变换矩阵的L_(2)灵敏度表达式,并进行稀疏化校准,将L_(2)灵敏度最小化问题转换为凸函数求最值问题,求导得到L_(2)灵敏度最小化表达式,代回即得前向差分算子数字滤波器的稀疏化状态空间实现.仿真结果表明,所提方法设计的数字滤波器具有更好的抗FWL效应.