On the Convergence of Stewart's QLP Algorithm for Approximating the SVD

The pivoted QLP decomposition, introduced by Stewart [20], represents the first two steps in an algorithm which approximates the SVD. The matrix A₀ is first factored as A₀=QR, and then the matrix R ^T₁ is factored as R ^T₁=PL ^T, resulting in A=Q₁ LP ^T₀ ^T, with Q and P orthogonal, L lower-triangular, and ₀ and ₁ permutation matrices. Stewart noted that the diagonal elements of L approximate the singular values of A with surprising accuracy. In this paper, we provide mathematical justification for this phenomenon. If there is a gap between _k and _k+1, partition the matrix L into diagonal blocks L ₁₁ and L ₂₂ and off-diagonal block L ₂₁, where L ₁₁ is k-by-k. We show that the convergence of ( _j (L ₁₁)^–1– _j ^–1)/ _j ^–1 for j=1,. . .,k, and of ( _j (L ₂₂)– _k+j )/ _k+j , for j=1,. . .,n–k, are all quadratic in the gap ratio _k+1/ _k . The worst case is therefore at the gap, where the absolute errors L ₁₁ ^–1– _k ^–1 and L ₂₂– _k+1 are thus cubic in _k ^–1 and _k+1, respectively. One order of convergence is due to the rank-revealing pivoting in the first step; then, because of the pivoting in the first step, two more orders are achieved in the second step. Our analysis assumes that ₁=I, that is, that pivoting is done only on the first step. Although our results explain some of the properties of the pivoted QLP decomposition, they hypothesize a gap in the singular values. However, a simple example shows that the decomposition can perform well even in the absence of a gap. Thus there is more to explain, and we hope that our paper encourages others to tackle the problem. The QLP algorithm can be continued beyond the first two steps, and we make some observations concerning the asymptotic convergence. For example, we point out that repeated singular values can accelerate convergence of individual elements. This, in addition to the relative convergence to all of the singular values being quadratic in the gap ratio, further indicates that the QLP decomposition can be powerful even when the ratios between neighboring singular values are close to one.     

Localization of the spectrum of certain non-self-adjoint operators

Let the self-adjoint operator A and the bounded operator B be specified in Hilbert space We let denote the spectral family of the operator A. If (E – E _N ) B ₂+E–_NB ² 0 npnN , then in the complex plane z=+ there will exist the curve ¦ ¦ =f (), limf () = 0 for ± such that the entire spectrum of the operator A+B lies within the region ¦ ¦ f(). In particular, the condition of the theorem will be satisfied when B is a completely continuous operator.Translated from Matematicheskie Zametki, Vol. 3, No. 4, pp. 415–420, April, 1968.The author expresses his appreciation to R. S. Ismagilov for his discussion of the results.     

Geometric methods in the study of irregularities of distribution

Let be a signed measure on E ^d with E ^d =0 and ¦¦E^d<. DefineD _s() as sup ¦H¦ whereH is an open halfspace. Using integral and metric geometric techniques results are proved which imply theorems such as the following.Theorem A. Let be supported by a finite pointsetp _i. ThenD _s()>c _d(₁/ ₂)^1/2{ _{i(p i})²}^1/2 where ₁ is the minimum distance between two distinctp _i, and ₂ is the maximum distance. The numberc _d is an absolute dimensional constant. (The number .05 can be chosen forc ₂ in Theorem A.)Theorem B. LetD be a disk of unit area in the planeE ², andp ₁,p ₂,...,p _n be a set of points lying inD. If m if the usual area measure restricted toD, while nP _i=1/n defines an atomic measure _n, then independently of _n,nD _s(m – _n) .0335n ^1/4. Theorem B gives an improved solution to the Roth disk segment problem as described by Beck and Chen. Recent work by Beck shows thatnD _s(m – _n)cn ^1/4(logn)^–7/2.     

On the boundedness of Cauchy singular operator from the spaceL p toL q,p>q>-1

It is proved that for a Cauchy type singular operator, given by equality (1), to be bounded from the Lebesgue spaceL _p () tol _q (), as = _n=1 ^Ȟ _n , _n ={z:|z|=r _n }, it is necessary and sufficient that either condition (4) or (5) be fulfilled.     

Product-integration with the Clenshaw-Curtis and related points

Summary This paper is concerned with the theoretical properties of a productintegration method for the integral , wherek is absolutely integrable andf is continuous. The integral is approximated by , where the points are given byx _ni =cos(i/n, 0in, and where the weightsw _ni are chosen to make the rule exact iff is any polynomial of degree n. The principal result is that ifkL _p [–1, 1] for somep>1, then the rule converges to the exact result asn for all continuous (or indeed R-integrable) functionsf, and moreover that the sum of the absolute values of the weights converges to the least possible value, namely . A limiting expression for the individual weights is also obtained, under certain assumptions. The results are exteded to other point sets of a similar kind, including the classical Chebyshev points.     

Computations on the growth of the first factor for prime cyclotomic fields

Denote byh(p) the first factor of the class number of the prime cyclotomic fieldk(exp (2i/p)). The theorem:h(p ₂)>h(p ₁) if 641 p ₂>p ₁ 19 is proved by straightforward computation.     

Exact Bounds on the Sizes of Covering Codes

A code c is a covering code of X with radius r if every element of X is within Hamming distance r from at least one codeword from c. The minimum size of such a c is denoted by c _r(X). Answering a question of Hämäläinen et al. [10], we show further connections between Turán theory and constant weight covering codes. Our main tool is the theory of supersaturated hypergraphs. In particular, for n > n ₀(r) we give the exact minimum number of Hamming balls of radius r required to cover a Hamming ball of radius r + 2 in {0, 1}ⁿ. We prove that c _r(B _n(0, r + 2)) = _{1 i r + 1} ( ^{(n + i – 1) / (r + 1) 2}) + n / (r + 1) and that the centers of the covering balls B(x, r) can be obtained by taking all pairs in the parts of an (r + 1)-partition of the n-set and by taking the singletons in one of the parts.     

Contractions Satisfying the Absolute Value Property

Let B(H) denote the algebra of operators on a complex Hilbert space H, and let U denote the class of operators which satisfy the absolute value condition . It is proved that if is a contraction, then either A has a nontrivial invariant subspace or A is a proper contraction and the nonnegative operator is strongly stable. A Putnam-Fuglede type commutativity theorem is proved for contractions A in , and it is shown that if normal subspaces of . It is proved that if are reducing, then every compact operator in the intersection of the weak closure of the range of the derivation with the commutant of A* is quasinilpotent.     

On the distribution of the residues of small multiplicative subgroups of $$ \mathbb{F}_p $$

Distributional properties of small multiplicative subgroups of are obtained. In particular, it is shown that if H < is of size larger than polylogarithmic in p, then, letting β < 1 be a fixed exponent, most elements of any coset aH (a ∈ , arbitrary) will not fall into the interval [−p ^β, p ^β] ∈ . The arguments are based on the theory of heights and results from additive combinatoric.     

A characterization of the periods of periodic points of 1-norm nonexpansive maps

In this paper the set of minimal periods of periodic points of 1-norm nonexpansive maps is studied. This set is denoted by R(n). The main goal is to present a characterization of R(n) by arithmetical and combinatorial constraints. More precisely, it is shown that , where denotes the set of periods of restricted admissible arrays on 2n symbols. The important point of this equality is that is determined by arithmetical and combinatorial constraints only, and that it can be computed in finite time. By using this equality the set R(n) is computed for . Furthermore it is shown that the largest element of R(n) satisfies:      

Sets associated with the farthest point problem

LetS be a convex compact set in a normed linear spaceX. For each cardinal numbern, defineS _n = {x X:x has exactlyn farthest points inS} andT _n = _kn S _k. It is shown that ifX =E thenT ₃ is countable andT ₂ is contractible to a point. Properties of associated level curves are given.     

Undecidability of the theory of Abelian groups with an automorphism

We prove undecidability of the elementary theories of: 1) (torsion-free) Abelian groups; 2) (Archimedean) ordered Abelian groups; 3) complete Abelian groups in the signature +, (x) =y, where + is addition and (x) = y is an automorphism of the (ordered) Abelian group.Translated from Matematicheskie Zametki, Vol. 23, No. 4, pp. 515–520, April, 1978.The author would like to thank A. I. Kokorin for suggesting this topic and A. G. Pinus for his valuable observations.     

Riemannian geometry on the diffeomorphism group of the circle

The topological group of diffeomorphisms of the unit circle of Sobolev class H ^k , for k large enough, is a Banach manifold modeled on the Hilbert space . In this paper we show that the H ¹ right-invariant metric obtained by right-translation of the H ¹ inner product on defines a smooth Riemannian metric on , and we explicitly construct a compatible smooth affine connection. Once this framework has been established results from the general theory of affine connections on Banach manifolds can be applied to study the exponential map, geodesic flow, parallel translation, curvature etc. The diffeomorphism group of the circle provides the natural geometric setting for the Camassa–Holm equation – a nonlinear wave equation that has attracted much attention in recent years – and in this context it has been remarked in various papers how to construct a smooth Riemannian structure compatible with the H ¹ right-invariant metric. We give a self-contained presentation that can serve as a detailed mathematical foundation for the future study of geometric aspects of the Camassa–Holm equation.     

Finite Representability of ℓp in Quotients of Banach Spaces

A typical result of the paper states that if X is a Banach space with a basis and for some 1pq, the spaces _p and _q are finitely block representable in every block subspace of X, then every block subspace of X admits a block quotient Z such that for every r[p,q], the space _r is finitely block representable in Z. Results of a similar nature are also established for ^N _p-block-sequences and asymptotic spaces.     

A White Noise Approach to Stochastic Neumann Boundary-Value Problems

We illustrate the use of white noise analysis in the solution of stochastic partial differential equations by explicitly solving the stochastic Neumann boundary-value problem LU(x)–c(x)U(x)=0, xDR ^d ,(x)U(x)=–W(x), xD, where L is a uniformly elliptic linear partial differential operator and W(x), xR ^d , is d-parameter white noise.     

Concerning the multiplicators of Fourier series in the trigonometric system

In this paper we prove theorems on multiplicators of Fourier series inL _p, where the conditions depend on a parameterp. An example illustrating the importance of these conditions is constructed. Translated fromMatematicheskie Zametki, Vol. 63, No. 2, pp. 235–247, February, 1998.     

Group automorphisms with finite entropy

A compact metrie abelian group X with the normalized Haar measure is a Lebesgue probability space. A group automorphism ofX is an invertible measure preserving transformation of the probability space. This paper is to show that if the entropy of is finite, then there exist totally disconnected subgroupsH andN, a finite-dimensional subgroupS and a subgroupT satisfying the conditions: (i)H, N, S andT are strictly -invariant, (ii)N=HST, (iii)h(| _N )=0, (iv) ifS/N is non-trivial then it is a finite-dimensional solenoidal group with condition (**) (see the definition in §1), (v) ifT/N is non-trivial then it is connected and locally connected, such thatX/N splits into a direct sumX/N=H/NS/NT/N. This result characterizes the structure of finite entropy automorphisms.     

A combinatorial property of points and ellipsoids

For eachd1 there is a constantc _d>0 such that any finite setXR ^d contains a subsetYX, |Y|[1/4d(d+3)]+1 having the following property: ifEY is an ellipsoid, then |E X|c _d |X|.On leave from the Mathematical Institute of the Hungarian Academy of Sciences, 1364 Budapest, P.O. Box 127, Hungary. Supported by a research fellowship from the Science and Engineering Research Council, U.K., and by Hungarian National Foundation for Scientific Research Grant No. 1812.     

The Weyl group and the normalizer of a conditional expectation

We define a discrete groupW(E) associated to a faithful normal conditional expectationE : M N forN M von Neuman algebras. This group shows the relation between the unitary groupU _N and the normalizerN _E ofE, which can be also considered as the isotropy of the action of the unitary groupU _M ofM onE. It is shown thatW(E) is finite if dimZ(N)< and bounded by the index in the factor case. Also sharp bounds of the order ofW(E) are founded.W(E) appears as the fibre of a covering space defined on the orbit ofE by the natural action of the unitary group ofM. W(E) is computed in some basic examples.     

On orthogonal resolutions of the classical Steiner quadruple system SQS(16)

A Steiner quadruple system SQS(16) is a pair where V is a 16-set of objects and is a collection of 4-subsets of V, called blocks, so that every 3-subset of V is contained in exactly one block. By classical is meant the boolean quadruple system, also known as the affine geometry AG(4,2). A parallel class is a collection of four blocks which partition V. The system possesses a resolution or parallelism, since can be partitioned into 35 parallel classes. Two resolutions are called orthogonal when each parallel class of one resolution has at most one block in common with each parallel class of the other resolution. We prove that there are at most nine further resolutions which, together with the classical one, are pairwise orthogonal.