On the condition number of the total least squares problem

This paper concerns singular value decomposition (SVD)-based computable formulas and bounds for the condition number of the total least squares (TLS) problem. For the TLS problem with the coefficient matrix $A$ and the right-hand side $b$ , a new closed formula is presented for the condition number. Unlike an important result in the literature that uses the SVDs of both $A$ and $[A,\ b]$ , our formula only requires the SVD of $[A,\ b]$ . Based on the closed formula, both lower and upper bounds for the condition number are derived. It is proved that they are always sharp and estimate the condition number accurately. A few lower and upper bounds are further established that involve at most the smallest two singular values of $A$ and of $[A,\ b]$ . Tightness of these bounds is discussed, and numerical experiments are presented to confirm our theory and to demonstrate the improvement of our upper bounds over the two upper bounds due to Golub and Van Loan as well as Baboulin and Gratton. Such lower and upper bounds are particularly useful for large scale TLS problems since they require the computation of only a few singular values of $A$ and $[A, \ b]$ other than all the singular values of them.     

Localization and delocalization of eigenvectors for heavy-tailed random matrices

Consider an $n \times n$ Hermitian random matrix with, above the diagonal, independent entries with $\alpha $ -stable symmetric distribution and $0 < \alpha < 2$ . We establish new bounds on the rate of convergence of the empirical spectral distribution of this random matrix as $n$ goes to infinity. When $1 < \alpha < 2$ and $ p > 2$ , we give vanishing bounds on the $L^p$ -norm of the eigenvectors normalized to have unit $L^2$ -norm. On the contrary, when $0 < \alpha < 2/3$ , we prove that these eigenvectors are localized.     

On maximum likelihood estimation of the concentration parameter of von Mises–Fisher distributions

Maximum likelihood estimation of the concentration parameter of von Mises–Fisher distributions involves inverting the ratio \(R_\nu = I_{\nu +1} / I_\nu \) of modified Bessel functions and computational methods are required to invert these functions using approximative or iterative algorithms. In this paper we use Amos-type bounds for \(R_\nu \) to deduce sharper bounds for the inverse function, determine the approximation error of these bounds, and use these to propose a new approximation for which the error tends to zero when the inverse of \(R_\nu \) is evaluated at values tending to \(1\) (from the left). We show that previously introduced rational bounds for \(R_\nu \) which are invertible using quadratic equations cannot be used to improve these bounds.     

Reorthogonalized block classical Gram–Schmidt

A reorthogonalized block classical Gram–Schmidt algorithm is proposed that factors a full column rank matrix $A$ into $A=QR$ where $Q$ is left orthogonal (has orthonormal columns) and $R$ is upper triangular and nonsingular. This block Gram–Schmidt algorithm can be implemented using matrix–matrix operations making it more efficient on modern architectures than orthogonal factorization algorithms based upon matrix-vector operations and purely vector operations. Gram–Schmidt orthogonal factorizations are important in the stable implementation of Krylov space methods such as GMRES and in approaches to modifying orthogonal factorizations when columns and rows are added or deleted from a matrix. With appropriate assumptions about the diagonal blocks of $R$ , the algorithm, when implemented in floating point arithmetic with machine unit $\varepsilon _M$ , produces $Q$ and $R$ such that $\Vert I- Q ^T\!~ Q \Vert =O(\varepsilon _M)$ and $\Vert A-QR \Vert =O(\varepsilon _M\Vert A \Vert )$ . The first of these bounds has not been shown for a block Gram–Schmidt procedure before. As consequence of these results, we provide a different analysis, with a slightly different assumption, that re-establishes a bound of Giraud et al. (Num Math, 101(1):87–100, 2005) for the CGS2 algorithm.     

On Artin Algebras Arising from Morita Contexts

We study Morita rings \(\Lambda _{(\phi ,\psi )}=\left (\begin {array}{cc}A &_{A}N_{B} \\ _{B}M_{A} & B \end {array}\right )\) in the context of Artin algebras from various perspectives. First we study covariantly finite, contravariantly finite, and functorially finite subcategories of the module category of a Morita ring when the bimodule homomorphisms \(\phi \) and \(\psi \) are zero. Further we give bounds for the global dimension of a Morita ring \(\Lambda _{(0,0)}\) , as an Artin algebra, in terms of the global dimensions of A and B in the case when both \(\phi \) and \(\psi \) are zero. We illustrate our bounds with some examples. Finally we investigate when a Morita ring is a Gorenstein Artin algebra and then we determine all the Gorenstein-projective modules over the Morita ring \(\Lambda _{\phi ,\psi }\) in case \(A=N=M=B\) and A an Artin algebra.     

Error bounds for Gauss-type quadratures with Bernstein–Szegő weights

The paper is concerned with the derivation of error bounds for Gauss-type quadratures with Bernstein?Szeg? weights, $${\int\limits_{-1}^{1}}f(t)w(t)\, dt=G_{n}[f]+R_{n}(f),\quad G_{n}[f]=\sum\limits_{\nu=1}^{n}\lambda_{\nu} f(\tau_{\nu}) \quad(n\in\textbf{N}),$$ where f is an analytic function inside an elliptical contour \(\mathcal{E}_{\rho}\) with foci at \(\mp 1\) and sum of semi-axes \(\rho > 1\) , and w is a nonnegative and integrable weight function of Bernstein?Szeg? type. The derivation of effective bounds on \(|R_{n}(f)|\) is possible if good estimates of \(\max_{z\in\mathcal{E}_{\rho}}|K_{n}(z)|\) are available, especially if one knows the location of the extremal point \(\eta\in\mathcal{E}_{\rho}\) at which \(|K_{n}|\) attains its maximum. In such a case, instead of looking for upper bounds on \(\max_{z\in\mathcal{E}_{\rho}}|K_{n}(z)|\) , one can simply try to calculate \(|K_{n}(\eta,w)|\) . In the case under consideration, i.e. when $$w(t)= \frac{(1-t^{2})^{-1/2}}{\beta(\beta-2\alpha)\,t^{2} +2\delta(\beta-\alpha)\,t+\alpha^{2}+\delta^{2}},\quad t\in(-1,1),$$ for some \(\alpha,\beta,\delta\) , which satisfy \(0<\alpha<\beta,\ \beta\ne 2\alpha,\vert\delta\vert<\beta-\alpha\) , the location on the elliptical contours where the modulus of the kernel attains its maximum value is investigated. This leads to effective bounds on \(|R_{n}(f)|\) . The quality of the derived bounds is analyzed by a comparison with other error bounds proposed in the literature for the same class of integrands.     

A construction for strength-3 covering arrays from linear feedback shift register sequences

We present a new construction for covering arrays inspired by ideas from Munemasa (Finite Fields Appl 4:252–260, 1998) using linear feedback shift registers (LFSRs). For a primitive polynomial \(f\) of degree \(m\) over \(\mathbb F _q\) , by taking all unique subintervals of length \(\frac{q^m-1}{q-1}\) from the LFSR generated by \(f\) , we derive a general construction for optimal variable strength orthogonal arrays over an infinite family of abstract simplicial complexes. For \(m=3\) , by adding the subintervals of the reversal of the LFSR to the variable strength orthogonal array, we derive a strength-3 covering array over \(q^2+q+1\) factors, each with \(q\) levels that has size only \(2q^3-1\) , i.e. a \(\text {CA}(2q^3-1; 3, q^2+q+1, q)\) whenever \(q\) is a prime power. When \(q\) is not a prime power, we obtain results by using fusion operations on the constructed array for higher prime powers and obtain improved bounds. Colbourn maintains a repository of the best known bounds for covering array sizes for all \(2 \le q \le 25\) . Our construction, with fusing when applicable, currently holds records of the best known upper bounds in this repository for all \(q\) except \(q = 2,3,6\) . By using these covering arrays as ingredients in recursive constructions, we build covering arrays over larger numbers of factors, again providing significant improvements on the previous best upper bounds.     

On Gromov’s Method of Selecting Heavily Covered Points

A result of Boros and Füredi ( \(d=2\) ) and of Bárány (arbitrary \(d\) ) asserts that for every \(d\) there exists \(c_d>0\) such that for every \(n\) -point set \(P\subset {\mathbb {R}}^d\) , some point of \({\mathbb {R}}^d\) is covered by at least of the \(d\) -simplices spanned by the points of  \(P\) . The largest possible value of \(c_d\) has been the subject of ongoing research. Recently Gromov improved the existing lower bounds considerably by introducing a new, topological proof method. We provide an exposition of the combinatorial component of Gromov’s approach, in terms accessible to combinatorialists and discrete geometers, and we investigate the limits of his method. In particular, we give tighter bounds on the cofilling profiles for the \((n-1)\) -simplex. These bounds yield a minor improvement over Gromov’s lower bounds on \(c_d\) for large \(d\) , but they also show that the room for further improvement through the cofilling profiles alone is quite small. We also prove a slightly better lower bound for \(c_3\) by an approach using an additional structure besides the cofilling profiles. We formulate a combinatorial extremal problem whose solution might perhaps lead to a tight lower bound for  \(c_d\) .     

Torsion homology of arithmetic lattices and K_2 of imaginary fields

Let \(X = G/K\) be a symmetric space of noncompact type. A result of Gelander provides exponential upper bounds in terms of the volume for the torsion homology of the noncompact arithmetic locally symmetric spaces \(\Gamma \backslash X\) . We show that under suitable assumptions on \(X\) this result can be extended to the case of nonuniform arithmetic lattices \(\Gamma \subset G\) that may contain torsion. Using recent work of Calegari and Venkatesh we deduce from this upper bounds (in terms of the discriminant) for \(K_2\) of the ring of integers of totally imaginary number fields \(F\) . More generally, we obtain such bounds for rings of \(S\) -integers in  \(F\) .     

Actions of arithmetic groups on homology spheres and acyclic homology manifolds

We establish lower bounds on the dimensions in which arithmetic groups with torsion can act on acyclic manifolds and homology spheres. The bounds rely on the existence of elementary $p$ -groups in the groups concerned. In some cases, including ${\mathrm{Sp}}(2n,\mathbb Z )$ , the bounds we obtain are sharp: if $X$ is a generalized $\mathbb Z /3$ -homology sphere of dimension less than $2n-1$ or a $\mathbb Z /3$ -acyclic $\mathbb Z /3$ -homology manifold of dimension less than $2n$ , and if $n\ge 3$ , then any action of ${\mathrm{Sp}}(2n,\mathbb Z )$ by homeomorphisms on $X$ is trivial; if $n=2$ , then every action of ${\mathrm{Sp}}(2n,\mathbb Z )$ on $X$ factors through the abelianization of ${\mathrm{Sp}}(4,\mathbb Z )$ , which is $\mathbb Z /2$ .     

Unified extension of variance bounds for integrated Pearson family

We use some properties of orthogonal polynomials to provide a class of upper/lower variance bounds for a function $g(X)$ of an absolutely continuous random variable $X$ , in terms of the derivatives of $g$ up to some order. The new bounds are better than the existing ones.     

Bounds for codes and designs in complex subspaces

We introduce the concepts of complex Grassmannian codes and designs. Let $\mathcal{G}_{m,n}$ denote the set of m-dimensional subspaces of ? ⁿ : then a code is a finite subset of $\mathcal{G}_{m,n}$ in which few distances occur, while a design is a finite subset of $\mathcal{G}_{m,n}$ that polynomially approximates the entire set. Using Delsarte’s linear programming techniques, we find upper bounds for the size of a code and lower bounds for the size of a design, and we show that association schemes can occur when the bounds are tight. These results are motivated by the bounds for real subspaces recently found by Bachoc, Bannai, Coulangeon and Nebe, and the bounds generalize those of Delsarte, Goethals and Seidel for codes and designs on the complex unit sphere.     

On lower bounds for cohomology growth in p-adic analytic towers

Let \(p\) and \(\ell \) be two distinct prime numbers and let \(\Gamma \) be a group. We study the asymptotic behaviour of the mod- \(\ell \) Betti numbers in \(p\) -adic analytic towers of finite index subgroups. If \(\Theta \) is a finite \(\ell \) -group of automorphisms of \(\Gamma \) , our main theorem allows to lift lower bounds for the mod- \(\ell \) cohomology growth in the fixed point group \(\Gamma ^\Theta \) to lower bounds for the growth in \(\Gamma \) . We give applications to \(S\) -arithmetic groups and we also obtain a similar result for cohomology with rational coefficients.     

On Sub-determinants and the Diameter of Polyhedra

We derive a new upper bound on the diameter of a polyhedron \(P = \{x {\in } {\mathbb {R}}^n :Ax\le b\}\) , where \(A \in {\mathbb {Z}}^{m\times n}\) . The bound is polynomial in \(n\) and the largest absolute value of a sub-determinant of \(A\) , denoted by \(\Delta \) . More precisely, we show that the diameter of \(P\) is bounded by \(O(\Delta ^2 n^4\log n\Delta )\) . If \(P\) is bounded, then we show that the diameter of \(P\) is at most \(O(\Delta ^2 n^{3.5}\log n\Delta )\) . For the special case in which \(A\) is a totally unimodular matrix, the bounds are \(O(n^4\log n)\) and \(O(n^{3.5}\log n)\) respectively. This improves over the previous best bound of \(O(m^{16}n^3(\log mn)^3)\) due to Dyer and Frieze (Math Program 64:1–16, 1994).     

Filtered Hopf algebras and counting geodesic chords

We prove lower bounds on the growth of certain filtered Hopf algebras by means of a Poincaré–Birkhoff–Witt type theorem for ordered products of primitive elements. When applied to the loop space homology algebra endowed with a natural length-filtration, these bounds lead to lower bounds for the number of geodesic paths between two points. Specifically, given a closed manifold  \(M\) whose universal covering space is not homotopy equivalent to a finite complex and whose fundamental group has polynomial growth, for any Riemannian metric on  \(M\) , any pair of non-conjugate points \(p,q \in M\) , and every component  \({\mathcal C}\) of the space of paths from  \(p\) to  \(q\) , the number of geodesics in  \({\mathcal C}\) of length at most  \(T\) grows at least like \(e^{\sqrt{T}}\) . Using Floer homology, we extend this lower bound to Reeb chords on the spherisation of  \(M\) , and give a lower bound for the volume growth of the Reeb flow.     

Root n estimates of vectors of integrated density partial derivative functionals

Based on a random sample of size \(n\) from an unknown \(d\) -dimensional density \(f\) , the nonparametric estimations of a single integrated density partial derivative functional as well as a vector of such functionals are considered. These single and vector functionals are important in a number of contexts. The purpose of this paper is to derive the information bounds for such estimations and propose estimates that are asymptotically optimal. The proposed estimates are constructed in the frequency domain using the sample characteristic function. For every \(d\) and sufficiently smooth \(f\) , it is shown that the proposed estimates are asymptotically normal, attain the optimal \(O_p(n^{-1/2})\) convergence rate and achieve the (conjectured) information bounds. In simulation studies the superior performances of the proposed estimates are clearly demonstrated.     

On the Stretch Factor of Randomly Embedded Random Graphs

We consider a random graph $\mathcal{G}(n,p)$ whose vertex set $V,$ of cardinality $n,$ has been randomly embedded in the unit square and whose edges, which occur independently with probability $p,$ are given weight equal to the geometric distance between their end vertices. Then each pair $\{u,v\}$ of vertices has a distance in the weighted graph, and a Euclidean distance. The stretch factor of the embedded graph is defined as the maximum ratio of these two distances, over all $\{u,v\}\subseteq V.$ We give upper and lower bounds on the stretch factor (holding asymptotically almost surely), and show that for $p$ not too close to 0 or 1, these bounds are the best possible in a certain sense. Our results imply that the stretch factor is bounded with probability tending to 1 if and only if $n(1-p)$ tends to 0, answering a question of O’Rourke.     

Improved bounds for separating hash families

An ${(N;n,m,\{w_1,\ldots, w_t\})}$ -separating hash family is a set ${\mathcal{H}}$ of N functions ${h: \; X \longrightarrow Y}$ with ${|X|=n, |Y|=m, t \geq 2}$ having the following property. For any pairwise disjoint subsets ${C_1, \ldots, C_t \subseteq X}$ with ${|C_i|=w_i, i=1, \ldots, t}$ , there exists at least one function ${h \in \mathcal{H}}$ such that ${h(C_1), h(C_2), \ldots, h(C_t)}$ are pairwise disjoint. Separating hash families generalize many known combinatorial structures such as perfect hash families, frameproof codes, secure frameproof codes, identifiable parent property codes. In this paper we present new upper bounds on n which improve many previously known bounds. Further we include constructions showing that some of these bounds are tight.     

Reorthogonalization for the Golub–Kahan–Lanczos bidiagonal reduction

The Golub–Kahan–Lanczos (GKL) bidiagonal reduction generates, by recurrence, the matrix factorization of $X \in \mathbb{R }^{m \times n}, m \ge n$ , given by $$\begin{aligned} X = UBV^T \end{aligned}$$ where $U \in \mathbb{R }^{m \times n}$ is left orthogonal, $V \in \mathbb{R }^{n \times n}$ is orthogonal, and $B \in \mathbb{R }^{n \times n}$ is bidiagonal. When the GKL recurrence is implemented in finite precision arithmetic, the columns of $U$ and $V$ tend to lose orthogonality, making a reorthogonalization strategy necessary to preserve convergence of the singular values. The use of an approach started by Simon and Zha (SIAM J Sci Stat Comput, 21:2257–2274, 2000) that reorthogonalizes only one of the two left orthogonal matrices $U$ and $V$ is shown to be very effective by the results presented here. Supposing that $V$ is the matrix reorthogonalized, the reorthogonalized GKL algorithm proposed here is modeled as the Householder Q–R factorization of $\left( \begin{array}{c} 0_{n \times k} \\ X V_k \end{array}\right) $ where $V_k = V(:,1:k)$ . That model is used to show that if $\varepsilon _M $ is the machine unit and $$\begin{aligned} \bar{\eta }= \Vert \mathbf{tril }(I-V^T\!~V)\Vert _F, \end{aligned}$$ where $\mathbf{tril }(\cdot )$ is the strictly lower triangular part of the contents, then: (1) the GKL recurrence produces Krylov spaces generated by a nearby matrix $X + \delta X$ , $\Vert \delta X\Vert _F = \mathcal O (\varepsilon _M + \bar{\eta }) \Vert X\Vert _F$ ; (2) singular values converge in the Lanczos process at the rate expected from the GKL algorithm in exact arithmetic on a nearby matrix; (3) a new proposed algorithm for recovering leading left singular vectors produces better bounds on loss of orthogonality and residual errors.     

Exact Lagrangian immersions with one double point revisited

We study exact Lagrangian immersions with one double point of a closed orientable manifold $K$ into $\mathbb{C }^{n}$ . We prove that if the Maslov grading of the double point does not equal $1$ then $K$ is homotopy equivalent to the sphere, and if, in addition, the Lagrangian Gauss map of the immersion is stably homotopic to that of the Whitney immersion, then $K$ bounds a parallelizable $(n+1)$ -manifold. The hypothesis on the Gauss map always holds when $n=2k$ or when $n=8k-1$ . The argument studies a filling of $K$ obtained from solutions to perturbed Cauchy–Riemann equations with boundary on the image $f(K)$ of the immersion. This leads to a new and simplified proof of some of the main results of Ekholm and Smith (Exact Lagrangian immersions with a single double point 2011)). which treated Lagrangian immersions in the case $n=2k$ by applying similar techniques to a Lagrange surgery of the immersion, as well as to an extension of these results to the odd-dimensional case.