Research Outputs
Permanent URI for this communityhttps://hdl.handle.net/20.500.14288/2
Browse
42 results
Search Results
Publication Open Access A subspace method for large-scale eigenvalue optimization(Society for Industrial and Applied Mathematics (SIAM), 2018) Meerbergen, Karl; Michiels, Wim; Department of Mathematics; Kangal, Fatih; Mengi, Emre; Faculty Member; Department of Mathematics; College of Sciences; Graduate School of Sciences and Engineering; N/A; 113760We consider the minimization or maximization of the Jth largest eigenvalue of an analytic and Hermitian matrix-valued function, and build on Mengi, Yildirim, and Kilic [SIAM T. Matrix Anal. Appl., 35, pp. 699-724, 2014]. This work addresses the setting when the matrix-valued function involved is very large. We describe subspace procedures that convert the original problem into a small-scale one by means of orthogonal projections and restrictions to certain subspaces, and that gradually expand these subspaces based on the optimal solutions of small-scale problems. Global convergence and superlinear rate-of-convergence results with respect to the dimensions of the subspaces are presented in the infinite dimensional setting, where the matrix-valued function is replaced by a compact operator depending on parameters. In practice, it suffices to solve eigenvalue optimization problems involving matrices with sizes on the scale of tens, instead of the original problem involving matrices with sizes on the scale of thousands.
Publication Metadata only A support function based algorithm for optimization with eigenvalue constraints(Siam Publications, 2017) N/A; Department of Mathematics; Mengi, Emre; Faculty Member; Department of Mathematics; College of Sciences; 113760Optimization of convex functions subject to eigenvalue constraints is intriguing because of peculiar analytical properties of eigenvalue functions and is of practical interest because of a wide range of applications in fields such as structural design and control theory. Here we focus on the optimization of a linear objective subject to a constraint on the smallest eigenvalue of an analytic and Hermitian matrix-valued function. We propose a numerical approach based on quadratic support functions that overestimate the smallest eigenvalue function globally. the quadratic support functions are derived by employing variational properties of the smallest eigenvalue function over a set of Hermitian matrices. We establish the local convergence of the algorithm under mild assumptions and deduce a precise rate of convergence result by viewing the algorithm as a fixed point iteration. the convergence analysis reveals that the algorithm is immune to the nonsmooth nature of the smallest eigenvalue. We illustrate the practical applicability of the algorithm on the pseudospectral functions.Publication Open Access Analysis of push-type epidemic data dissemination in fully connected networks(Elsevier, 2014) Sezer, Ali Devin; Department of Mathematics; Çağlar, Mine; Faculty Member; Department of Mathematics; College of Sciences; 105131Consider a fully connected network of nodes, some of which have a piece of data to be disseminated to the whole network. We analyze the following push-type epidemic algorithm: in each push round, every node that has the data, i.e., every infected node, randomly chooses c E Z. other nodes in the network and transmits, i.e., pushes, the data to them. We write this round as a random walk whose each step corresponds to a random selection of one of the infected nodes; this gives recursive formulas for the distribution and the moments of the number of newly infected nodes in a push round. We use the formula for the distribution to compute the expected number of rounds so that a given percentage of the network is infected and continue a numerical comparison of the push algorithm and the pull algorithm (where the susceptible nodes randomly choose peers) initiated in an earlier work. We then derive the fluid and diffusion limits of the random walk as the network size goes to infinity and deduce a number of properties of the push algorithm: (1) the number of newly infected nodes in a push round, and the number of random selections needed so that a given percent of the network is infected, are both asymptotically normal, (2) for large networks, starting with a nonzero proportion of infected nodes, a pull round infects slightly more nodes on average, (3) the number of rounds until a given proportion lambda of the network is infected converges to a constant for almost all lambda is an element of (0, 1). Numerical examples for theoretical results are provided.Publication Open Access Area minimizing surfaces in mean convex 3-manifolds(De Gruyter, 2015) Bourni, Theodora; Department of Mathematics; Coşkunüzer, Barış; Faculty Member; Department of Mathematics; College of SciencesIn this paper, we give several results on area minimizing surfaces in strictly mean convex 3-manifolds. First, we study the genus of absolutely area minimizing surfaces in a compact, orientable, strictly mean convex 3-manifold M bounded by a simple closed curve in partial derivative M. Our main result is that for any g >= 0, the space of simple closed curves in partial derivative M where all the absolutely area minimizing surfaces they bound in M has genus >= g is open and dense in the space A of nullhomologous simple closed curves in partial derivative M. For showing this we prove a bridge principle for absolutely area minimizing surfaces. Moreover, we show that for any g >= 0, there exists a curve gamma(g) in A such that the minimum genus of the absolutely area minimizing surfaces gamma(g) bounds is exactly g. As an application of these results, we further prove that the simple closed curves in partial derivative M bounding more than one minimal surface in M is an open and dense subset of A. We also show that there are disjoint simple closed curves in partial derivative M bounding minimal surfaces in M which are not disjoint. This allows us to answer a question of Meeks, by showing that for any strictly mean convex 3-manifold M, there exists a simple closed curve Gamma in partial derivative M which bounds a stable minimal surface which is not embedded. We also gave some applications of these results to the simple closed curves in R-3.Publication Open Access Averaged vs. quenched large deviations and entropy for random walk in a dynamic random environment(University of Washington Press, 2017) Rassoul-Agha, Firas; Seppalainen, Timo; Department of Mathematics; Yılmaz, Atilla; Faculty Member; Department of Mathematics; College of Sciences; 26605We consider random walk with bounded jumps on a hypercubic lattice of arbitrary dimension in a dynamic random environment. The environment is temporally independent and spatially translation invariant. We study the rate functions of the level-3 averaged and quenched large deviation principles from the point of view of the particle. In the averaged case the rate function is a specific relative entropy, while in the quenched case it is a Donsker-Varadhan type relative entropy for Markov processes. We relate these entropies to each other and seek to identify the minimizers of the level-3 to level-1 contractions in both settings. Motivation for this work comes from variational descriptions of the quenched free energy of directed polymer models where the same Markov process entropy appears.Publication Metadata only Big Heegner point Kolyvagin system for a family of modular forms(Springer International Publishing Ag, 2014) Department of Mathematics; Büyükboduk, Kazım; Faculty Member; Department of Mathematics; College of Sciences; N/AThe principal goal of this paper is to develop Kolyvagin's descent to apply with the big Heegner point Euler system constructed by Howard for the big Galois representation attached to a Hida family of elliptic modular forms. In order to achieve this, we interpolate and control the Tamagawa factors attached to each member of the family at bad primes, which should be of independent interest. Using this, we then work out the Kolyvagin descent on the big Heegner point Euler system so as to obtain a big Kolyvagin system that interpolates the collection of Kolyvagin systems obtained by Fouquet for each member of the family individually. This construction has standard applications to Iwasawa theory, which we record at the end.Publication Metadata only Cell-specific and post-hoc spatial clustering tests based on nearest neighbor contingency tables(Korean Statistical Soc, 2017) Department of Mathematics; Ceyhan, Elvan; Faculty Member; Department of Mathematics; College of Sciences; N/ASpatial clustering patterns in a multi-class setting such as segregation and association between classes have important implications in various fields, e.g., in ecology, and can be tested using nearest neighbor contingency tables (NNCTs). a NNCT is constructed based on the types of the nearest neighbor (NN) pairs and their frequencies. We survey the cell-specific (or pairwise) and overall segregation tests based on NNCTs in literature and introduce new ones and determine their asymptotic distributions. We demonstrate that cell-specific tests enjoy asymptotic normality, while overall tests have chi-square distributions asymptotically. Some of the overall tests are confounded by the unstable generalized inverse of the rank-deficient covariance matrix. To overcome this problem, we propose rank-based corrections for the overall tests to stabilize their behavior. We also perform an extensive' Monte Carlo simulation study to compare the finite sample performance of the tests in terms of empirical size and power based on the asymptotic and Monte Carlo critical values and determine the tests that have the best size and power performance and are robust to differences in relative abundances (of the classes). in addition to the cell-specific tests, we discuss one(-class)-versus-rest type of tests as post-hoc,tests after a significant overall test. We also introduce the concepts of total, strong, and partial segregatioN/Association to differentiate different levels of these patterns. We compare the new tests with the existing NNCT-tests in literature with simulations and illustrate the tests on an ecological data set. (C) 2016 the Korean Statistical Society. Published by Elsevier B.V. all rights reserved.Publication Open Access Classification of imbalanced data with a geometric digraph family(Journal of Machine Learning Research (JMLR), 2016) Department of Mathematics; Manukyan, Artur; Ceyhan, Elvan; PhD Student; Undergraduate Student; Faculty Member; Department of Mathematics; Graduate School of Sciences and Engineering; College of SciencesWe use a geometric digraph family called class cover catch digraphs (CCCDs) to tackle the class imbalance problem in statistical classification. CCCDs provide graph theoretic solutions to the class cover problem and have been employed in classification. We assess the classification performance of CCCD classifiers by extensive Monte Carlo simulations, comparing them with other classifiers commonly used in the literature. In particular, we show that CCCD classifiers perform relatively well when one class is more frequent than the other in a two-class setting, an example of the cl ass imbalance problem. We also point out the relationship between class imbalance and class overlapping problems, and their influence on the performance of CCCD classifiers and other classification methods as well as some state-of-the-art algorithms which are robust to class imbalance by construction. Experiments on both simulated and real data sets indicate that CCCD classifiers are robust to the class imbalance problem. CCCDs substantially undersample from the majority class while preserving the information on the discarded points during the undersampling process. Many state-of-the-art methods, however, keep this information by means of ensemble classifiers, but CCCDs yield only a single classifier with the same property, making it both appealing and fast.Publication Metadata only Comparison of relative density of two random geometric digraph families in testing spatial clustering(Springer, 2014) Department of Mathematics; Ceyhan, Elvan; Faculty Member; Department of Mathematics; College of Sciences; N/AWe compare the performance of relative densities of two parameterized random geometric digraph families called proximity catch digraphs (PCDs) in testing bivariate spatial patterns. These PCD families are proportional edge (PE) and central similarity (CS) PCDs and are defined with proximity regions based on relative positions of data points from two classes. The relative densities of these PCDs were previously used as statistics for testing segregation and association patterns against complete spatial randomness. The relative density of a digraph, D, with n vertices (i.e., with order n) represents the ratio of the number of arcs in D to the number of arcs in the complete symmetric digraph of the same order. When scaled properly, the relative density of a PCD is a U-statistic; hence, it has asymptotic normality by the standard central limit theory of U-statistics. The PE- and CS-PCDs are defined with an expansion parameter that determines the size or measure of the associated proximity regions. In this article, we extend the distribution of the relative density of CS-PCDs for expansion parameter being larger than one, and compare finite sample performance of the tests by Monte Carlo simulations and asymptotic performance by Pitman asymptotic efficiency. We find the optimal expansion parameters of the PCDs for testing each alternative in finite samples and in the limit as the sample size tending to infinity. As a result of our comparisons, we demonstrate that in terms of empirical power (i.e., for finite samples) relative density of CS-PCD has better performance (which occurs for expansion parameter values larger than one) for the segregation alternative, while relative density of PE-PCD has better performance for the association alternative. The methods are also illustrated in a real-life data set from plant ecology.Publication Open Access Computation of pseudospectral abscissa for large-scale nonlinear eigenvalue problems(Oxford University Press (OUP), 2017) Meerbergen, Karl; Michiels, Wim; Van Beeumen, Roel; Department of Mathematics; Mengi, Emre; Faculty Member; Department of Mathematics; College of Sciences; 113760We present an algorithm to compute the pseudospectral abscissa for a nonlinear eigenvalue problem. The algorithm relies on global under-estimator and over-estimator functions for the eigenvalue and singular value functions involved. These global models follow from eigenvalue perturbation theory. The algorithm has three particular features. First, it converges to the globally rightmost point of the pseudospectrum, and it is immune to nonsmoothness. The global convergence assertion is under the assumption that a global lower bound is available for the second derivative of a singular value function depending on one parameter. It may not be easy to deduce such a lower bound analytically, but assigning large negative values works robustly in practice. Second, it is applicable to large-scale problems since the dominant cost per iteration stems from computing the smallest singular value and associated singular vectors, for which efficient iterative solvers can be used. Furthermore, a significant increase in computational efficiency can be obtained by subspace acceleration, that is, by restricting the domains of the linear maps associated with the matrices involved to small but suitable subspaces, and solving the resulting reduced problems. Occasional restarts of these subspaces further enhance the efficiency for large-scale problems. Finally, in contrast to existing iterative approaches based on constructing low-rank perturbations and rightmost eigenvalue computations, the algorithm relies on computing only singular values of complex matrices. Hence, the algorithm does not require solutions of nonlinear eigenvalue problems, thereby further increasing efficiency and reliability. This work is accompanied by a robust implementation of the algorithm that is publicly available.