Condition numbers and perturbation analysis for the Tikhonov regularization of discrete ill‐posed problems

One of the most successful methods for solving the least‐squares problem min_x∥Ax?b∥₂ with a highly ill‐conditioned or rank deficient coefficient matrix A is the method of Tikhonov regularization. In this paper, we derive the normwise, mixed and componentwise condition numbers and componentwise perturbation bounds for the Tikhonov regularization. Our results are sharper than the known results. Some numerical examples are given to illustrate our results. Copyright © 2010 John Wiley & Sons, Ltd.     

Possible isolation number of a matrix over nonnegative integers

Let ?₊ be the semiring of all nonnegative integers and A an m × n matrix over ?₊. The rank of A is the smallest k such that A can be factored as an m × k matrix times a k×n matrix. The isolation number of A is the maximum number of nonzero entries in A such that no two are in any row or any column, and no two are in a 2 × 2 submatrix of all nonzero entries. We have that the isolation number of A is a lower bound of the rank of A. For A with isolation number k, we investigate the possible values of the rank of A and the Boolean rank of the support of A. So we obtain that the isolation number and the Boolean rank of the support of a given matrix are the same if and only if the isolation number is 1 or 2 only. We also determine a special type of m×n matrices whose isolation number is m. That is, those matrices are permutationally equivalent to a matrix A whose support contains a submatrix of a sum of the identity matrix and a tournament matrix.     

A gradual rank increasing process for matrix completion

The matrix completion problem is easy to state: let A be a given data matrix in which some entries are unknown. Then, it is needed to assign “appropriate values” to these entries. A common way to solve this problem is to compute a rank-k matrix, B _k , that approximates A in a least squares sense. Then, the unknown entries in A attain the values of the corresponding entries in B _k . This raises the question of how to determine a suitable matrix rank. The method proposed in this paper attempts to answer this question. It builds a finite sequence of matrices \(B_{k}, k = 1, 2, \dots \), where B _k is a rank-k matrix that approximates A in a least squares sense. The computational effort is reduced by using B _k-1 as starting point in the computation of B _k . The ability of B _k to serve as substitute for A is measured with two objective functions: a “training” function that measures the distance between the known part of A and the corresponding part of B _k , and a “probe” function that assesses the quality of the imputed entries. Watching the changes in these functions as k increases enables us to find an optimal matrix rank. Numerical experiments illustrate the usefulness of the proposed approach.     

Approximating minimum norm solutions of rank-deficient least squares problems

In this paper we consider the solution of linear least squares problems min_x∥Ax - b∥²₂ where the matrix A ∈ R ^{m × n} is rank deficient. Put p = min{m, n}, let σ_i, i = 1, 2,…, p, denote the singular values of A, and let u_i and v_i denote the corresponding left and right singular vectors. Then the minimum norm solution of the least squares problem has the form x* = ∫^r_{i = 1}(u^T_ib/σ_i)v_i, where r ≤ p is the rank of A. The Riley–Golub iteration, x_{k + 1} = arg min_x{∥Ax - b∥²₂ + λ∥x − x_k∥²₂} converges to the minimum norm solution if x₀ is chosen equal to zero. The iteration is implemented so that it takes advantage of a bidiagonal decomposition of A. Thus modified, the iteration requires only O(p) flops (floating point operations). A further gain of using the bidiagonalization of A is that both the singular values σ_i and the scalar products u^T_ib can be computed at marginal extra cost. Moreover, we determine the regularization parameter, λ, and the number of iterations, k, in a way that minimizes the difference x* − x_k with respect to a certain norm. Explicit rules are derived for calculating these parameters. One advantage of our approach is that the numerical rank can be easily determined by using the singular values. Furthermore, by the iterative procedure, x* is approximated without computing the singular vectors of A. This gives a fast and reliable method for approximating minimum norm solutions of well-conditioned rank-deficient least squares problems. Numerical experiments illustrate the viability of our ideas, and demonstrate that the new method gives more accurate approximations than an approach based on a QR decomposition with column pivoting. © 1998 John Wiley & Sons, Ltd.     

The Minimum Rank of a 3 × 3 Partial Block Matrix

After recalling the definition and some basic properties of finite hypergroups—a notion introduced in a recent paper by one of the authors—several non-trivial examples of such hypergroups are constructed. The examples typically consist of n n×n matrices, each of which is an appropriate polynomial in a certain tri-diagonal matrix. The crucial result required in the construction is the following: ‘let A be the matrix with ones on the super-and sub-diagonals, and with main diagonal given by a ₁…a _n which are non-negative integers that form either a non-decreasing or a symmetric unimodal sequence; then A_k =P_k (A) is a non-negative matrix, where p_k denotes the characteristic polynomial of the top k× k principal submatrix of A, for k=1,…,n. The matrices A_k as well as the eigenvalues of A, are explicitly described in some special cases, such as (i) a_i =0 for all ior (ii) a_i =0 for i<n and a_n =1. Characters ot finite abelian hypergroups are defined, and that naturally leads to harmonic analysis on such hypergroups.     

Lanczos and the Riemannian SVD in information retrieval applications

Variations of the latent semantic indexing (LSI) method in information retrieval (IR) require the computation of singular subspaces associated with the k dominant singular values of a large m × n sparse matrix A, where k?min(m,n). The Riemannian SVD was recently generalized to low‐rank matrices arising in IR and shown to be an effective approach for formulating an enhanced semantic model that captures the latent term‐document structure of the data. However, in terms of storage and computation requirements, its implementation can be much improved for large‐scale applications. We discuss an efficient and reliable algorithm, called SPK‐RSVD‐LSI, as an alternative approach for deriving the enhanced semantic model. The algorithm combines the generalized Riemannian SVD and the Lanczos method with full reorthogonalization and explicit restart strategies. We demonstrate that our approach performs as well as the original low‐rank Riemannian SVD method by comparing their retrieval performance on a well‐known benchmark document collection. Copyright 2004 John Wiley & Sons, Ltd.     

Possible numbers of ones in the squares of 0–1 matrices with a given rank

For a symmetric 0–1 matrix A, we give the number of ones in A ² when rank(A) = 1, 2, and give the maximal number of ones in A ² when rank(A) = k (3 ≤ k ≤ n). The sufficient and necessary condition under which the maximal number is achieved is also obtained. For generic 0–1 matrices, we only study the cases of rank 1 and rank 2.     

Null ideals and spanning ranks of matrices

Let Rbe a commutative ring and A?M _m×n . The spanning rank of Ais the smallest positive integer s for which A=PQ(m×s s×n) The spanning rank of the zero matrix is set equal to zero. If Ris a field, then the spanning rank of Ais just the classical rank of A. In the first section of this paper, various theorems and examples are given which indicate how much of the classical theory of rank is still valid for spanning rank over a commutative ring. If A= PQ(n×s s×n) is a spanning rank factorization of a square matrix and D= QP, then Dis called a spanning rank partner of A. In the second part of this paper, the null ideals N _Aand N _Dof Aand Drespectively are compared. For instance, we show N _A=N _Dif s= nand N _A= XN _Dif s<nwhenever Ris a PIDand A≠0. This result sometimes (e.g. s<<n) makes the computation of N _Aeasy.     

On automorphisms of finite Abelian <Emphasis Type="Italic">p</Emphasis>-groups

Let A be a finitely generated abelian group. We describe the automorphism group Aut(A) using the rank of A and its torsion part p-part A _p . For a finite abelian p-group A of type (k ₁, ..., k _n ), simple necessary and sufficient conditions for an n × n-matrix over integers to be associated with an automorphism of A are presented. Then, the automorphism group Aut(A) for a finite p-group A of type (k ₁, k ₂) is analyzed. This work has begin during the visit of the second author to the Faculty of Mathematics and Computer Science, Nicolaus Copernicus University during the period July 31–August 13, 2005. This visit was supported by the Nicolaus Copernicus University and a grant from Cnpq.     

The Hilbert Scheme Parameterizing Finite Length Subschemes of the Line with Support at the Origin

We introduce symmetrizing operators of the polynomial ring A[x] in the variable x over a ring A. When A is an algebra over a field k these operators are used to characterize the monic polynomials F(x) of degree n in A[x] such that A _k k[x]_(x)/(F(x)) is a free A-module of rank n. We use the characterization to determine the Hilbert scheme parameterizing subschemes of length n of k[x]_(x).     

The solvability conditions for inverse eigenproblem of symmetric and anti‐persymmetric matrices and its approximation

The problem of generating a matrix A with specified eigen‐pair, where A is a symmetric and anti‐persymmetric matrix, is presented. An existence theorem is given and proved. A general expression of such a matrix is provided. We denote the set of such matrices by ??????_Eⁿ. The optimal approximation problem associated with ??????_Eⁿ is discussed, that is: to find the nearest matrix to a given matrix A* by A∈??????_Eⁿ. The existence and uniqueness of the optimal approximation problem is proved and the expression is provided for this nearest matrix. Copyright © 2002 John Wiley & Sons, Ltd.     

When is a matrix unitary or Hermitian plus low rank?

Hermitian and unitary matrices are two representatives of the class of normal matrices whose full eigenvalue decomposition can be stably computed in quadratic computing complexity once the matrix has been reduced, for instance, to tridiagonal or Hessenberg form. Recently, fast and reliable eigensolvers dealing with low‐rank perturbations of unitary and Hermitian matrices have been proposed. These structured eigenvalue problems appear naturally when computing roots, via confederate linearizations, of polynomials expressed in, for example, the monomial or Chebyshev basis. Often, however, it is not known beforehand whether or not a matrix can be written as the sum of a Hermitian or unitary matrix plus a low‐rank perturbation. In this paper, we give necessary and sufficient conditions characterizing the class of Hermitian or unitary plus low‐rank matrices. The number of singular values deviating from 1 determines the rank of a perturbation to bring a matrix to unitary form. A similar condition holds for Hermitian matrices; the eigenvalues of the skew‐Hermitian part differing from 0 dictate the rank of the perturbation. We prove that these relations are linked via the Cayley transform. Then, based on these conditions, we identify the closest Hermitian or unitary plus rank k matrix to a given matrix A, in Frobenius and spectral norm, and give a formula for their distance from A. Finally, we present a practical iteration to detect the low‐rank perturbation. Numerical tests prove that this straightforward algorithm is effective.     

The rank of a difference of matrices and associated generalized inverses

Various representations are given to characterize the rank of A-S in terms of rank A+k where A and S are arbitrary complex matrices and k is a function of A and S. It is shown that if S=AMA for some matrix M, and if G is any matrix satisfying A=AGA, then

$\text{rank(A-S) = rankA-nullity (I-SG)}$

. Several alternative forms of this result are established, as are many equivalent conditions to have

$\text{rank(A-S) = rankA-rankS}$

. General forms for the Moore-Penrose inverse of matrices A-S are developed which include as special cases various results by Penrose, Wedin, Hartwig and others.     

Varieties for Modules of Quantum Elementary Abelian Groups

We define a rank variety for a module of a noncocommutative Hopf algebra A = L \rtimes GA = \Lambda \rtimes G where L = k[X₁, ..., X_m]/(X₁^l, ..., X_m^l), G = (\mathbbZ/l\mathbbZ)^m\Lambda = k[X_1, \dots, X_m]/(X_1^{\ell}, \dots, X_m^{\ell}), G = (\mathbb{Z}/\ell\mathbb{Z})^m and char k does not divide ℓ, in terms of certain subalgebras of A playing the role of “cyclic shifted subgroups”. We show that the rank variety of a finitely generated module M is homeomorphic to the support variety of M defined in terms of the action of the cohomology algebra of A. As an application we derive a theory of rank varieties for the algebra Λ. When ℓ=2, rank varieties for Λ-modules were constructed by Erdmann and Holloway using the representation theory of the Clifford algebra. We show that the rank varieties we obtain for Λ-modules coincide with those of Erdmann and Holloway.     

Some results on the cartan matrix of a frobenius algebra

Let F be a field and A a Frobenius algebra over F. The Jacobson radical of A is denoted by J = J(A) and the kth socle of A by S _k (A). Let [Abar]=A/J ^k or A/S _k (A). This article gives new interesting relations between the Cartan matrix of A and that of [Abar]. From these results we prove that the Cartan matrix of A is diagonal if A/Soc(A) is a symmetric algebra. Let G be a finite group. If A is a block of F|G] with the above condition, then the Cartan matrix of A is (n), where n is the order of the defect group of A and the least integer such that Jⁿ (A)=0.     

A direct method for a regularized least‐squares problem

We consider a linear system of the form A₁x₁+ A₂x₂+η=b₁. The vector η consists of identically distributed random variables all with mean zero. The unknowns are split into two groups x₁ and x₂. In the model usually there are more unknowns than observations and the resulting linear system is most often consistent having an infinite number of solutions. Hence some constraint on the parameter vector x is needed. One possibility is to avoid rapid variation in, e.g. the parameters x₂. We formulate the problem as a partially regularized least‐squares problem, and propose a direct solution method based on the QR decomposition of matrix blocks. Further we consider regularizing using one and two regularization parameters, respectively. We also discuss the choice of regularization parameters, and extend Reinsch's method to the case with two parameters. Also the cross‐validation technique is treated. We present test examples taken from an application in modelling of the substance transport in rivers. Copyright © 2009 John Wiley & Sons, Ltd.     

Higher rank numerical ranges and low rank perturbations of quantum channels

For a positive integer k, the rank-k numerical range Λk(A) of an operator A acting on a Hilbert space H of dimension at least k is the set of scalars λ such that PAP=λP for some rank k orthogonal projection P. In this paper, a close connection between low rank perturbation of an operator A and Λk(A) is established. In particular, for 1?r<k it is shown that Λk(A)⊆Λk−r(A+F) for any operator F with rank(F)?r. In quantum computing, this result implies that a quantum channel with a k-dimensional error correcting code under a perturbation of rank at most r will still have a (k−r)-dimensional error correcting code. Moreover, it is shown that if A is normal or if the dimension of A is finite, then Λk(A) can be obtained as the intersection of Λk−r(A+F) for a collection of rank r operators F. Examples are given to show that the result fails if A is a general operator. The closure and the interior of the convex set Λk(A) are completely determined. Analogous results are obtained for Λ_∞(A) defined as the set of scalars λ such that PAP=λP for an infinite rank orthogonal projection P. It is shown that Λ_∞(A) is the intersection of all Λk(A) for k=1,2,…. If A−μI is not compact for all μ∈C, then the closure and the interior of Λ_∞(A) coincide with those of the essential numerical range of A. The situation for the special case when A−μI is compact for some μ∈C is also studied.     

Solution of large‐scale weighted least‐squares problems

A sequence of least‐squares problems of the form min_y∥G^1/2(A^T y?h)∥₂, where G is an n×n positive‐definite diagonal weight matrix, and A an m×n (m?n) sparse matrix with some dense columns; has many applications in linear programming, electrical networks, elliptic boundary value problems, and structural analysis. We suggest low‐rank correction preconditioners for such problems, and a mixed solver (a combination of a direct solver and an iterative solver). The numerical results show that our technique for selecting the low‐rank correction matrix is very effective. Copyright © 2002 John Wiley & Sons, Ltd.     

Monotonicity of permanents of direct sums of doubly stochastic matrices

Let Ωn be the set of all n × n doubly stochastic matrices, let J_n be the n × n matrix all of whose entries are 1/n and let σ _k (A) denote the sum of the permanent of all k × k submatrices of A. It has been conjectured that if A ε Ω _n and A ≠ J_J then g_A,k (θ) ? σ _k ((1 θ)J_n 1 θA) is strictly increasing on [0,1] for k = 2,3,…,n. We show that if A = A ₁ ⊕ ⊕A_t (t ≥ 2) is an n × n matrix where A_i for i = 1,2, …,t, and if for each i g_Ai,ki (θ) is non-decreasing on [0.1] for k_t = 2,3,…,n_i , then g_A,k (θ) is strictly increasing on [0,1] for k = 2,3,…,n.     

A determinantal version of the frobenius-könig theorem

Let F be a field and let {d ₁,…,d_k } be a set of independent indeterminates over F. Let A(d ₁,…,d_k ) be an n × n matrix each of whose entries is an element of F or a sum of an element of F and one of the indeterminates in {d ₁,…,d_k }. We assume that no d ¹ appears twice in A(d ₁,…,d_k ). We show that if det A(d ₁,…,d_k ) = 0 then A(d ₁,…,d_k ) must contain an r × s submatrix B, with entries in F, so that r + s = n + p and rank B ? p ? 1: for some positive integer p.