Perturbation Identities for Regularized Tikhonov Inverses and Weighted Pseudoinverses

We consider the perturbation analysis of two important problems for solving ill-conditioned or rank-deficient linear least squares problems. The Tikhonov regularized problem is a linear least squares problem with a regularization term balancing the size of the residual against the size of the weighted solution. The weight matrix can be a non-square matrix (usually with fewer rows than columns). The minimum-norm problem is the minimization of the size of the weighted solutions given by the set of solutions to the, possibly rank-deficient, linear least squares problem.It is well known that the solution of the Tikhonov problem tends to the minimum-norm solution as the regularization parameter of the Tikhonov problem tends to zero. Using this fact and the generalized singular value decomposition enable us to make a perturbation analysis of the minimum-norm problem with perturbation results for the Tikhonov problem. From the analysis we attain perturbation identities for Tikhonov inverses and weighted pseudoinverses.     

Quantum Fourier transform revisited

The fast Fourier transform (FFT) is one of the most successful numerical algorithms of the 20th century and has found numerous applications in many branches of computational science and engineering. The FFT algorithm can be derived from a particular matrix decomposition of the discrete Fourier transform (DFT) matrix. In this paper, we show that the quantum Fourier transform (QFT) can be derived by further decomposing the diagonal factors of the FFT matrix decomposition into products of matrices with Kronecker product structure. We analyze the implication of this Kronecker product structure on the discrete Fourier transform of rank‐1 tensors on a classical computer. We also explain why such a structure can take advantage of an important quantum computer feature that enables the QFT algorithm to attain an exponential speedup on a quantum computer over the FFT algorithm on a classical computer. Further, the connection between the matrix decomposition of the DFT matrix and a quantum circuit is made. We also discuss a natural extension of a radix‐2 QFT decomposition to a radix‐d QFT decomposition. No prior knowledge of quantum computing is required to understand what is presented in this paper. Yet, we believe this paper may help readers to gain some rudimentary understanding of the nature of quantum computing from a matrix computation point of view.     

Analytical and numerical solutions of a one-dimensional fractional-in-space diffusion equation in a composite medium

In this paper a one-dimensional space fractional diffusion equation in a composite medium consisting of two layers in contact is studied both analytically and numerically. Since domain decomposition is the only approach available to solve this problem, we at first investigate analytical and numerical strategies for a composite medium with the same fractal dimension in each layer to ascertain which domain decomposition approach is the most accurate and consistent with a global solution methodology, which is available in this case. We utilise a matrix representation of the fractional-in-space operator to generate a system of linear ODEs with the matrix raised to the same fractional exponent. We show that the global and domain decomposition numerical strategies for this problem produce simulation results that are in good agreement with their analytic counterparts and conclude that the domain decomposition that imposes the Neumann condition at the interface produces the most consistent results. Finally, we carry this finding to study the composite problem with different fractal dimensions, where we again favourably compare analytic and numerical solutions. The resulting method can be naturally extended to space fractional diffusion in a composite medium consisting of more than two layers.     

Creating Advanced Bases For Large Scale Linear Programs Exploiting Embedded Network Structure

In this paper, we investigate how an embedded pure network structure arising in many linear programming (LP) problems can be exploited to create improved sparse simplex solution algorithms. The original coefficient matrix is partitioned into network and non-network parts. For this partitioning, a decomposition technique can be applied. The embedded network flow problem can be solved to optimality using a fast network flow algorithm. We investigate two alternative decompositions namely, Lagrangean and Benders. In the Lagrangean approach, the optimal solution of a network flow problem and in Benders the combined solution of the master and the subproblem are used to compute good (near optimal and near feasible) solutions for a given LP problem. In both cases, we terminate the decomposition algorithms after a preset number of passes and active variables identified by this procedure are then used to create an advanced basis for the original LP problem. We present comparisons with unit basis and a well established crash procedure. We find that the computational results of applying these techniques to a selection of Netlib models are promising enough to encourage further research in this area.     

Mixed-integer programming techniques for decomposing IMRT fluence maps using rectangular apertures

We consider a matrix decomposition problem arising in Intensity Modulated Radiation Therapy (IMRT). The problem input is a matrix of intensity values that are to be delivered to a patient via IMRT from some given angle, under the condition that the IMRT device can only deliver radiation in rectangular shapes. This paper studies the problem of minimizing the number of rectangles (and their associated intensities) necessary to decompose such a matrix. We propose an integer programming-based methodology for providing lower and upper bounds on the optimal solution, and demonstrate the efficacy of our approach on clinical data.     

Elementary landscape decomposition of the 0-1 unconstrained quadratic optimization

Landscapes’ theory provides a formal framework in which combinatorial optimization problems can be theoretically characterized as a sum of an especial kind of landscape called elementary landscape. The elementary landscape decomposition of a combinatorial optimization problem is a useful tool for understanding the problem. Such decomposition provides an additional knowledge on the problem that can be exploited to explain the behavior of some existing algorithms when they are applied to the problem or to create new search methods for the problem. In this paper we analyze the 0-1 Unconstrained Quadratic Optimization from the point of view of landscapes’ theory. We prove that the problem can be written as the sum of two elementary components and we give the exact expressions for these components. We use the landscape decomposition to compute autocorrelation measures of the problem, and show some practical applications of the decomposition.     

On the stability of the incomplete Cholesky decomposition for a singular perturbed problem,where the coefficient matrix is not an M-matrix

The incomplete Cholesky decomposition is known as an excellent smoother in a multigrid iteration and as a preconditioner for the conjugate gradient method. However, the existence of the decomposition is only ensured if the system matrix is an M-matrix. It is well-known that finite element methods usually do not lead to M-matrices. In contrast to this restricting fact, numerical experiments show that, even in cases where the system matrix is not an M-matrix the behaviour of the incomplete Cholesky decomposition apparently does not depend on the structure of the grid. In this paper the behaviour of the method is investigated theoretically for a model problem, where the M-matrix condition is violated systematically by a suitable perturbation. It is shown that in this example the stability of the incomplete Cholesky decomposition is independent of the perturbation and that the analysis of the smoothing property can be carried through. This can be considered as a generalization of the results for the so called square-grid triangulation, as has been established by Wittum in [12] and [11].     

The rank of the covariance matrix of an evanescent field

Evanescent random fields arise as a component of the 2D Wold decomposition of homogeneous random fields. Besides their theoretical importance, evanescent random fields have a number of practical applications, such as in modeling the observed signal in the space-time adaptive processing (STAP) of airborne radar data. In this paper we derive an expression for the rank of the low-rank covariance matrix of a finite dimension sample from an evanescent random field. It is shown that the rank of this covariance matrix is completely determined by the evanescent field spectral support parameters, alone. Thus, the problem of estimating the rank lends itself to a solution that avoids the need to estimate the rank from the sample covariance matrix. We show that this result can be immediately applied to considerably simplify the estimation of the rank of the interference covariance matrix in the STAP problem.     

Half Dirichlet problem for matrix functions on the unit ball in Hermitian Clifford analysis

The simultaneous null solutions of the two complex Hermitian Dirac operators are focused on in Hermitian Clifford analysis, where the Hermitian Cauchy integral was constructed and will play an important role in the framework of circulant (2×2) matrix functions. Under this setting we will present the half Dirichlet problem for circulant (2×2) matrix functions on the unit ball of even dimensional Euclidean space. We will give the unique solution to it merely by using the Hermitian Cauchy transformation, get the solution to the Dirichlet problem on the unit ball for circulant (2×2) matrix functions and the solution to the classical Dirichlet problem as the special case, derive a decomposition of the Poisson kernel for matrix Laplace operator, and further obtain the decomposition theorems of solution space to the Dirichlet problem for circulant (2×2) matrix functions.     

Modified ILU as a smoother

Summary. We study a variant of ILU, viz. with , as a smoother in multi-grid methods. The -decomposition is characterized by the fact that the rest matrix is not zero on the diagonal but instead of that satisfies . The use of as a smoother is recommended because of the observed robustness when it is applied to singular perturbation problems. However, until now, a proof of robustness has only been given for one model anisotropic equation by Wittum. In this paper, we show that the -decomposition of an M-matrix exists and yields a regular splitting. For symmetric M-matrices and symmetric decomposition ``patterns' we prove that the eigenvalues of the -smoother are in \footnote{After this paper was submitted, the author learned of a report of Notay (\cite{239.5}) where related results are discussed}, whereas the rest matrix is at most a modest factor larger than the rest matrix of the unmodified ILU-decomposition. With these properties, robustness can now be shown when the rest matrix of the unmodified decomposition is ``small enough'. Our results generalize Wittum's results for the model problem. Received August 16, 1992 / Revised version received September 7, 1993     

Matrix computations for information retrieval and major and outlier cluster detection

In this paper we introduce COV, a novel information retrieval (IR) algorithm for massive databases based on vector space modeling and spectral analysis of the covariance matrix, for the document vectors, to reduce the scale of the problem. Since the dimension of the covariance matrix depends on the attribute space and is independent of the number of documents, COV can be applied to databases that are too massive for methods based on the singular value decomposition of the document-attribute matrix, such as latent semantic indexing (LSI). In addition to improved scalability, theoretical considerations indicate that results from our algorithm tend to be more accurate than those from LSI, particularly in detecting subtle differences in document vectors. We demonstrate the power and accuracy of COV through an important topic in data mining, known as outlier cluster detection. We propose two new algorithms for detecting major and outlier clusters in databases—the first is based on LSI, and the second on COV. Our implementation studies indicate that our cluster detection algorithms outperform the basic LSI and COV algorithm in detecting outlier clusters.     

The Haar Wavelet Analysis of Matrices and Its Applications

It is well known that Fourier analysis or wavelet analysis is a very powerful and useful tool for a function since they convert time-domain problems into frequency-domain problems. Are there similar tools for a matrix? By pairing a matrix to a piecewise function,a Haar-like wavelet is used to set up a similar tool for matrix analyzing, resulting in new methods for matrix approximation and orthogonal decomposition. By using our method, one can approximate a matrix by matrices with different orders. Our method also results in a new matrix orthogonal decomposition, reproducing Haar transformation for matrices with orders of powers of two. The computational complexity of the new orthogonal decomposition is linear. That is, for an m × n matrix, the computational complexity is O(mn). In addition,when the method is applied to k-means clustering, one can obtain that k-means clustering can be equivalently converted to the problem of finding a best approximation solution of a function. In fact, the results in this paper could be applied to any matrix related problems.In addition, one can also employ other wavelet transformations and Fourier transformation to obtain similar results.     

Lagrangean decomposition: A model yielding stronger lagrangean bounds

Given a mixed-integer programming problem with two matrix constraints, it is possible to define a Lagrangean relaxation such that the relaxed problem decomposes additively into two subproblems, each having one of the two matrices of the original problem as its constraints. There is one Lagrangean multiplier per variable. We prove that the optimal value of this new Lagrangean dual dominates the optimal value of the Lagrangean dual obtained by relaxing one set of constraints and give a necessary condition for a strict improvement. We show on an example that the resulting bound improvement can be substantial. We show on a complex practical problem how Lagrangean decomposition may help uncover hidden special structures and thus yield better solution methodology. Research supported by the National Science Foundation under grant ECS-8508142.     

矩阵在等价分解下的Penrose型广义逆的通式(英文)

设A∈Rrm×n,本文讨论了矩阵A在等价分解下的13类Moore-Penrose型广义逆的通式.由于等价分解是矩阵论及其应用中的一种重要的分解,并且本文所给出的通式只需通过矩阵的初等变换和乘法运算就能得到,故这些通式在相关的理论研究和实际应用中是有一定价值的.     

Decomposed enumeration of extreme points in the linear programming problem

In this paper we consider the problem of enumeration of extreme points in the linear programming problem when the matrix is of block-angular type. It is shown how decomposition methods can be used. Finally application of decomposed enumeration to the problem of computing equilibrium prices in a capital market network is given as an example.     

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.     

Converging upon basic feasible solutions through Dantzig–Wolfe decomposition

We derive an important property for solving large-scale integer programs by examining the master problem in Dantzig–Wolfe decomposition. In particular, we prove that if a linear program can be divided into subproblems with affinely independent corner points, then there is a direct mapping between basic feasible solutions in the master and original problems. This has implications for integer programs where the feasible region has integer corner points, ensuring that integer solutions to the original problem will be found even through the decomposition approach. An application to air traffic flow scheduling, which motivated this result, is highlighted.     

The calculation of the distance to a nearby defective matrix

The distance of a matrix to a nearby defective matrix is an important classical problem in numerical linear algebra, as it determines how sensitive or ill‐conditioned an eigenvalue decomposition of a matrix is. The concept has been discussed throughout the history of numerical linear algebra, and the problem of computing the nearest defective matrix first appeared in Wilkinsons famous book on the algebraic eigenvalue problem. In this paper, a new fast algorithm for the computation of the distance of a matrix to a nearby defective matrix is presented. The problem is formulated following Alam and Bora introduced in (2005) and reduces to finding when a parameter‐dependent matrix is singular subject to a constraint. The solution is achieved by an extension of the implicit determinant method introduced by Spence and Poulton in (2005). Numerical results for several examples illustrate the performance of the algorithm. Copyright © 2013 John Wiley & Sons, Ltd.     

矩阵不等式约束下矩阵方程AX=B的双对称解

本文讨论矩阵不等式CXD≥E 约束下矩阵方程AX=B的双对称解,即给定矩阵A,B,C,D和 E, 求双对称矩阵X, 使得AX=B 和 CXD≥E, 其中CXD≥E表示矩阵CXD-E非负.本文将问题转化为矩阵不等式最小非负偏差问题,利用极分解理论给出了求其解的迭代方法,并结合相关矩阵理论说明算法的收敛性.最后给出数值算例验证算法的有效性.     

Analysis of sensitivity of reciprocal matrices

We develop a method based on the Hadamard Product of matrices to analyze the sensitivity of reciprocal matrices. We show that this type of matrices can be decomposed into the Hadamard Product of a consistent matrix and an inconsistent matrix. The consistent matrix has the same principal eigenvector as the original matrix, and the inconsistent matrix has the same principal eigenvalue as the original one. We use this decomposition in the analysis of sensitivity to compute the principle eigenvector of a perturbed reciprocal matrix.