Acceleration of randomized Kaczmarz method via the Johnson–Lindenstrauss Lemma

The Kaczmarz method is an algorithm for finding the solution to an overdetermined consistent system of linear equations Ax = b by iteratively projecting onto the solution spaces. The randomized version put forth by Strohmer and Vershynin yields provably exponential convergence in expectation, which for highly overdetermined systems even outperforms the conjugate gradient method. In this article we present a modified version of the randomized Kaczmarz method which at each iteration selects the optimal projection from a randomly chosen set, which in most cases significantly improves the convergence rate. We utilize a Johnson–Lindenstrauss dimension reduction technique to keep the runtime on the same order as the original randomized version, adding only extra preprocessing time. We present a series of empirical studies which demonstrate the remarkable acceleration in convergence to the solution using this modified approach.     

A Randomized Kaczmarz Algorithm with Exponential Convergence

The Kaczmarz method for solving linear systems of equations is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Despite the popularity of this method, useful theoretical estimates for its rate of convergence are still scarce. We introduce a randomized version of the Kaczmarz method for consistent, overdetermined linear systems and we prove that it converges with expected exponential rate. Furthermore, this is the first solver whose rate does not depend on the number of equations in the system. The solver does not even need to know the whole system but only a small random part of it. It thus outperforms all previously known methods on general extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations as well as theoretical analysis reveal that our algorithm can converge faster than the celebrated conjugate gradient algorithm. Furthermore, our theory and numerical simulations confirm a prediction of Feichtinger et al. in the context of reconstructing bandlimited functions from nonuniform sampling. T. Strohmer was supported by NSF DMS grant 0511461. R. Vershynin was supported by the Alfred P. Sloan Foundation and by NSF DMS grant 0401032.     

A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates

Reconstructing bandlimited functions from random sampling is an important problem in signal processing. Strohmer and Vershynin obtained good results for this problem by using a randomized version of the Kaczmarz algorithm (RK) and assigning to every equation a probability weight proportional to the average distance of the sample from its two nearest neighbors. However, their results are valid only for moderate to high sampling rates; in practice, it may not always be possible to obtain many samples. Experiments show that the number of projections required by RK and other Kaczmarz variants rises seemingly exponentially when the equations/variables ratio (EVR) falls below 5. CGMN, which is a CG acceleration of Kaczmarz, provides very good results for low values of EVR and it is much better than CGNR and CGNE. A derandomization method, based on an extension of the bit-reversal permutation, is combined with the weights and shown to improve the performance of CGMN and the regular (cyclic) Kaczmarz, which even outperforms RK. A byproduct of our results is the finding that signals composed mainly of high-frequency components are easier to recover.     

Convergence Properties of a Self-adaptive Levenberg-Marquardt Algorithm Under Local Error Bound Condition

We propose a new self-adaptive Levenberg-Marquardt algorithm for the system of nonlinear equations F(x) = 0. The Levenberg-Marquardt parameter is chosen as the product of ‖F_k‖^δ with δ being a positive constant, and some function of the ratio between the actual reduction and predicted reduction of the merit function. Under the local error bound condition which is weaker than the nonsingularity, we show that the Levenberg-Marquardt method converges superlinearly to the solution for δ∈ (0, 1), while quadratically for δ∈ [1, 2]. Numerical results show that the new algorithm performs very well for the nonlinear equations with high rank deficiency. This work is supported by Chinese NSFC grants 10401023 and 10501013, Research Grants for Young Teachers of Shanghai Jiao Tong University, and E-Institute of Shanghai Municipal Education Commission, N. E03004.     

Greedy Drawings of Triangulations

Greedy Routing is a class of routing algorithms in which the packets are forwarded in a manner that reduces the distance to the destination at every step. In an attempt to provide theoretical guarantees for a class of greedy routing algorithms, Papadimitriou and Ratajczak (Theor. Comput. Sci. 344(1):3–14, 2005) came up with the following conjecture:

Any 3-connected planar graph can be drawn in the plane such that for every pair of vertices s and t a distance decreasing path can be found. A path s=v ₁,v ₂,…,v _k =t in a drawing is said to be distance decreasing if ‖v _i −t‖<‖v _i−1−t‖,2≤i≤k where ‖…‖ denotes the Euclidean distance.

We settle this conjecture in the affirmative for the case of triangulations.     

Fixed point theorems for non-Lipschitzian mappings of asymptotically nonexpansive type

LetX be a Banach space,K a nonempty, bounded, closed and convex subset ofX, and supposeT:K→K satisfies: for eachx∈K, lim sup _i→∞{sup _y∈K ‖t ⁱx−Tⁱy∼−‖x−y‖}≦0. IfT ^N is continuous for some positive integerN, and if either (a)X is uniformly convex, or (b)K is compact, thenT has a fixed point inK. The former generalizes a theorem of Goebel and Kirk for asymptotically nonexpansive mappings. These are mappingsT:K→K satisfying, fori sufficiently large, ‖Tⁱx−Tⁱy‖≦k _i‖x−y∼,x,y∈K, wherek _i→1 asi→∞. The precise assumption in (a) is somewhat weaker than uniform convexity, requiring only that Goebel’s characteristic of convexity, ɛ₀ (X), be less than one. Research supported by National Science Foundation Grant GP 18045.     

On Spherical Averages of Radial Basis Functions

A radial basis function (RBF) has the general form

Onp-absolutely summing constants of banach spaces

Given 1≦p<∞ and a real Banach spaceX, we define thep-absolutely summing constantμ _p(X) as inf{Σ _i ^=1/m |x*(x _i)|^p p Σ _i ^=1/m ‖x _i‖^p p]¹ p}, where the supremum ranges over {x*∈X*; ‖x*‖≤1} and the infimum is taken over all sets {x ₁,x ₂, …,x _m} ⊂X such that Σ _i ^=1/m ‖x _i‖>0. It follows immediately from [2] thatμ _p(X)>0 if and only ifX is finite dimensional. In this paper we find the exact values ofμ _p(X) for various spaces, and obtain some asymptotic estimates ofμ _p(X) for general finite dimensional Banach spaces. This is a part of the author’s Ph.D. Thesis prepared at the Hebrew University of Jerusalem, under the supervision of Prof. A. Dvoretzky and Prof. J. Lindenstrauss.     

On extremal point distributions in the Euclidean plane

We ask for the maximum σ _n ^γ of Σ _i,j=1 ⁿ ‖x _i-x _j‖^γ, where x ₁,χ,x _n are points in the Euclidean plane R ² with ‖x_i-x_j‖ ≦1 for all 1≦ i,j ≦ n and where ‖.‖^γ denotes the γ-th power of the Euclidean norm, γ ≧ 1. (For γ =1 this question was stated by L. Fejes Tóth in [1].) We calculate the exact value of σ _n ^γ for all γ γ 1,0758χ and give the distributions which attain the maximum σ _n ^γ . Moreover we prove upper bounds for σ _n ^γ for all γ ≧ 1 and calculate the exact value of σ ₄ ^γ for all γ ≧ 1. This revised version was published online in June 2006 with corrections to the Cover Date.     

Trust-region and other regularisations of linear least-squares problems

We consider methods for regularising the least-squares solution of the linear system Ax=b. In particular, we propose iterative methods for solving large problems in which a trust-region bound ‖x‖≤Δ is imposed on the size of the solution, and in which the least value of linear combinations of ‖Ax−b‖₂ ^q and a regularisation term ‖x‖₂ ^p for various p and q=1,2 is sought. In each case, one or more “secular” equations are derived, and fast Newton-like solution procedures are suggested. The resulting algorithms are available as part of the ALAHAD optimization library. This work was partially supported by EPSRC grants EP/E053351/1 and EP/F005369/1.     

The zero-two law in Banach lattice algebras

LetA be a unital Banach lattice algebra and leta εA ⁺ satisfy ‖a ‖≦1. Then either ‖a ⁿ⁺¹ −a ⁿ ‖=2 for alln≧0 or else ‖a ⁿ⁺¹ −a ⁿ ‖ → 0 asn → ∞. Cyclicity of the peripheral spectrum ofa is also established.     

Slices for biparabolics of index 1

Let \mathfraka \mathfrak{a} be an algebraic Lie subalgebra of a simple Lie algebra \mathfrakg \mathfrak{g} with index \mathfraka \mathfrak{a}  ≤ rank \mathfrakg \mathfrak{g} . Let Y( \mathfraka ) Y\left( \mathfrak{a} \right) denote the algebra of \mathfraka \mathfrak{a} invariant polynomial functions on \mathfraka^* {\mathfrak{a}^*} . An algebraic slice for \mathfraka \mathfrak{a} is an affine subspace η + V with h ? \mathfraka^* \eta \in {\mathfrak{a}^*} and V ì \mathfraka^* V \subset {\mathfrak{a}^*} subspace of dimension index \mathfraka \mathfrak{a} such that restriction of function induces an isomorphism of Y( \mathfraka ) Y\left( \mathfrak{a} \right) onto the algebra R[η + V] of regular functions on η + V. Slices have been obtained in a number of cases through the construction of an adapted pair (h, η) in which h ? \mathfraka h \in \mathfrak{a} is ad-semisimple, η is a regular element of \mathfraka^* {\mathfrak{a}^*} which is an eigenvector for h of eigenvalue minus one and V is an h stable complement to ( \textad  \mathfraka )h \left( {{\text{ad}}\;\mathfrak{a}} \right)\eta in \mathfraka^* {\mathfrak{a}^*} . The classical case is for \mathfrakg \mathfrak{g} semisimple [16], [17]. Yet rather recently many other cases have been provided; for example, if \mathfrakg \mathfrak{g} is of type A and \mathfraka \mathfrak{a} is a “truncated biparabolic” [12] or a centralizer [13]. In some of these cases (in particular when the biparabolic is a Borel subalgebra) it was found [13], [14], that η could be taken to be the restriction of a regular nilpotent element in \mathfrakg \mathfrak{g} . Moreover, this calculation suggested [13] how to construct slices outside type A when no adapted pair exists. This article makes a first step in taking these ideas further. Specifically, let \mathfraka \mathfrak{a} be a truncated biparabolic of index one. (This only arises if \mathfrakg \mathfrak{g} is of type A and \mathfraka \mathfrak{a} is the derived algebra of a parabolic subalgebra whose Levi factor has just two blocks whose sizes are coprime.) In this case it is shown that the second member of an adapted pair (h, η) for \mathfraka \mathfrak{a} is the restriction of a particularly carefully chosen regular nilpotent element of \mathfrakg \mathfrak{g} . A by-product of our analysis is the construction of a map from the set of pairs of coprime integers to the set of all finite ordered sequences of ±1.     

Absolutely continuous invariant measures for piecewise expandingC 2 transformations inR N

LetS be a bounded region inR ^N and let ℊ={S _i} _i ^=1/m be a partition ofS into a finite number of subsets having piecewiseC ² boundaries. We assume that whereC ² segments of the boundaries meet, the angle subtended by tangents to these segments at the point of contact is bounded away from 0. Letτ:S →S be piecewiseC ² on ℊ and expanding in the sense that there exists 0<σ< 1 such that for anyi=1, 2, ...,m, ‖Dτ _i ⁻¹ ‖<σ, whereDτ _i ⁻¹ is the derivative matrix ofτ _i ⁻¹ and ‖ ‖ is the euclidean matrix norm. The main result provides an upper bound onσ which guarantees the existence of an absolutely continuous invariant measure forτ. The research of the second author was supported by NSERC and FCAR grants.     

<Emphasis Type="Italic">P</Emphasis>-orderings of finite subsets of Dedekind domains

If R is a Dedekind domain, P a prime ideal of R and S⊆R a finite subset then a P-ordering of S, as introduced by M. Bhargava in (J. Reine Angew. Math. 490:101–127, 1997), is an ordering {a _i } _i=1 ^m of the elements of S with the property that, for each 1<i≤m, the choice of a _i minimizes the P-adic valuation of ∏ _j<i (s−a _j ) over elements s∈S. If S, S ^′ are two finite subsets of R of the same cardinality then a bijection φ:S→S ^′ is a P-ordering equivalence if it preserves P-orderings. In this paper we give upper and lower bounds for the number of distinct P-orderings a finite set can have in terms of its cardinality and give an upper bound on the number of P-ordering equivalence classes of a given cardinality.     

A Simple Proof of Perelman’s Collapsing Theorem for 3-manifolds

We will simplify earlier proofs of Perelman’s collapsing theorem for 3-manifolds given by Shioya–Yamaguchi (J. Differ. Geom. 56:1–66, 2000; Math. Ann. 333: 131–155, 2005) and Morgan–Tian ( [math.DG], 2008). A version of Perelman’s collapsing theorem states: “Let {M³_i}\{M^{3}_{i}\} be a sequence of compact Riemannian 3-manifolds with curvature bounded from below by (−1) and $\mathrm{diam}(M^{3}_{i})\ge c_{0}>0$\mathrm{diam}(M^{3}_{i})\ge c_{0}>0 . Suppose that all unit metric balls in M³_iM^{3}_{i} have very small volume, at most v _i →0 as i→∞, and suppose that either M³_iM^{3}_{i} is closed or has possibly convex incompressible toral boundary. Then M³_iM^{3}_{i} must be a graph manifold for sufficiently large i”. This result can be viewed as an extension of the implicit function theorem. Among other things, we apply Perelman’s critical point theory (i.e., multiple conic singularity theory and his fibration theory) to Alexandrov spaces to construct the desired local Seifert fibration structure on collapsed 3-manifolds.     

Inequalities and sphere-packing inl p

If 1<p<∞, there is a constantr _p <1/2 so that ifr>r _p only a bounded number of balls inl _p of radiusr can be packed into the unit ball ofl _p . We obtain the exact value of this bound for eachp andr as a consequence of several new inequalities relating the expressions Σλ _i λ _j ‖x _i –x _j ‖ ^p , Σλ _i ‖x _i ‖ ^p and Σλ _i ^/2 for sequences (x _i ) ₁ ⁿ ⊂l _p and (λ _i ) ₁ ⁿ ⊂R.     

Local linear operators and multicontour solutions of homogeneous coupled map lattices

Theorems are proved establishing a relationship between the spectra of the linear operators of the formA+Ωg _iB_ig_i ⁻¹ andA+B _i, whereg _i∈G, andG is a group acting by linear isometric operators. It is assumed that the closed operatorsA andB _i possess the following property: ‖B _iA⁻¹gB_jA⁻¹‖→0 asd(e,g)→∞. Hered is a left-invariant metric onG ande is the unit ofG. Moreover, the operatorA is invariant with respect to the action of the groupG. These theorems are applied to the proof of the existence of multicontour solutions of dynamical systems on lattices. Translated fromMatematicheskie Zametki, Vol. 65, No. 1, pp. 37–47, January, 1999.     

Codescente en K-théorie étale et corps de nombres

In this paper, we give a codescent criterion for the higher tame kernelK _2i ^−2/ét O _E for a Galoisp-extensionE/F of algebraic number fields (p odd). As an application, we give fori∈ℤ a “going-up” theorem for certain property called (p, i)-regularity, which allows us in particular to construct examples of number fields verifying “twisted” Leopoldt conjectures.      

A globally convergent inexact Newton method with a new choice for the forcing term

In inexact Newton methods for solving nonlinear systems of equations, an approximation to the step s _k of the Newton’s system J(x _k )s=−F(x _k ) is found. This means that s _k must satisfy a condition like ‖F(x _k )+J(x _k )s _k ‖≤η _k ‖F(x _k )‖ for a forcing term η _k ∈[0,1). Possible choices for η _k have already been presented. In this work, a new choice for η _k is proposed. The method is globalized using a robust backtracking strategy proposed by Birgin et al. (Numerical Algorithms 32:249–260, 2003), and its convergence properties are proved. Several numerical experiments with boundary value problems are presented. The numerical performance of the proposed algorithm is analyzed by the performance profile tool proposed by Dolan and Moré (Mathematical Programming Series A 91:201–213, 2002). The results obtained show a competitive inexact Newton method for solving academic and applied problems in several areas. Supported by FAPESP, CNPq, PRONEX-Optimization.     

Positive definite functions and stable random vectors

We say that a random vector X = (X ₁, …, X _n ) in ℝ ⁿ is an n-dimensional version of a random variable Y if, for any a ∈ ℝ ⁿ , the random variables Σa _i X _i and γ(a)Y are identically distributed, where γ: ℝ ⁿ → [0,∞) is called the standard of X. An old problem is to characterize those functions γ that can appear as the standard of an n-dimensional version. In this paper, we prove the conjecture of Lisitsky that every standard must be the norm of a space that embeds in L ₀. This result is almost optimal, as the norm of any finite-dimensional subspace of L _p with p ∈ (0, 2] is the standard of an n-dimensional version (p-stable random vector) by the classical result of P. Lèvy. An equivalent formulation is that if a function of the form f(‖ · ‖ _K ) is positive definite on ℝ ⁿ , where K is an origin symmetric star body in ℝ ⁿ and f: ℝ → ℝ is an even continuous function, then either the space (ℝ ⁿ , ‖·‖ _K ) embeds in L ₀ or f is a constant function. Combined with known facts about embedding in L ₀, this result leads to several generalizations of the solution of Schoenberg’s problem on positive definite functions.