超声逆散射图象重建问题中截断奇异值分解正则化方法研究

为解决超声逆散射成像问题中的非线性性,人们需要反复地求解前向散射方程和逆散射方程,以达到对全场和未知函数的精确近似,从而根据这一未知函数的精确近似,较好地重建物体内部的断层图象.前向散射方程是一个适定的方程组,可以采用通常的方法进行求解;而逆散射方程则是一个不适定性的方程组,即使数据中存在一个微小的误差,都可能引起解的较大偏离,因此,对这个不适定方程组的求解问题是整个迭代算法成功的关键.而在不适定性问题的求解过程中,正则化参数的选取又是非常重要的.求解不适定性方程的传统方法是Tikhonov正则化方法,这一方法的实质是在传统最小二乘方法上加上一个小于1的滤波因子,对于超声逆散射成像问题来说,效果并不太好.本文将截断奇异值分解正则化方法应用于逆散射方程的求解问题中,并对正则化参数的选取方法进行修正.数值仿真结果表明,这一方法配合适当的正则化参数选取,可以更好地滤除噪声,提高重建图象的质量与可信度,同时还可以减小迭代过程中的计算量.     

A Simple Regularization of the Polynomial Interpolation for the Resolution of the Runge Phenomenon

A polynomial interpolation based on a uniform grid yields the well-known Runge phenomenon, where maximum error is unbounded for functions with complex roots in the Runge zone. In this paper, we investigate the Runge phenomenon with the finite precision operation. We first show that the maximum error is bounded because of round-off errors inherent to the finite precision operation. Then we propose a simple truncation method based on the truncated singular value decomposition. The method consists of two stages: In the first stage, a new interpolating matrix is constructed using the assumption that the function is analytic. The new interpolating matrix is preconditioned using the statistical filter method. In the second stage, a truncation procedure is applied such that singular values of the new interpolating matrix are truncated if they are equal to or lower than a certain tolerance level. We generalize the method, by analyzing the singular vectors of both the original and new interpolation matrices based on the assumption in the first stage. We show that the structure of the singular vectors makes the first stage essential for an accurate reconstruction of the original function. Numerical examples show that exponential decay of the error can be achieved if an appropriate truncation is chosen.     

An Alternative Algorithm for a Sliding Window ULV Decomposition

The ULV decomposition (ULVD) is an important member of a class of rank-revealing two-sided orthogonal decompositions used to approximate the singular value decomposition (SVD). The ULVD can be modified much faster than the SVD. When modifiying the ULVD, the accurate computation of the subspaces is required in certain time varying applications in signal processing. In this paper, we present an updating algorithm which is suitable for large scaled matrices of low rank and as effective as alternatives. The algorithm runs in O(n²) time.     

Boundary element solution for the Cauchy problem in linear elasticity using singular value decomposition

In this paper the singular value decomposition (SVD), truncated at an optimal number, is analysed for obtaining approximate solutions to ill-conditioned linear algebraic systems of equations which arise from the boundary element method (BEM) discretisation of an ill-posed boundary value problem in linear elasticity. The regularisation parameter, namely the optimal truncation number, is chosen according to the discrepancy principle. The numerical results obtained confirm that the SVD+BEM produces a convergent and stable numerical solution with respect to decreasing the mesh size discretisation and the amount of noise added into the input data.     

自由运行结构动态载荷识别的格林函数法

将Green函数法应用于平动自由结构的载荷识别问题.不计刚-柔耦合效应,建立测点的绝对运动加速度和动态激励的卷积关系,Green核函数由整体刚体运动与弹性振动的脉冲响应迭加而成,采用正则化方法求解反卷积问题.对自由梁和组合薄壁结构给出两个算例,以数值仿真结果叠加20%噪声水平的随机噪声模拟实测响应,结果表明,Green函数法能有效地反演复杂平动自由结构的动载荷,正则化方法求解此类问题的稳健性和耐噪性强.文中得到的Green函数法对复杂自由结构体系的动载荷反演具有应用潜力.     

Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations

The successive projection algorithm (SPA) can quickly solve a nonnegative matrix factorization problem under a separability assumption. Even if noise is added to the problem, SPA is robust as long as the perturbations caused by the noise are small. In particular, robustness against noise should be high when handling the problems arising from real applications. The preconditioner proposed by Gillis and Vavasis (SIAM J Optim 25(1):677–698, 2015) makes it possible to enhance the noise robustness of SPA. Meanwhile, an additional computational cost is required. The construction of the preconditioner contains a step to compute the top-k truncated singular value decomposition of an input matrix. It is known that the decomposition provides the best rank-k approximation to the input matrix; in other words, a matrix with the smallest approximation error among all matrices of rank less than k. This step is an obstacle to an efficient implementation of the preconditioned SPA. To address the cost issue, we propose a modification of the algorithm for constructing the preconditioner. Although the original algorithm uses the best rank-k approximation, instead of it, our modification uses an alternative. Ideally, this alternative should have high approximation accuracy and low computational cost. To ensure this, our modification employs a rank-k approximation produced by an SPA based algorithm. We analyze the accuracy of the approximation and evaluate the computational cost of the algorithm. We then present an empirical study revealing the actual performance of the SPA based rank-k approximation algorithm and the modified preconditioned SPA.     

Accelerating the SVD Block-Jacobi Method

The paper discusses how to improve performance of the one-sided block-Jacobi algorithm for computing the singular value decomposition of rectangular matrices. In particular, it is shown how cosine-sine decomposition of orthogonal matrices can be used to accelerate the slowest part of the algorithm – updating the block-columns.     

State estimation for multi‐channel stochastic singular systems with multiplicative noise

The state estimation problem for multi‐channel singular systems with multiplicative noise is considered based on singular value decomposition. First, two equivalent reduced order subsystems are obtained via the decomposition. Then, in order to solve the estimation problem, the subsystems are rewritten into a new form. It is noted that the measurement noise here becomes colored noise, which contains the dynamic noise, measurement noise, and multiplicative noise of the original system. In this situation, existing filtering methods cannot be directly applied, so a modified filtering method is given. The recursive algorithm for the state estimation is obtained by the filtering method. In addition, the estimation of dynamic noise is derived via the algorithm. A simulation example is given to show the effectiveness of the proposed algorithm. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

基于截断HOSVD的图像压缩算法

本文提出了一种新的图像压缩技术。受高阶奇异值分解(HOSVD)的启发,该技术将每一幅灰度和彩色图像都作为高阶张量,并丢弃奇异子张量相应较小的奇异值来实现图像压缩。在文中还证明了HOSVD是SVD矩阵自然扩伸,并且由于n模式奇异向量相应的较大n模式奇异值在张量分解奇异值耗费更多的资源,我们采用截断HOSVD来实现图像压缩。通过对比实验表明,基于截断HOSVD图像压缩技术比JPEG可以获得更好的性能。     

基于信噪比经验值的奇异值分解滤波门限确定*

针对奇异值分解滤波器（SVDF）现有的奇异值截断准则之不足,提出了一种基于信噪比经验值的SVDF滤波门限确定新方法。推导了门限值与信噪比之间的数学关系。实验结果证实了该滤波消噪算法的有效性和合理性。与现有方法相比,消噪效果得以明显改进;而且原理清晰,实现简单。     

A truncated Levenberg-Marquardt algorithm for the calibration of highly parameterized nonlinear models

We propose a modification to the Levenberg-Marquardt minimization algorithm for a more robust and more efficient calibration of highly parameterized, strongly nonlinear models of multiphase flow through porous media. The new method combines the advantages of truncated singular value decomposition with those of the classical Levenberg-Marquardt algorithm, thus enabling a more robust solution of underdetermined inverse problems with complex relations between the parameters to be estimated and the observable state variables used for calibration. The truncation limit separating the solution space from the calibration null space is re-evaluated during the iterative calibration process. In between these re-evaluations, fewer forward simulations are required, compared to the standard approach, to calculate the approximate sensitivity matrix. Truncated singular values are used to calculate the Levenberg-Marquardt parameter updates, ensuring that safe small steps along the steepest-descent direction are taken for highly correlated parameters of low sensitivity, whereas efficient quasi-Gauss-Newton steps are taken for independent parameters with high impact. The performance of the proposed scheme is demonstrated for a synthetic data set representing infiltration into a partially saturated, heterogeneous soil, where hydrogeological, petrophysical, and geostatistical parameters are estimated based on the joint inversion of hydrological and geophysical data.     

Fast Summation of Radial Functions on the Sphere

Radial functions are a powerful tool in many areas of multi-dimensional approximation, especially when dealing with scattered data. We present a fast approximate algorithm for the evaluation of linear combinations of radial functions on the sphere . The approach is based on a particular rank approximation of the corresponding Gram matrix and fast algorithms for spherical Fourier transforms. The proposed method takes (L) arithmetic operations for L arbitrarily distributed nodes on the sphere. In contrast to other methods, we do not require the nodes to be sorted or pre-processed in any way, thus the pre-computation effort only depends on the particular radial function and the desired accuracy. We establish explicit error bounds for a range of radial functions and provide numerical examples covering approximation quality, speed measurements, and a comparison of our particular matrix approximation with a truncated singular value decomposition.     

Super-resolution imaging based on the BeiDou B3 signal

ABSTRACT

Using global navigation satellites to construct bi-static synthetic aperture radar for imaging has been a major research hotspot in passive radar. However, the low range resolution of Global Navigation Satellite signal (GNSS) limits the quality of actual scene imaging. To increase the range resolution of the imaging, a super-resolution imaging method by mixing the back-projection (BP) algorithm with truncated singular value decomposition (TSVD) is proposed. This paper first introduces the BeiDou Navigation Satellite System (BDS) signal model for ground imaging, carries out the range compression and describes the BP algorithm. Subsequently, the super-resolution method is given and some simulation results are demonstrated. Two field experimental cases, including targets of trees and ferries, are then carried out. The experimental results demonstrate the effectiveness of the proposed method.     

Application of the truncated singular value decomposition method to the obtention of rovibrational population distributions from electronic spectra of diatomic molecules

The truncated singular value decomposition method is applied to obtain the rovibrational population distributions of an electronically excited state of a diatomic molecule from the corresponding emission spectra, when a large number of emitting levels contribute to the spectrum. The molecular spectral intensities are written as the independent term of a set of coupled linear equations where the unknowns are the population distribution of the molecular excited state. Several computer programs have been written in order to perform the following operations: calculation of molecular energy levels, obtention of wavefunctions and transition matrix elements between pair of electronic states, resolution of the system of equations and spectral simulation. A routine based on the truncated singular value decomposition algorithm solves the typically ill conditioned system of coupled linear equations calculating the population distribution. The program incorporates criteria to choose the best set of solutions and performs several tests to check the reliability of the different steps of the calculation. The capability of the algorithm to retrieve the population distribution from spectra obtained under typical experimental conditions, that is spectral intensities affected by noise and overlap of spectral lines, is examined.     

Identification of masses moving on multi-span beams based on a genetic algorithm

This paper describes a theoretical study on the identification of masses moving on a multi-span continuous beam using the acceleration measurements. In the study, the acceleration measurements are simulated from the solution to the forward problem of a continuous beam under moving masses, together with the addition of artificially generated measurement noise. In particular, the forward problem for the simulation is solved using the modified beam vibration functions. A simple dynamic force identification procedure using pseudo-inverse and singular value decomposition is first employed to arrive at rough approximations of the moving masses. A genetic algorithm is then used to find the best estimated values of the moving masses by minimizing the errors between the measured accelerations and the reconstructed accelerations from the moving masses in each generation. Five numerical examples are given to demonstrate the robustness of this method. Various possible sources of error including the effects of measurement noise and surface roughness are also discussed.     

Orthogonal least squares methods and their application to non-linear system identification

Identification algorithms based on the well-known linear least squares methods of gaussian elimination, Cholesky decomposition, classical Gram-Schmidt, modified Gram-Schmidt, Householder transformation, Givens method, and singular value decomposition are reviewed. The classical Gram-Schmidt, modified Gram-Schmidt, and Householder transformation algorithms are then extended to combine structure determination, or which terms to include in the model, and parameter estimation in a very simple and efficient manner for a class of multivariate discrete-time non-linear stochastic systems which are linear in the parameters.     

超声逆散射成像方法研究

在研究奇异值分解、最小二乘法的基础上,采用空间域方法研究超声逆散射成像问题。通过脉冲基和点匹配的方法将泛函方程转换为代数方程,运用迭代算法解决方程的非线性问题。利用Picard准则判断方程的不适定程度,并采用均值处理和截断奇异值分解正则化2种方法对方程进行求解。实验结果证明,该方法可以较好地滤除噪声,提高重建图像的质量和可信度,减少迭代过程中的计算量。     

Improvement in computational efficiency of Euler equations via a modified Sparse Point Representation method

A modified Sparse Point Representation (SPR) method is proposed to enhance the computational efficiency of Euler equations. A SPR dataset adapted to a solution is constructed through interpolating wavelet decomposition and thresholding. The fluxes are evaluated only at the points within a SPR dataset, which reduces the total computing time. In order to improve the overall efficiency and accuracy of the SPR method in a steady-state calculation, the following three techniques are applied: First, the threshold method is modified so as to maintain the spatial accuracy of a conventional solver by switching between a threshold value and the order of magnitude of a spatial truncation error. Second, a stabilization technique is added to improve the compression ratio of the SPR method by keeping numerical errors due to the thresholding from being inserted into the computational domain. Third, if the variations of flow variables in a time integration step are below the order of a threshold value at the points excluded from a SPR dataset, then the tiny variations are restricted by adopting a weighting factor. The modified SPR method was applied to two-dimensional steady Euler equations and it was confirmed that their efficiency and convergence were greatly enhanced without compromising the accuracy of the solution when compared to a conventional solver.