A randomized tensor singular value decomposition based on the t‐product

The tensor SVD (t‐SVD) for third‐order tensors, previously proposed in the literature, has been applied successfully in many fields, such as computed tomography, facial recognition, and video completion. In this paper, we propose a method that extends a well‐known randomized matrix method to the t‐SVD. This method can produce a factorization with similar properties to the t‐SVD, but it is more computationally efficient on very large data sets. We present details of the algorithms and theoretical results and provide numerical results that show the promise of our approach for compressing and analyzing image‐based data sets. We also present an improved analysis of the randomized and simultaneous iteration for matrices, which may be of independent interest to the scientific community. We also use these new results to address the convergence properties of the new and randomized tensor method as well.     

A singular value decomposition for the Shack-Hartmann based wavefront reconstruction

We study the problem of reconstructing a wavefront from measurements of Shack-Hartmann-type sensors. Mathematically, this leads to the problem of reconstructing a function from a discrete set of averages of the gradient.After choosing appropriate function spaces this is an underdetermined problem for which least squares solutions and generalized inverses can be used. We explore this problem in more detail for the case of periodic functions on a quadratic aperture, where we calculate the singular value decomposition of the associated forward operator. The nonzero singular values can be estimated which shows that asymptotically, with increasing number of measurements, the reconstruction problem becomes an ill-posed problem.     

Sensitivity analysis for the generalized singular value decomposition

In this paper, we discuss the sensitivity of multiple nonzero finite generalized singular values and the corresponding generalized singular matrix set of a real matrix pair analytically dependent on several parameters. From our results, the partial derivatives of multiple nonzero singular values and their left and right singular vector matrices are obtained.Copyright © 2012 John Wiley & Sons, Ltd.     

A singular value decomposition algorithm based on solving hyperplane constrained nonlinear systems

A new algorithm for singular value decomposition (SVD) is presented through relating SVD problem to nonlinear systems whose solutions are constrained on hyperplanes. The hyperplane constrained nonlinear systems are solved with the help of Newton’s iterative method. It is proved that our SVD algorithm has the quadratic convergence substantially and all singular pairs are computable. These facts are also confirmed by some numerical examples.     

A weighted singular value decomposition for the discrete inverse problems

In this paper, we introduce and analyze a new singular value decomposition (SVD) called weighted SVD (WSVD) using a new inner product instead of the Euclidean one. We use the WSVD to approximate the singular values and the singular functions of the Fredholm integral operators. In this case, the new inner product arises from the numerical integration used to discretize the operator. Then, the truncated WSVD (TWSVD) is used to regularize the Nyström discretization of the first‐kind Fredholm integral equations. Also, we consider the weighted LSQR (WLSQR) to approximate the solution obtained by the TWSVD method for large problems. Numerical experiments on a few problems are used to illustrate that the TWSVD can perform better than the TSVD.     

The QRPS algorithm: A generalization of the QR algorithm for the singular values decomposition of rectangular matrices

A generalization of the QR algorithm proposed by Francis [2] for square matrices is introduced for the singular values decomposition of arbitrary rectangular matrices. Geometrically the algorithm means the subsequent orthogonalization of the image of orthonormal bases produced in the course of the iteration. Our purpose is to show how to get a series of lower triangular matrices by alternate orthogonal-upper triangular decompositions in different dimensions and to prove the convergence of this series.     

Randomized LU decomposition

Randomized algorithms play a central role in low rank approximations of large matrices. In this paper, the scheme of the randomized SVD is extended to a randomized LU algorithm. Several error bounds are introduced, that are based on recent results from random matrix theory related to subgaussian matrices. The bounds also improve the existing bounds of already known randomized SVD algorithm. The algorithm is fully parallelized and thus can utilize efficiently GPUs without any CPU–GPU data transfer. Numerical examples, which illustrate the performance of the algorithm and compare it to other decomposition methods, are presented.     

A modification of the Adomian decomposition method for a class of nonlinear singular boundary value problems

In this paper, the Adomian decomposition method is modified to solve a class of nonlinear singular boundary value problems which arise as nonlinear normal modal equations in nonlinear conservative vibratory systems. The effectiveness of the modified method is verified by three examples.     

A new approximation algorithm for the multilevel facility location problem

In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems.     

On randomized algorithms for the majority problem

In the majority problem, we are given n balls coloured black or white and we are allowed to query whether two balls have the same colour or not. The goal is to find a ball of majority colour in the minimum number of queries. The answer is known to be n−B(n) where B(n) is the number of 1’s in the binary representation of n. In this paper we study randomized algorithms for determining majority, which are allowed to err with probability at most ε. We show that any such algorithm must have expected running time at least . Moreover, we provide a randomized algorithm which shows that this result is best possible. These extend a result of De Marco and Pelc [G. De Marco, A. Pelc, Randomized algorithms for determining the majority on graphs, Combin. Probab. Comput. 15 (2006) 823-834].     

A modified truncated singular value decomposition method for discrete ill‐posed problems

Truncated singular value decomposition is a popular method for solving linear discrete ill‐posed problems with a small to moderately sized matrix A. Regularization is achieved by replacing the matrix A by its best rank‐k approximant, which we denote by A_k. The rank may be determined in a variety of ways, for example, by the discrepancy principle or the L‐curve criterion. This paper describes a novel regularization approach, in which A is replaced by the closest matrix in a unitarily invariant matrix norm with the same spectral condition number as A_k. Computed examples illustrate that this regularization approach often yields approximate solutions of higher quality than the replacement of A by A_k.Copyright © 2014 John Wiley & Sons, Ltd.     

On efficient implementations of Kogbetliantz's algorithm for computing the singular value decomposition

Summary In this paper we compare several implementations of Kogbetliantz's algorithm for computing the SVD on sequential as well as on parallel machines. Comparisons are based on timings and on operation counts. The numerical accuracy of the different methods is also analyzed.     

A survey of randomized algorithms for control synthesis and performance verification

In this paper, we present an overview of probabilistic techniques based on randomized algorithms for solving “hard’’ problems arising in performance verification and control of complex systems. This area is fairly recent, even though its roots lie in the robustness techniques for handling uncertain control systems developed in the 1980s. In contrast to these deterministic techniques, the main ingredient of the methods discussed in this survey is the use of probabilistic concepts. The introduction of probability and random sampling permits overcoming the fundamental tradeoff between numerical complexity and conservatism that lie at the roots of the worst-case deterministic methodology. The simplicity of implementation of randomized techniques may also help bridging the gap between theory and practical applications.     

On the quadratic convergence of Kogbetliantz's algorithm for computing the singular value decomposition

It is shown that the cyclic Kogbetliantz algorithm ultimately converges quadratically when no pathologically close singular values are present.     

Simultaneous singular value decomposition

We consider the following problem: Given a set of m×n real (or complex) matrices A₁,…,A_N, find an m×m orthogonal (or unitary) matrix P and an n×n orthogonal (or unitary) matrix Q such that P^*A₁Q,…,P^*A_NQ are in a common block-diagonal form with possibly rectangular diagonal blocks. We call this the simultaneous singular value decomposition (simultaneous SVD). The name is motivated by the fact that the special case with N=1, where a single matrix is given, reduces to the ordinary SVD. With the aid of the theory of *-algebra and bimodule it is shown that a finest simultaneous SVD is uniquely determined. An algorithm is proposed for finding the finest simultaneous SVD on the basis of recent algorithms of Murota-Kanno-Kojima-Kojima and Maehara-Murota for simultaneous block-diagonalization of square matrices under orthogonal (or unitary) similarity.     

A new analytical and numerical treatment for singular two-point boundary value problems via the Adomian decomposition method

Based on the Adomian decomposition method, a new analytical and numerical treatment is introduced in this research to investigate linear and non-linear singular two-point BVPs. The effectiveness of the proposed approach is verified by several linear and non-linear examples.     

A randomized algorithm for the decomposition of matrices

Given an $m\times n$ matrix A and a positive integer k, we describe a randomized procedure for the approximation of A with a matrix Z of rank k. The procedure relies on applying $A^{\mathrm{T}}$ to a collection of l random vectors, where l is an integer equal to or slightly greater than k; the scheme is efficient whenever A and $A^{\mathrm{T}}$ can be applied rapidly to arbitrary vectors. The discrepancy between A and Z is of the same order as $\sqrt{lm}$ times the $(k+1)$st greatest singular value ${\sigma }_{k+1}$ of A, with negligible probability of even moderately large deviations. The actual estimates derived in the paper are fairly complicated, but are simpler when $l?k$ is a fixed small nonnegative integer. For example, according to one of our estimates for $l?k=20$, the probability that the spectral norm $6A?Z6$ is greater than $10\sqrt{(k+20)m}{\sigma }_{k+1}$ is less than ${10}^{?17}$. The paper contains a number of estimates for $6A?Z6$, including several that are stronger (but more detailed) than the preceding example; some of the estimates are effectively independent of m. Thus, given a matrix A of limited numerical rank, such that both A and $A^{\mathrm{T}}$ can be applied rapidly to arbitrary vectors, the scheme provides a simple, efficient means for constructing an accurate approximation to a singular value decomposition of A. Furthermore, the algorithm presented here operates reliably independently of the structure of the matrix A. The results are illustrated via several numerical examples.     

Updating the singular value decomposition

Summary LetA be anm×n matrix with known singular value decomposition. The computation of the singular value decomposition of a matrixà is considered, whereà is obtained by appending a row or a column toA whenmn or by deleting a row or a column fromA whenm>n. An algorithm is also presented for solving the updated least squares problemà y–b, obtained from the least squares problemAx–b by appending an equation, deleting an equation, appending an unknown, or deleting an unknown.This research was supported by NSF grants MCS 75-06510 and MCS 76-03139     

Inverse estimation of indoor airflow patterns using singular value decomposition

The fast pace in the development of indoor sensors and communication technologies is allowing a great amount of sensor data to be utilized in various areas of indoor air applications, such as estimating indoor airflow patterns. The development of such an inverse model and the design of a sensor system to collect appropriate data are discussed in this study. Algebraic approaches, including singular value decomposition (SVD), are evaluated as methods to inversely estimate airflow patterns given limited sensor measurements. In lieu of actual sensor data, computational fluid dynamics data are used to evaluate the accuracy of the airflow patterns estimated by the inverse models developed in this study. It was found that the airflow patterns estimated by the linear inverse SVD model were as accurate as those estimated by the nonlinear inverse-multizone model. For the zones tested, sensor measurements along on the walls and near the inlet and outlet provided the greatest improvement in the accuracy of the estimated airflow patterns when compared with the results using measurements from other locations.