We prove a Saad's type bound for harmonic Ritz vectors of a Hermitian matrix. The new bound reveals a dependence of the harmonic Rayleigh--Ritz procedure on the condition number of a shifted problem operator. Several practical implications are discussed. In particular, the bound motivates incorporation of preconditioning into the harmonic Rayleigh--Ritz scheme.
In particular, if @math is Hermitian, the result of @cite_4 states that eq:chen.jia (x, v) 1 + ^2 |B^ -1 |^2 sep ( ,G)^2 (x, K), where @math , @math , and @math denotes an orthogonal projector onto @math . The quantity @math describes separation of the targeted eigenvalue @math from the harmonic Ritz values different from the one associated with @math , which are the eigenvalues of @math ; see @cite_4 for the precise definition of @math .
@cite_4
1975625541
Let A be a real m×n matrix with m≧n. It is well known (cf. [4]) that @math (1) where @math The matrix U consists of n orthonormalized eigenvectors associated with the n largest eigenvalues of AA T , and the matrix V consists of the orthonormalized eigenvectors of A T A. The diagonal elements of ∑ are the non-negative square roots of the eigenvalues of A T A; they are called singular values. We shall assume that @math Thus if rank(A)=r, σ r+1 = σ r+2=⋯=σ n = 0. The decomposition (1) is called the singular value decomposition (SVD). We derive a new upper bound on the diameter of a polyhedron @math P = x ? R n : A x ≤ b , where @math A ? Z m × n . The bound is polynomial in @math n and the largest absolute value of a sub-determinant of @math A , denoted by @math Δ . More precisely, we show that the diameter of @math P is bounded by @math O ( Δ 2 n 4 log n Δ ) . If @math P is bounded, then we show that the diameter of @math P is at most @math O ( Δ 2 n 3.5 log n Δ ) . For the special case in which @math A is a totally unimodular matrix, the bounds are @math O ( n 4 log n ) and @math O ( n 3.5 log n ) respectively. This improves over the previous best bound of @math O ( m 16 n 3 ( log m n ) 3 ) due to Dyer and Frieze (Math Program 64:1---16, 1994). Introduction Preliminaries Special linear groups: @math Orthogonal groups: @math Symplectic groups: @math Unitary groups: @math Proofs of Theorems 1.1 and 1.1, and of corollaries 1.2-1.4 Permutation group algorithms Concluding remarks References. The little Grothendieck problem consists of maximizing @math źijCijxixj for a positive semidefinite matrix C, over binary variables @math xiź ?1 . In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given @math CźRdn?dn a positive semidefinite matrix, the objective is to maximize @math źijtrCijTOiOjT restricting @math Oi to take values in the group of orthogonal matrices @math Od, where @math Cij denotes the (ij)-th @math d?d block of C. We propose an approximation algorithm, which we refer to as Orthogonal-Cut, to solve the little Grothendieck problem over the group of orthogonal matrices @math Od and show a constant approximation ratio. Our method is based on semidefinite programming. For a given @math dź1, we show a constant approximation ratio of @math źR(d)2, where @math źR(d) is the expected average singular value of a @math d?d matrix with random Gaussian @math N0,1d i.i.d. entries. For @math d=1 we recover the known @math źR(1)2=2 ź approximation guarantee for the classical little Grothendieck problem. Our algorithm and analysis naturally extends to the complex valued case also providing a constant approximation ratio for the analogous little Grothendieck problem over the Unitary Group @math Ud. Orthogonal-Cut also serves as an approximation algorithm for several applications, including the Procrustes problem where it improves over the best previously known approximation ratio of @math 122. The little Grothendieck problem falls under the larger class of problems approximated by a recent algorithm proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler and provides better approximation with matching integrality gaps. Finally, we also provide an improved approximation algorithm for the more general little Grothendieck problem over the orthogonal (or unitary) group with rank constraints, recovering, when @math d=1, the sharp, known ratios. In this paper we study general @math l p regularized unconstrained minimization problems. In particular, we derive lower bounds for nonzero entries of the first- and second-order stationary points and hence also of local minimizers of the @math l p minimization problems. We extend some existing iterative reweighted @math l 1 ( @math IRL 1 ) and @math l 2 ( @math IRL 2 ) minimization methods to solve these problems and propose new variants for them in which each subproblem has a closed-form solution. Also, we provide a unified convergence analysis for these methods. In addition, we propose a novel Lipschitz continuous @math ∈ -approximation to @math ? x ? p p . Using this result, we develop new @math IRL 1 methods for the @math l p minimization problems and show that any accumulation point of the sequence generated by these methods is a first-order stationary point, provided that the approximation parameter @math ∈ is below a computable threshold value. This is a remarkable result since all existing iterative reweighted minimization methods require that @math ∈ be dynamically updated and approach zero. Our computational results demonstrate that the new @math IRL 1 method and the new variants generally outperform the existing @math IRL 1 methods (Chen and Zhou in 2012; Foucart and Lai in Appl Comput Harmon Anal 26:395---407, 2009). This text is about spiked models of non Hermitian random matrices. More specifically, we consider matrices of the type @math , where the rank of @math stays bounded as the dimension goes to infinity and where the matrix @math is a non Hermitian random matrix, satisfying an isotropy hypothesis: its distribution is invariant under the left and right actions of the unitary group. The macroscopic eigenvalue distribution of such matrices is governed by the so called Single Ring Theorem, due to Guionnet, Krishnapur and Zeitouni. We first prove that if @math has some eigenvalues out of the maximal circle of the single ring, then @math has some eigenvalues (called outliers) in the neighborhood of those of @math , which is not the case for the eigenvalues of @math in the inner cycle of the single ring. Then, we study the fluctuations of the outliers of @math around the eigenvalues of @math and prove that they are distributed as the eigenvalues of some finite dimensional random matrices. Such facts had already been noticed for Hermitian models. More surprising facts are that outliers can here have very various rates of convergence to their limits (depending on the Jordan Canonical Form of @math ) and that some correlations can appear between outliers at a macroscopic distance from each other (a fact already noticed by Knowles and Yin in the Hermitian case, but only in the case of non Gaussian models, whereas spiked Gaussian matrices belong to our model and can have such correlated outliers). Our first result generalizes a previous result by Tao for matrices with i.i.d. entries, whereas the second one (about the fluctuations) is new. Let @math be a positive integer and @math be a positive even integer. Let @math be an @math order @math -dimensional real weakly symmetric tensor and @math be a real weakly symmetric positive definite tensor of the same size. @math is called a @math -eigenvalue of @math if @math for some @math . In this paper, we introduce two unconstrained optimization problems and obtain some variational characterizations for the minimum and maximum @math --eigenvalues of @math . Our results extend Auchmuty's unconstrained variational principles for eigenvalues of real symmetric matrices. This unconstrained optimization approach can be used to find a Z-, H-, or D-eigenvalue of an even order weakly symmetric tensor. We provide some numerical results to illustrate the effectiveness of this approach for finding a Z-eigenvalue and for determining the positive semidefiniteness of an even order symmetric tensor. We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with 2-variable constraints (2-CSP's). More concretely, we show for every 2-CSP instance I a rounding algorithm for r rounds of the Lasserre SDP hierarchy for I that obtains an integral solution that is at most worse than the relaxation's value (normalized to lie in [0,1]), as long as r > k ( ) ( ) ;, where k is the alphabet size of I, @math , and @math denotes the number of eigenvalues larger than @math in the normalized adjacency matrix of the constraint graph of @math . In the case that @math is a instance, the threshold @math is only a polynomial in @math , and is independent of the alphabet size. Also in this case, we can give a non-trivial bound on the number of rounds for instance. In particular our result yields an SDP-hierarchy based algorithm that matches the performance of the recent subexponential algorithm of Arora, Barak and Steurer (FOCS 2010) in the worst case, but runs faster on a natural family of instances, thus further restricting the set of possible hard instances for Khot's Unique Games Conjecture. Our algorithm actually requires less than the @math constraints specified by the @math level of the Lasserre hierarchy, and in some cases @math rounds of our program can be evaluated in time @math . We describe and analyze a randomized homotopy algorithm for the Hermitian eigenvalue problem. Given an @math n×n Hermitian matrix @math A, the algorithm returns, almost surely, a pair @math (?,v) which approximates, in a very strong sense, an eigenpair of @math A. We prove that the expected cost of this algorithm, where the expectation is both over the random choices of the algorithm and a probability distribution on the input matrix @math A, is @math O(n6), that is, cubic on the input size. Our result relies on a cost assumption for some pseudorandom number generators whose rationale is argued by us. In this paper, we study online algorithms that schedule malleable jobs, i.e., jobs that can be parallelized on any subset of the available @math m identical machines. We study a model that accounts for the tradeoff between multiprocessor speedup and overhead time, namely, if job @math j has processing requirement @math pj and is assigned to run on @math kj machines, then @math j's execution time becomes @math pj kj+(kj-1)c, where @math c is a constant parameter to the problem. For @math m=2, we present an online algorithm OCS that has a strong competitive ratio of 3 2, matching a previously established lower bound. We also present an online algorithm ASYM2 that is asymptotically @math ((4-∈) (3-∈))-competitive when @math m=2, where @math 0<∈≤2 is a parameter to the algorithm, improving upon an existing asymptotically (3 2)-competitive algorithm. Finally, we present an online algorithm OTO that is strongly @math 2-competitive when @math m=3, improving upon the previous best upper bound of @math 9 4. Given a random matrix, what condition number should be expected? This paper presents a proof that for real or complex @math matrices with elements from a standard normal distribution, the expected value of the log of the 2-norm condition number is asymptotic to @math as @math . In fact, it is roughly @math for real matrices and @math for complex matrices as @math . The paper discusses how the distributions of the condition numbers behave for large n for real or complex and square or rectangular matrices. The exact distributions of the condition numbers of @math matrices are also given.Intimately related to this problem is the distribution of the eigenvalues of Wishart matrices. This paper studies in depth the largest and smallest eigenvalues, giving exact distributions in some cases. It also describes the behavior of all the eigenvalues, giving an exact formula for the expected characteristic polynomial. We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property @math is called a @math -graph . If @math satisfies certain properties, then an n-node m-edge @math -graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most @math bits for any continuous superadditive function @math so that there are at most @math distinct @math -node @math -graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such @math include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) @math is directed or undirected; (3) @math is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from @math for @math ; (5) the edges of G are labeled with labels from @math for @math ; and (6) each node (respectively, edge) of G has at most @math self-loops (respectively, @math multiple edges). Moreover, @math and @math are not required to be O(1) for the cases of @math being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes. When graph Ramsey theory is viewed as a game, "Painter" 2-colors the edges of a graph presented by "Builder". Builder wins if every coloring has a monochromatic copy of a fixed graph @math . In the on-line version, iteratively, Builder presents one edge and Painter must color it. Builder must keep the presented graph in a class @math . Builder wins the game @math if a monochromatic copy of @math can be forced. The on-line degree Ramsey number @math is the least @math such that Builder wins @math when @math is the class of graphs with maximum degree at most @math . Our results include: 1) @math if and only if @math is a linear forest or each component lies inside @math . 2) @math , where @math . 3) @math for a tree @math , where @math and @math are two largest vertex degrees. 4) @math , with @math except for finitely many odd values of @math . 5) @math when @math . The lower bounds come from strategies for Painter that color edges red whenever the red graph remains in a specified class. The upper bounds use a result showing that Builder may assume that Painter plays "consistently". This paper is concerned with the problem min @math where X is a convex subset of a linear space H, and f is a smooth real-valued function on H. We propose the class of methods @math , where P denotes projection on X with respect to a Hilbert space norm @math , @math denotes the Frechet derivative of f at @math with respect to another Hilbert space norm @math on H, and @math is a positive scalar stepsize. We thus remove an important restriction in the original proposal of Goldstein [1] and Levitin and Poljak [2], where the norms @math and @math must be the same. It is therefore possible to match the norm @math with the structure of X so that the projection operation is simplified while at the same time reserving the option to choose @math on the basis of approximations to the Hessian of f so as to attain a typically superlinear rate of convergence. The resulting methods are particularly attrac... Let @math be independent random positive variables and let @math , @math Let us denote [ P _1 + + _n < t = G_n (t). ]Theorem. [ t 1 - G_n (t) 1 - G(t) = n, n = 1,2,3, , ]if and only if [ t 1 - G_2 (t) 1 - G(t) = 2. ] This theorem is useful in some investigations of age-dependent branching processes. Let @math XźA2r be a real curve embedded into an even-dimensional affine space. We characterise when the @math rth secant variety to @math X is an irreducible component of the algebraic boundary of the convex hull of the real points @math X(R) of @math X. This fact is then applied to @math 4-dimensional @math SO(2)-orbitopes and to the so called Barvinok---Novik orbitopes to study when they are basic closed semi-algebraic sets. In the case of @math 4-dimensional @math SO(2)-orbitopes, we find all irreducible components of their algebraic boundary. An @math -spanner of a graph G is a subgraph H such that @math for every pair of vertices u,w, where distG'(u,w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible @math -spanner (also known as multiplicative @math -spanner) of size @math for every integer @math , and a polynomially constructible (1,2)-spanner (also known as additive 2-spanner) of size @math . This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant @math there exists a constant @math such that for every @math -vertex graph G there is an efficiently constructible @math -spanner of size @math . The paper is devoted to optimization of resonances associated with 1-D wave equations in inhomogeneous media. The medium's structure is represented by a nonnegative function B. The problem is to design for a given @math a medium that generates a resonance on the line @math with a minimal possible modulus of the imaginary part. We consider an admissible family of mediums that arises in a problem of optimal design for photonic crystals. This admissible family is defined by the constraints @math with certain constants @math . The paper gives an accurate definition of optimal structures that ensures their existence. We prove that optimal structures are piecewise constant functions taking only two extreme possible values @math and @math . This result explains an effect recently observed in numerical experiments. Then we show that intervals of constancy of an optimal structure are tied to the phase of the corresponding resonant mode and write this connection as a nonlinear eigenvalue problem. Given a static array of @math totally ordered objects, the range minimum query problem is to build a data structure that allows us to answer efficiently subsequent on-line queries of the form “what is the position of a minimum element in the subarray ranging from @math to @math ?”. We focus on two settings, where (1) the input array is available at query time, and (2) the input array is available only at construction time. In setting (1), we show new data structures (a) of size @math bits and query time @math for any positive integer function @math for an arbitrary constant @math , or (b) with @math bits and @math query time, where @math denotes the empirical entropy of @math th order of the input array. In setting (2), we give a data structure of size @math bits and query time @math . All data structures can be constructed in linear time and almost in-place. Let @math be constant, and let @math denote the set of r-regular graphs with vertex set V = 1,2,...,n . Let G be chosen randomly from @math . We prove that with high probability ( ) the cover time of a random walk on G is asymptotic to @math .