Output-Sensitive Construction of Reeb Graphs

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. This paper describes a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds or non-manifolds in any dimension. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Critical points correspond to nodes in the Reeb graph. Arcs connecting the nodes are computed in the second step by a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The paper also describes a scheme for controlled simplification of the Reeb graph and two different graph layout schemes that help in the effective presentation of Reeb graphs for visual analysis of scalar fields. Finally, the Reeb graph is employed in four different applications-surface segmentation, spatially-aware transfer function design, visualization of interval volumes, and interactive exploration of time-varying data.

Relay Precoder Optimization in MIMO-Relay Networks With Imperfect CSI

In this paper, we consider robust joint designs of relay precoder and destination receive filters in a nonregenerative multiple-input multiple-output (MIMO) relay network. The network consists of multiple source-destination node pairs assisted by a MIMO-relay node. The channel state information (CSI) available at the relay node is assumed to be imperfect. We consider robust designs for two models of CSI error. The first model is a stochastic error (SE) model, where the probability distribution of the CSI error is Gaussian. This model is applicable when the imperfect CSI is mainly due to errors in channel estimation. For this model, we propose robust minimum sum mean square error (SMSE), MSE-balancing, and relay transmit power minimizing precoder designs. The next model for the CSI error is a norm-bounded error (NBE) model, where the CSI error can be specified by an uncertainty set. This model is applicable when the CSI error is dominated by quantization errors. In this case, we adopt a worst-case design approach. For this model, we propose a robust precoder design that minimizes total relay transmit power under constraints on MSEs at the destination nodes. We show that the proposed robust design problems can be reformulated as convex optimization problems that can be solved efficiently using interior-point methods. We demonstrate the robust performance of the proposed design through simulations.

Polynomial Approximation, Local Polynomial convexity, and Degenerate CR Singularities- II

We provide some conditions for the graph of a Holder-continuous function on (D) over bar, where (D) over bar is a closed disk in C, to be polynomially convex. Almost all sufficient conditions known to date - provided the function (say F) is smooth - arise from versions of the Weierstrass Approximation Theorem on (D) over bar. These conditions often fail to yield any conclusion if rank(R)DF is not maximal on a sufficiently large subset of (D) over bar. We bypass this difficulty by introducing a technique that relies on the interplay of certain plurisubharmonic functions. This technique also allows us to make some observations on the polynomial hull of a graph in C(2) at an isolated complex tangency.

An (O)over-bar(m(2)n) randomized algorithm to compute a minimum cycle basis of a directed graph

We consider the problem of computing a minimum cycle basis in a directed graph G. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {- 1, 0, 1} incidence vector is associated with each cycle and the vector space over Q generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of weights of the cycles is minimum is called a minimum cycle basis of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m arcs and n vertices runs in O(m(w+1)n) time (where w < 2.376 is the exponent of matrix multiplication). If one allows randomization, then an (O) over tilde (m(3)n) algorithm is known for this problem. In this paper we present a simple (O) over tilde (m(2)n) randomized algorithm for this problem. The problem of computing a minimum cycle basis in an undirected graph has been well-studied. In this problem a {0, 1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in O(m(2)n + mn(2) logn) time and our randomized algorithm for directed graphs almost matches this running time.

Some Aspects of the Kobayashi and Carath,odory Metrics on Pseudoconvex Domains

The purpose of this article is to consider two themes, both of which emanate from and involve the Kobayashi and the Carath,odory metric. First, we study the biholomorphic invariant introduced by B. Fridman on strongly pseudoconvex domains, on weakly pseudoconvex domains of finite type in C (2), and on convex finite type domains in C (n) using the scaling method. Applications include an alternate proof of the Wong-Rosay theorem, a characterization of analytic polyhedra with noncompact automorphism group when the orbit accumulates at a singular boundary point, and a description of the Kobayashi balls on weakly pseudoconvex domains of finite type in C (2) and convex finite type domains in C (n) in terms of Euclidean parameters. Second, a version of Vitushkin's theorem about the uniform extendability of a compact subgroup of automorphisms of a real analytic strongly pseudoconvex domain is proved for C (1)-isometries of the Kobayashi and Carath,odory metrics on a smoothly bounded strongly pseudoconvex domain.

On concave univalent functions

We consider functions that map the open unit disc conformally onto the complement of an unbounded convex set with opening angle pa, a ? (1, 2], at infinity. In this paper, we show that every such function is close-to-convex of order (a - 1) and is included in the set of univalent functions of bounded boundary rotation. Many interesting consequences of this result are obtained. We also determine the extreme points of the set of concave functions with respect to the linear structure of the Hornich space.

GINZBURG-LANDAU LIKE THEORY OF HIGH TEMPERATURE SUPERCONDUCTIVITY IN THE CUPRATES: EMERGENT d-WAVE ORDER

High temperature superconductivity in the cuprates remains one of the most widely investigated, constantly surprising and poorly understood phenomena in physics. Here, we describe briefly a new phenomenological theory inspired by the celebrated description of superconductivity due to Ginzburg and Landau and believed to describe its essence. This posits a free energy functional for the superconductor in terms of a complex order parameter characterizing it. We propose that there is, for superconducting cuprates, a similar functional of the complex, in plane, nearest neighbor spin singlet bond (or Cooper) pair amplitude psi(ij). Further, we suggest that a crucial part of it is a (short range) positive interaction between nearest neighbor bond pairs, of strength J'. Such an interaction leads to nonzero long wavelength phase stiffness or superconductive long range order, with the observed d-wave symmetry, below a temperature T-c similar to zJ' where z is the number of nearest neighbors; d-wave superconductivity is thus an emergent, collective consequence. Using the functional, we calculate a large range of properties, e. g., the pseudogap transition temperature T* as a function of hole doping x, the transition curve T-c(x), the superfluid stiffness rho(s)(x, T), the specific heat (without and with a magnetic field) due to the fluctuating pair degrees of freedom and the zero temperature vortex structure. We find remarkable agreement with experiment. We also calculate the self-energy of electrons hopping on the square cuprate lattice and coupled to electrons of nearly opposite momenta via inevitable long wavelength Cooper pair fluctuations formed of these electrons. The ensuing results for electron spectral density are successfully compared with recent experimental results for angle resolved photo emission spectroscopy (ARPES), and comprehensively explain strange features such as temperature dependent Fermi arcs above T-c and the ``bending'' of the superconducting gap below T-c.

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m(3/2)) time. For sparse graphs (m/n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(n(5/2)) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Omega(n(2)2 root(2lgn)) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Theta (n(2) log n) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

The local polynomial hull near a degenerate CR singularity: Bishop discs revisited

Let be a smooth real surface in and let be a point at which the tangent plane is a complex line. How does one determine whether or not is locally polynomially convex at such a p-i.e. at a CR singularity? Even when the order of contact of with at p equals 2, no clean characterisation exists; difficulties are posed by parabolic points. Hence, we study non-parabolic CR singularities. We show that the presence or absence of Bishop discs around certain non-parabolic CR singularities is completely determined by a Maslov-type index. This result subsumes all known facts about Bishop discs around order-two, non-parabolic CR singularities. Sufficient conditions for Bishop discs have earlier been investigated at CR singularities having high order of contact with . These results relied upon a subharmonicity condition, which fails in many simple cases. Hence, we look beyond potential theory and refine certain ideas going back to Bishop.

Efficient Methods for Robust Classification Under Uncertainty in Kernel Matrices

In this paper we study the problem of designing SVM classifiers when the kernel matrix, K, is affected by uncertainty. Specifically K is modeled as a positive affine combination of given positive semi definite kernels, with the coefficients ranging in a norm-bounded uncertainty set. We treat the problem using the Robust Optimization methodology. This reduces the uncertain SVM problem into a deterministic conic quadratic problem which can be solved in principle by a polynomial time Interior Point (IP) algorithm. However, for large-scale classification problems, IP methods become intractable and one has to resort to first-order gradient type methods. The strategy we use here is to reformulate the robust counterpart of the uncertain SVM problem as a saddle point problem and employ a special gradient scheme which works directly on the convex-concave saddle function. The algorithm is a simplified version of a general scheme due to Juditski and Nemirovski (2011). It achieves an O(1/T-2) reduction of the initial error after T iterations. A comprehensive empirical study on both synthetic data and real-world protein structure data sets show that the proposed formulations achieve the desired robustness, and the saddle point based algorithm outperforms the IP method significantly.

Identification of Active Sources in Single-Channel Convolutive Mixtures Using Known Source Models

We address the problem of identifying the constituent sources in a single-sensor mixture signal consisting of contributions from multiple simultaneously active sources. We propose a generic framework for mixture signal analysis based on a latent variable approach. The basic idea of the approach is to detect known sources represented as stochastic models, in a single-channel mixture signal without performing signal separation. A given mixture signal is modeled as a convex combination of known source models and the weights of the models are estimated using the mixture signal. We show experimentally that these weights indicate the presence/absence of the respective sources. The performance of the proposed approach is illustrated through mixture speech data in a reverberant enclosure. For the task of identifying the constituent speakers using data from a single microphone, the proposed approach is able to identify the dominant source with up to 8 simultaneously active background sources in a room with RT60 = 250 ms, using models obtained from clean speech data for a Source to Interference Ratio (SIR) greater than 2 dB.

On the Erdos-Szekeres n-interior point problem

The n-interior point variant of the Erdos-Szekeres problem is to show the following: For any n, n-1, every point set in the plane with sufficient number of interior points contains a convex polygon containing exactly n-interior points. This has been proved only for n-3. In this paper, we prove it for pointsets having atmost logarithmic number of convex layers. We also show that any pointset containing atleast n interior points, there exists a 2-convex polygon that contains exactly n-interior points.

Loop transformations: convexity, pruning, and optimization

High-level loop transformations are a key instrument in mapping computational kernels to effectively exploit the resources in modern processor architectures. Nevertheless, selecting required compositions of loop transformations to achieve this remains a significantly challenging task; current compilers may be off by orders of magnitude in performance compared to hand-optimized programs. To address this fundamental challenge, we first present a convex characterization of all distinct, semantics-preserving, multidimensional affine transformations. We then bring together algebraic, algorithmic, and performance analysis results to design a tractable optimization algorithm over this highly expressive space. Our framework has been implemented and validated experimentally on a representative set of benchmarks running on state-of-the-art multi-core platforms.

A sequential dual method for structural SVMs

In many real world prediction problems the output is a structured object like a sequence or a tree or a graph. Such problems range from natural language processing to compu- tational biology or computer vision and have been tackled using algorithms, referred to as structured output learning algorithms. We consider the problem of structured classifi- cation. In the last few years, large margin classifiers like sup-port vector machines (SVMs) have shown much promise for structured output learning. The related optimization prob -lem is a convex quadratic program (QP) with a large num-ber of constraints, which makes the problem intractable for large data sets. This paper proposes a fast sequential dual method (SDM) for structural SVMs. The method makes re-peated passes over the training set and optimizes the dual variables associated with one example at a time. The use of additional heuristics makes the proposed method more efficient. We present an extensive empirical evaluation of the proposed method on several sequence learning problems.Our experiments on large data sets demonstrate that the proposed method is an order of magnitude faster than state of the art methods like cutting-plane method and stochastic gradient descent method (SGD). Further, SDM reaches steady state generalization performance faster than the SGD method. The proposed SDM is thus a useful alternative for large scale structured output learning.

A constant factor approximation algorithm for boxicity of circular arc graphs

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional axis parallel boxes in Rk. Equivalently, it is the minimum number of interval graphs on the vertex set V such that the intersection of their edge sets is E. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below O(n0.5-ε)-factor, for any ε > 0 in polynomial time unless NP = ZPP. Till date, there is no well known graph class of unbounded boxicity for which even an nε-factor approximation algorithm for computing boxicity is known, for any ε < 1. In this paper, we study the boxicity problem on Circular Arc graphs - intersection graphs of arcs of a circle. We give a (2+ 1/k)-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where k ≥ 1 is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is O(mn+n2) in both these cases and in O(mn+kn2) which is at most O(n3) time we also get their corresponding box representations, where n is the number of vertices of the graph and m is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time.