An Empirical Evaluation of Preconditioning Data for Accelerating Convex Hull Computations

The convex hull describes the extent or shape of a set of data and is used ubiquitously in computational geometry. Common algorithms to construct the convex hull on a finite set of n points (x,y) range from O(nlogn) time to O(n) time. However, it is often the case that a heuristic procedure is applied to reduce the original set of n points to a set of s < n points which contains the hull and so accelerates the final hull finding procedure. We present an algorithm to precondition data before building a 2D convex hull with integer coordinates, with three distinct advantages. First, for all practical purposes, it is linear; second, no explicit sorting of data is required and third, the reduced set of s points is constructed such that it forms an ordered set that can be directly pipelined into an O(n) time convex hull algorithm. Under these criteria a fast (or O(n)) pre-conditioner in principle creates a fast convex hull (approximately O(n)) for an arbitrary set of points. The paper empirically evaluates and quantifies the acceleration generated by the method against the most common convex hull algorithms. An extra acceleration of at least four times when compared to previous existing preconditioning methods is found from experiments on a dataset.

An Empirical Evaluation of Preconditioning Data for Accelerating Convex Hull Computations

The convex hull describes the extent or shape of a set of data and is used ubiquitously in computational geometry. Common algorithms to construct the convex hull on a finite set of n points (x,y) range from O(nlogn) time to O(n) time. However, it is often the case that a heuristic procedure is applied to reduce the original set of n points to a set of s < n points which contains the hull and so accelerates the final hull finding procedure. We present an algorithm to precondition data before building a 2D convex hull with integer coordinates, with three distinct advantages. First, for all practical purposes, it is linear; second, no explicit sorting of data is required and third, the reduced set of s points is constructed such that it forms an ordered set that can be directly pipelined into an O(n) time convex hull algorithm. Under these criteria a fast (or O(n)) pre-conditioner in principle creates a fast convex hull (approximately O(n)) for an arbitrary set of points. The paper empirically evaluates and quantifies the acceleration generated by the method against the most common convex hull algorithms. An extra acceleration of at least four times when compared to previous existing preconditioning methods is found from experiments on a dataset.

Joint Information and Jamming Beamforming for Secrecy Rate Maximization in Cognitive Radio Networks

In this paper, we consider the secure beamforming design for an underlay cognitive radio multiple-input singleoutput broadcast channel in the presence of multiple passive eavesdroppers. Our goal is to design a jamming noise (JN) transmit strategy to maximize the secrecy rate of the secondary system. By utilizing the zero-forcing method to eliminate the interference caused by JN to the secondary user, we study the joint optimization of the information and JN beamforming for secrecy rate maximization of the secondary system while satisfying all the interference power constraints at the primary users, as well as the per-antenna power constraint at the secondary transmitter. For an optimal beamforming design, the original problem is a nonconvex program, which can be reformulated as a convex program by applying the rank relaxation method. To this end, we prove that the rank relaxation is tight and propose a barrier interior-point method to solve the resulting saddle point problem based on a duality result. To find the global optimal solution, we transform the considered problem into an unconstrained optimization problem. We then employ Broyden-Fletcher-Goldfarb-Shanno (BFGS) method to solve the resulting unconstrained problem which helps reduce the complexity significantly, compared to conventional methods. Simulation results show the fast convergence of the proposed algorithm and substantial performance improvements over existing approaches.

Data-Adaptive Modeling using Convex Regression

Thesis (Ph.D.)--University of Washington, 2016-08

Convex Optimization Algorithms and Statistical Bounds for Learning Structured Models

Thesis (Ph.D.)--University of Washington, 2016-08

T-duality without isometry via extended gauge symmetries of 2D sigma models

Target space duality is one of the most profound properties of string theory. However it customarily requires that the background fields satisfy certain invariance conditions in order to perform it consistently; for instance the vector fields along the directions that T-duality is performed have to generate isometries. In the present paper we examine in detail the possibility to perform T-duality along non-isometric directions. In particular, based on a recent work of Kotov and Strobl, we study gauged 2D sigma models where gauge invariance for an extended set of gauge transformations imposes weaker constraints than in the standard case, notably the corresponding vector fields are not Killing. This formulation enables us to follow a procedure analogous to the derivation of the Buscher rules and obtain two dual models, by integrating out once the Lagrange multipliers and once the gauge fields. We show that this construction indeed works in non-trivial cases by examining an explicit class of examples based on step 2 nilmanifolds.

Asymptotic scattering and duality in the one-dimensional three-state quantum Potts model on a lattice

We determine numerically the single-particle and the two-particle spectrum of the three-state quantum Potts model on a lattice by using the density matrix renormalization group method, and extract information on the asymptotic (small momentum) S-matrix of the quasiparticles. The low energy part of the finite size spectrum can be understood in terms of a simple effective model introduced in a previous work, and is consistent with an asymptotic S-matrix of an exchange form below a momentum scale p*. This scale appears to vanish faster than the Compton scale, mc, as one approaches the critical point, suggesting that a dangerously irrelevant operator may be responsible for the behaviour observed on the lattice.

On the Set of Locally Convex Topologies Compatible with a Given Topology on a Vector Space: Cardinality Aspects

For a topological vector space (X, τ ), we consider the family LCT (X, τ ) of all locally convex topologies defined on X, which give rise to the same continuous linear functionals as the original topology τ . We prove that for an infinite-dimensional reflexive Banach space (X, τ ), the cardinality of LCT (X, τ ) is at least c.

Mackey topology on locally convex spaces and on locally quasi-convex groups. Similarities and historical remarks

A counterpart of the Mackey–Arens Theorem for the class of locally quasi-convex topological Abelian groups (LQC-groups) was initiated in Chasco et al. (Stud Math 132(3):257–284, 1999). Several authors have been interested in the problems posed there and have done clarifying contributions, although the main question of that source remains open. Some differences between the Mackey Theory for locally convex spaces and for locally quasi-convex groups, stem from the following fact: The supremum of all compatible locally quasi-convex topologies for a topological abelian group G may not coincide with the topology of uniform convergence on the weak quasi-convex compact subsets of the dual groupG∧. Thus, a substantial part of the classical Mackey–Arens Theorem cannot be generalized to LQC-groups. Furthermore, the mentioned fact gives rise to a grading in the property of “being a Mackey group”, as defined and thoroughly studied in Díaz Nieto and Martín-Peinador (Proceedings in Mathematics and Statistics 80:119–144, 2014). At present it is not known—and this is the main open question—if the supremum of all the compatible locally quasi-convex topologies on a topological group is in fact a compatible topology. In the present paper we do a sort of historical review on the Mackey Theory, and we compare it in the two settings of locally convex spaces and of locally quasi-convex groups. We point out some general questions which are still open, under the name of Problems.

Corrigendum to “The envelope theorem for multiobjective convex programming via contingent derivatives” [J. Math. Anal. Appl. 372 (1) (2010) 197–207]

The aim of this note is to formulate an envelope theorem for vector convex programs. This version corrects an earlier work, “The envelope theorem for multiobjective convex programming via contingent derivatives” by Jiménez Guerra et al. (2010) [3]. We first propose a necessary and sufficient condition allowing to restate the main result proved in the alluded paper. Second, we introduce a new Lagrange multiplier in order to obtain an envelope theorem avoiding the aforementioned error.

Sensitivity Analysis in Convex Optimization through the Circatangent Derivative

The main goal of this paper is to analyse the sensitivity of a vector convex optimization problem according to variations in the right-hand side. We measure the quantitative behavior of a certain set of Pareto optimal points characterized to become minimum when the objective function is composed with a positive function. Its behavior is analysed quantitatively using the circatangent derivative for set-valued maps. Particularly, it is shown that the sensitivity is closely related to a Lagrange multiplier solution of a dual program.

D. H. Lawrence’s Principles of Duality in “Fanny and Annie”

The present article aims at presenting a reading of D. H. Lawrence’s “Fanny and Annie”, considering a general outlook of Lawrence’s sexology and his principles of duality as they emerge from his fiction and critical studies.

Foil rolling : a new interpretation of experimental results

This paper explores a new interpretation of experiments on foil rolling. The assumption that the roll remains convex is relaxed so that the strip profile may become concave, or thicken in the roll gap. However, we conjecture that the concave profile is associated with phenomena which occur after the rolls have stopped. We argue that the yield criterion must be satisfied in a nonconventional manner if such a phenomenon is caused plastically. Finite element analysis on an extrusion problem appears to confirm this conjecture.

Lateral bone density variations in the scoliotic spine

Adolescent Idiopathic Scoliosis (AIS) is the most common deformity of the spine, affecting 2-4% of the population. Previous studies have shown that the vertebrae in scoliotic spines undergo abnormal shape changes, however there has been little exploration of how AIS affects bone density distribution within the vertebrae. Existing pre-operative CT scans of 53 female idiopathic scoliosis patients with right-sided main thoracic curves were used to measure the lateral (right to left) bone density profile at mid-height through each vertebral body. This study demonstrated that AIS patients have a marked convex/concave asymmetry in bone density for vertebral levels at or near the apex of the scoliotic curve. To the best of our knowledge, the only previous studies of bone density distribution in AIS are those of Périé et al [1,2], who reported a coronal plane ‘mechanical migration’ of 0.54mm toward the concavity of the scoliotic curve in the lumbar apical vertebrae of 11 scoliosis patients. This is comparable to the value of 0.8mm (4%) in our study, especially since our patients had more severe scoliotic curves. From a bone adaptation perspective, these results suggest that the axial loading on the scoliotic spine is strongly asymmetric.