Low-Rank Positive Approximants of Symmetric Matrices

Given a symmetric matrix X, we consider the problem of finding a low-rank positive approximant of X. That is, a symmetric positive semidefinite matrix, S, whose rank is smaller than a given positive integer, , which is nearest to X in a certain matrix norm. The problem is first solved with regard to four common norms: The Frobenius norm, the Schatten p-norm, the trace norm, and the spectral norm. Then the solution is extended to any unitarily invariant matrix norm. The proof is based on a subtle combination of Ky Fan dominance theorem, a modified pinching principle, and Mirsky minimum-norm theorem.

基于低秩逼近代理模型的N-1安全约束经济调度快速计算方法

随着新能源并网比例不断提高,为保障电力系统可靠运行,安全约束经济调度(SCED)需要考虑海量的N-1安全约束,对模型求解造成极大的计算负担.N-1安全约束中只有少量约束在计算过程中起作用,剔除大量冗余约束有助于提高SCED模型的求解效率.提出基于低秩逼近(LRA)代理模型的SCED模型快速计算方法,首先构建考虑风力发电、光伏的SCED模型,并根据SCED模型的历史运行信息建立LRA代理模型;其次基于LRA代理模型的估计结果辨识关键约束和构建积极约束集,并提出基于LRA的SCED模型迭代求解流程;最后在IEEE 39节点系统下进行算例仿真.仿真结果表明,LRA代理模型与SCED模型的求解结果误差小于10%,约束辨识准确率高,所提求解流程的平均迭代求解时间降低了50%以上,显著提高了SCED模型的求解效率.

海洋条件下非能动系统高效全局敏感性分析方法研究

非能动系统运行过程中包含大量的不确定性参数,一般通过最佳估算加不确定性分析对其可靠性进行评估,评估过程中一个重要的步骤是参数的敏感性分析,用来识别系统关键参数以降低模型复杂性。传统的全局敏感性分析因其高昂的计算成本难以被应用于复杂的核动力系统中,为提高其分析效率,本研究提出采用低秩近似(Low-Rank Approximations,LRA)方法改进基于蒙特卡罗的Sobol方法,并利用多个基准题验证所提方法的有效性。最后用此方法对某一体化压水堆的非能动余热排出系统进行敏感性分析。结果表明:本文所提方法仅需200次模拟计算,耗时约55 min就能准确识别系统关键参数,且与Sobol方法运行1.0×10^(5)次模拟计算,耗时约19 d所得到的敏感性排序结果一致。因此,本研究建立的高效全局敏感性分析方法可为非能动系统的可靠性分析和设计优化等过程提供有效指导。

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.

Generalized Nonconvex Low-Rank Algorithm for Magnetic Resonance Imaging (MRI) Reconstruction

In recent years,utilizing the low-rank prior information to construct a signal from a small amount of measures has attracted much attention.In this paper,a generalized nonconvex low-rank(GNLR) algorithm for magnetic resonance imaging(MRI)reconstruction is proposed,which reconstructs the image from highly under-sampled k-space data.In the algorithm,the nonconvex surrogate function replacing the conventional nuclear norm is utilized to enhance the low-rank property inherent in the reconstructed image.An alternative direction multiplier method(ADMM) is applied to solving the resulting non-convex model.Extensive experimental results have demonstrated that the proposed method can consistently recover MRIs efficiently,and outperforms the current state-of-the-art approaches in terms of higher peak signal-to-noise ratio(PSNR) and lower high-frequency error norm(HFEN) values.

Robust least squares projection twin SVM and its sparse solution

Least squares projection twin support vector machine(LSPTSVM)has faster computing speed than classical least squares support vector machine(LSSVM).However,LSPTSVM is sensitive to outliers and its solution lacks sparsity.Therefore,it is difficult for LSPTSVM to process large-scale datasets with outliers.In this paper,we propose a robust LSPTSVM model(called R-LSPTSVM)by applying truncated least squares loss function.The robustness of R-LSPTSVM is proved from a weighted perspective.Furthermore,we obtain the sparse solution of R-LSPTSVM by using the pivoting Cholesky factorization method in primal space.Finally,the sparse R-LSPTSVM algorithm(SR-LSPTSVM)is proposed.Experimental results show that SR-LSPTSVM is insensitive to outliers and can deal with large-scale datasets fastly.

Low-rank spectral estimation algorithm of learning Markov model

This paper proposes a low-rank spectral estimation algorithm of learning Markov model.First,an approximate projection algorithm for the rank-constrained frequency matrix set is proposed,and thereafter its local Lipschitzian error bound established.Then,we propose a low-rank spectral estimation algorithm for estimating the state transition frequency matrix and the probability matrix of Markov model by applying the approximate projection algorithm to correct the maximum likelihood estimation of the frequency matrix,and prove that there is only a multiplying constant difference in estimation errors between the low-rank spectral estimation and the maximum likelihood estimation under appropriate conditions.Finally,numerical comparisons with the prevailing maximum likelihood estimation,spectral estimation,and rank-constrained maxi-mum likelihood estimation show that the low-rank spectral estimation algorithm is effective.

一种改进的基于低秩逼近的空时自适应处理算法

针对非均匀杂波情况下的空时自适应处理的小样本问题,该文提出一种基于权矩阵低秩逼近的空时自适应处理方法。与传统的低秩逼近算法不同,利用空时导向矢量特殊的克罗累计性,该文重新构造新的权矩阵,使得该权矩阵的行数与列数尽可能地相近或相同,以减少算法所需的样本个数和计算量。采用低秩逼近方法对新构造的权矩阵进行表示,则原二次优化问题转化为求解一个双二次代价函数问题。实验表明,改进的空时权矩阵低秩逼近方法能有效地提高空时自适应处理的收敛速度和降低算法复杂度。

面向元动作的机械传动系统可靠性分配方法

针对机械传动系统可靠性分配中存在的不确定性问题,提出了一种对不确定性进行量化的机械传动系统可靠性分配方法。利用“功能运动动作”的分解方法提取了传动系统中可靠性分配的最小粒度(即元动作);根据元动作的可靠性数学模型,提出了一种基于低阶逼近的Sobol'法的传动系统灵敏度计算方法,量化了传动系统中各个元动作的可靠性灵敏度,并甄别出影响传动系统可靠性的关键元动作;建立了元动作与系统整机可靠性的映射关系,并对映射结果进行了求解。应用结果表明,该方法具有较高的计算精度,为机械传动系统的可靠性分配提供了指导。

Linear low-rank approximation and nonlinear dimensionality reduction

We present our recent work on both linear and nonlinear data reduction methods and algorithms: for the linear case we discuss results on structure analysis of SVD of columnpartitioned matrices and sparse low-rank approximation; for the nonlinear case we investigate methods for nonlinear dimensionality reduction and manifold learning. The problems we address have attracted great deal of interest in data mining and machine learning.

Seismic data reconstruction based on low dimensional manifold model

Seismic data reconstruction is an essential and yet fundamental step in seismic data processing workflow,which is of profound significance to improve migration imaging quality,multiple suppression effect,and seismic inversion accuracy.Regularization methods play a central role in solving the underdetermined inverse problem of seismic data reconstruction.In this paper,a novel regularization approach is proposed,the low dimensional manifold model(LDMM),for reconstructing the missing seismic data.Our work relies on the fact that seismic patches always occupy a low dimensional manifold.Specifically,we exploit the dimension of the seismic patches manifold as a regularization term in the reconstruction problem,and reconstruct the missing seismic data by enforcing low dimensionality on this manifold.The crucial procedure of the proposed method is to solve the dimension of the patches manifold.Toward this,we adopt an efficient dimensionality calculation method based on low-rank approximation,which provides a reliable safeguard to enforce the constraints in the reconstruction process.Numerical experiments performed on synthetic and field seismic data demonstrate that,compared with the curvelet-based sparsity-promoting L1-norm minimization method and the multichannel singular spectrum analysis method,the proposed method obtains state-of-the-art reconstruction results.

Randomized Generalized Singular Value Decomposition

The generalized singular value decomposition(GSVD)of two matrices with the same number of columns is a very useful tool in many practical applications.However,the GSVD may suffer from heavy computational time and memory requirement when the scale of the matrices is quite large.In this paper,we use random projections to capture the most of the action of the matrices and propose randomized algorithms for computing a low-rank approximation of the GSVD.Serval error bounds of the approximation are also presented for the proposed randomized algorithms.Finally,some experimental results show that the proposed randomized algorithms can achieve a good accuracy with less computational cost and storage requirement.

The Equivalence between Orthogonal Iterations and Alternating Least Squares

This note explores the relations between two different methods. The first one is the Alternating Least Squares (ALS) method for calculating a rank-k approximation of a real m×n matrix, A. This method has important applications in nonnegative matrix factorizations, in matrix completion problems, and in tensor approximations. The second method is called Orthogonal Iterations. Other names of this method are Subspace Iterations, Simultaneous Iterations, and block-Power method. Given a real symmetric matrix, G, this method computes k dominant eigenvectors of G. To see the relation between these methods we assume that G = AT A. It is shown that in this case the two methods generate the same sequence of subspaces, and the same sequence of low-rank approximations. This equivalence provides new insight into the convergence properties of both methods.

Nonlocally Centralized Simultaneous Sparse Coding

The concept of structured sparse coding noise is introduced to exploit the spatial correlations and nonlocal constraint of the local structure. Then the model of nonlocally centralized simultaneous sparse coding(NCSSC)is proposed for reconstructing the original image, and an algorithm is proposed to transform the simultaneous sparse coding into reweighted low-rank approximation. Experimental results on image denoisng, deblurring and super-resolution demonstrate the advantage of the proposed NC-SSC method over the state-of-the-art image restoration methods.

Fast nonnegative tensor ring decomposition based on the modulus method and low-rank approximation

Nonnegative tensor ring(NTR) decomposition is a powerful tool for capturing the significant features of tensor objects while preserving the multi-linear structure of tensor data. The existing algorithms rely on frequent reshaping and permutation operations in the optimization process and use a shrinking step size or projection techniques to ensure core tensor nonnegativity, which leads to a slow convergence rate, especially for large-scale problems. In this paper, we first propose an NTR algorithm based on the modulus method(NTR-MM), which constrains core tensor nonnegativity by modulus transformation. Second, a low-rank approximation(LRA) is introduced to NTR-MM(named LRA-NTR-MM), which not only reduces the computational complexity of NTR-MM significantly but also suppresses the noise. The simulation results demonstrate that the proposed LRA-NTR-MM algorithm achieves higher computational efficiency than the state-of-the-art algorithms while preserving the effectiveness of feature extraction.

Numerical Computation of Structured Singular Values for Companion Matrices

In this article, the computation of μ-values known as Structured Singular Values SSV for the companion matrices is presented. The comparison of lower bounds with the well-known MATLAB routine mussv is investigated. The Structured Singular Values provides important tools to analyze the stability and instability analysis of closed loop time invariant systems in the linear control theory as well as in structured eigenvalue perturbation theory.

Computing Structured Singular Values for Delay and Polynomial Eigenvalue Problems

In this article the computation of the Structured Singular Values (SSV) for the delay eigenvalue problems and polynomial eigenvalue problems is presented and investigated. The comparison of bounds of SSV with the well-known MATLAB routine mussv is investigated.

Doubling Phase Shifters for Efficient Hybrid Precoder Design in Millimeter-Wave Communication Systems

Hybrid precoding is a cost-effective approach to support directional transmissions for millimeter-wave(mmWave)communications,but its precoder design is highly complicated.In this paper,we propose a new hybrid precoder implementation,namely the double phase shifter(DPS)implementation,which enables highly tractable hybrid precoder design.Efficient algorithms are then developed for two popular hybrid precoder structures,i.e.,the fully-and partially-connected structures.For the fully-connected one,the RF-only precoding and hybrid precoding problems are formulated as a least absolute shrinkage and selection operator problem and a low-rank matrix approximation problem,respectively.In this way,computationally efficient algorithms are provided to approach the performance of the fully digital one with a small number of radio frequency(RF)chains.On the other hand,the hybrid precoder design in the partially-connected structure is identified as an eigenvalue problem.To enhance the performance of this cost-effective structure,dynamic mapping from RF chains to antennas is further proposed,for which a greedy algorithm and a modified K-means algorithm are developed.Simulation results demonstrate the performance gains of the proposed hybrid precoding algorithms over existing ones.It shows that,with the proposed DPS implementation,the fully-connected structure enjoys both satisfactory performance and low design complexity while the partially-connected one serves as an economic solution with low hardware complexity.

Latent spatio-temporal activity structures: a new approach to inferring intra-urban functional regions via social media check-in data

This article introduces a novel low rank approximation (LRA)-based model to detect the functional regions with the data from about 15 million social media check-in records during a year-long period in Shanghai, China. We identified a series of latent structures, named latent spatio-temporal activity structures. While interpreting these structures, we can obtain a series of underlying associations between the spatial and temporal activity patterns. Moreover, we can not only reproduce the observed data with a lower dimensional representative, but also project spatio-temporal activity patterns in the same coordinate system. With the K-means clustering algorithm, five significant types of clusters that are directly annotated with a combination of temporal activities can be obtained, providing a clear picture of the correlation between the groups of regions and different activities at different times during a day. Besides the commercial and transportation dominant areas, we also detected two kinds of residential areas, the developed residential areas and the developing residential areas.We further interpret the spatial distribution of these clusters using urban form analytics. The results are highly consistent with the government planning in the same periods, indicating that our model is applicable to infer the functional regions from social media check-in data and can benefit a wide range of fields, such as urban planning, public services, and location-based recommender systems.

Directional H^(2) Compression Algorithm: Optimisations and Application to a Discontinuous Galerkin BEM for the Helmholtz Equation

This study aimed to specialise a directional H^(2)(DH^(2))compression to matrices arising from the discontinuous Galerkin(DG)discretisation of the hypersingular equation in acoustics.The significantfinding is an algorithm that takes a DG stiffness matrix andfinds a near-optimal DH^(2) approximation for low and high-frequency problems.We introduced the necessary special optimisations to make this algorithm more efficient in the case of a DG stiffness matrix.Moreover,an automatic parameter tuning strategy makes it easy to use and versatile.Numerical comparisons with a classical Boundary Element Method(BEM)show that a DG scheme combined with a DH^(2) gives better computational efficiency than a classical BEM in the case of high-order finite elements and hp heterogeneous meshes.The results indicate that DG is suitable for an auto-adaptive context in integral equations.