29 research outputs found
Decremental (1+ε)-Approximate Maximum Eigenvector: Dynamic Power Method
Full text linkWe present a dynamic algorithm for maintaining (1+ε)-approximate maximum eigenvector and eigenvalue of a positive semi-definite matrix A undergoing decreasing updates, i.e., updates which may only decrease eigenvalues. Given a vector v updating A ← A-vv^⊤, our algorithm takes Õ(nnz(v)) amortized update time, i.e., polylogarithmic per non-zeros in the update vector.
Our technique is based on a novel analysis of the influential power method in the dynamic setting. The two previous sets of techniques have the following drawbacks (1) algebraic techniques can maintain exact solutions but their update time is at least polynomial per non-zeros, and (2) sketching techniques admit polylogarithmic update time but suffer from a crude additive approximation.
Our algorithm exploits an oblivious adversary. Interestingly, we show that any algorithm with polylogarithmic update time per non-zeros that works against an adaptive adversary and satisfies an additional natural property would imply a breakthrough for checking psd-ness of matrices in Õ(n²) time, instead of O(n^ω) time
Acceleration Meets Inverse Maintenance: Faster _∞-Regression
Full text linkWe propose a randomized multiplicative weight update (MWU) algorithm for _{∞} regression that runs in Õ(n^{2+1/22.5} poly(1/ε)) time when ω = 2+o(1), improving upon the previous best Õ(n^{2+1/18} polylog(1/ε)) runtime in the low-accuracy regime. Our algorithm combines state-of-the-art inverse maintenance data structures with acceleration. In order to do so, we propose a novel acceleration scheme for MWU that exhibits stability and robustness, which are required for the efficient implementations of the inverse maintenance data structures.
We also design a faster deterministic MWU algorithm that runs in Õ(n^{2+1/12}poly(1/ε)) time when ω = 2+o(1), improving upon the previous best Õ(n^{2+1/6} poly log(1/ε)) runtime in the low-accuracy regime. We achieve this by showing a novel stability result that goes beyond previously known works based on interior point methods (IPMs).
Our work is the first to use acceleration and inverse maintenance together efficiently, finally making the two most important building blocks of modern structured convex optimization compatible
Almost-linear-time weighted ℓp-norm solvers in slightly dense graphs via sparsification
Full text linkISSN:1868-896
Fast Algorithms for -Regression and Other Problems
No full textRegression in -norm is a canonical problem in optimization, machine learning and theoretical computer science which asks for a vector with minimum -norm in a linear subspace. In this thesis, we give fast, high-accuracy algorithms for regression for all . Our algorithms are built on novel techniques including {\it iterative refinement for -norms}, and a fast {\it width-reduced} multiplicative weight update routine among others. Furthermore, via a new {\it inverse maintenance} scheme, we can solve -regression almost as fast as linear regression for all . For graph instances, where the goal is to optimize -norm objectives (flow or voltages), our algorithms incorporate sparsification routines that preserve such objectives, to obtain {\it near-linear-time} algorithms. As a consequence, we also obtain a fast algorithm for the maximum flow problem in unweighted graphs.
A popular approach to fast algorithms for -regression in practice is via empirical modifications of the {Iteratively Reweighted Least Squares (IRLS)} algorithm since the basic version of IRLS is known to converge only for and diverge even for moderate (e.g., ). We give the first IRLS algorithm that provably converges to a high accuracy solution in a few iterations. Our algorithm has shown exemplary practical performance as well beating standard MATLAB CVX implementations by 10-50x.
We further extend our techniques to obtain fast algorithms for {\it Quasi-self-concordant (QSC)} functions, which includes -regression, softmax regression, and logistic regression among others. We show how iterative refinement and width reduction techniques extend and give fast rates of convergence for all QSC functions.Ph.D
Decremental -Approximate Maximum Eigenvector: Dynamic Power Method
Full text linkWe present a dynamic algorithm for maintaining -approximate
maximum eigenvector and eigenvalue of a positive semi-definite matrix
undergoing \emph{decreasing} updates, i.e., updates which may only decrease
eigenvalues. Given a vector updating , our algorithm
takes amortized update time, i.e., polylogarithmic
per non-zeros in the update vector.
Our technique is based on a novel analysis of the influential power method in
the dynamic setting. The two previous sets of techniques have the following
drawbacks (1) algebraic techniques can maintain exact solutions but their
update time is at least polynomial per non-zeros, and (2) sketching techniques
admit polylogarithmic update time but suffer from a crude additive
approximation.
Our algorithm exploits an oblivious adversary. Interestingly, we show that
any algorithm with polylogarithmic update time per non-zeros that works against
an adaptive adversary and satisfies an additional natural property would imply
a breakthrough for checking psd-ness of matrices in time,
instead of time.Comment: 35 Page
Link Weight Tolerance: A study of betweenness centrality and data transmission in complex networks
No full textLinks play a significant role in the functioning of a complex network. The aim of this thesis is to study the links in a weighted network by introducing two new concepts. The link betweenness centrality of a link is defined as the fraction of shortest paths between all pairs of nodes in a graph that traverses that link. Although link betweenness is a widely known measure that characterizes the link, we introduce the concept, link weight tolerance, to understand the extent to which the weight of the link can be increased or decreased such that the shortest paths in the graph are unaffected, therefore the link betweenness of the links remain the same. We develop a method to generate the positive and negative tolerance of a link. We use examples to illustrate the algorithm and discuss the results. Prior to introducing this concept, in addition to surveying existing network theory measures, we also analyse the metric, betweenness centrality and describe the methods used to generate weighted and unweighted random graphs. To extend the concept of link betweenness, we introduce the second concept, link tension. Link tension provides the information related to the ability of the link to handle transmission of data and shows us the links that are important in a network.Electrical Engineering | Embedded System
Inculcating a sense of stewardship and responsibility towards urban trees amongst citizens: Using i-tree technology as a means to facilitate active participation of local communities in urban forestry
No full textCities are in an urgent need to adapt to the impacts of climate change, particularly, high temperatures and heat stress. Urban Forests are the most effective means of climate adaptation. However, the multiple benefits of urban trees are highly undervalued in the urban contexts. This project focuses on positioning urban trees as effective agents in improving the overall liveability of cities. The premise of the project lies in the fuzzy front end of the innovation process where the i-Tree technology is being redeveloped for its effective adoption in Netherlands. The goal of the project is to synchronize the technical potential of i-Tree as a tool and communicate the benefits of trees to multiple stakeholders in the process.The overall design direction aims to address these problems through a series of interventions across the system of urban forestry. The concept introduces a public awareness campaign to bridge the knowledge gap between citizens and other stakeholders. The campaign is proposed to stretch over a duration of 10-11 months with several touchpoints along the way for citizens to get enthusiastic about the idea of maintaining and taking care of urban trees. The touchpoints aim to target events like Dutch Design week, Boomfeestdag (Tree Festival) and Springsnow festival. To make the awareness program desirable and interesting. A podcast series and a guide is developed called “How to befriend a Tree?”. A concept for the i-Tree Eco tool is proposed which communicates tree benefits in a way that is comprehensible by all the citizens. All the touch points lead the audience of the campaign to the digital platform of i-Tree Netherlands which helps people become caretakers of trees easily.Strategic Product Desig
Numerical Modelling of Power Transformers under Geomagnetically Induced Currents
No full textModelling of power transformers to predict and examine its performance in the presence of Geomagnetic Induced Currents (GICs) is of particular interest in research since these currents that are quasi-DC in nature drive the transformer into half-cycle saturation. During the half-cycle saturation, the increased leakage flux and harmonics have undesirable effects on the windings and the structural components of the transformer, which can possibly lead to their permanent damage. This prompts the need to perform a precautionary study of the transformer validating its robustness when subject to GICs. This thesis proposes a method to model the transformer and its electromagnetic (EM) behaviour under GICs that combines the accuracy of Finite Element Modelling (FEM) with the speed of Magnetic Equivalent Modelling (MEM) to produce a fast-computing yet detailed modelling method using simulation tools, COMSOL and MATLAB Simulink, respectively. The transformer under study in this thesis is a single-phase 280MVA, 500/230kV auto transformer designed by Royal Smit Transformers. It was first modelled using FEM in COMSOL, providing details of the equivalent 2D axisymmetric geometry of the core and the windings and the material properties to each component. The model was then computed and validated against factory measurements done by Royal SMIT for the transformer when not subjected to GICs. After which, the model was run for the condition in which the transformer is subject to a GIC. The main problem of failure of the model to converge before reaching steady-state condition under GIC was overcome after optimizing the solver settings of the FEM software. The difference in the EM behaviour of the transformer with and without GIC were studied. After ensuring that the FEM model was robust and accurately represents the transformer under GIC as well, the time-consuming part of computing the FEM model till it reached steady-state under GIC was then made to be taken care of by a MEM model developed in Simulink. Induced flux versus magnetizing current characteristics of the transformer were obtained from the FEM model, and fed to the MEM model, which only took a few seconds to run. The magnetizing current waveform obtained for a few cycles after reaching steady-state under GIC was then transferred to the FEM model, which could finally compute - for those values of magnetizing current - the detailed EM effects of GICs on the transformer, spatially. An important EM study needing the spatial distribution of the EM properties within the transformer is the calculation of eddy current losses in the windings. In this thesis, a method that only considers the envelope of the set of windings as opposed to modelling every strand to calculate their losses is developed using an analytical formula found in literature. This is validated against the losses calculated by Royal SMIT as well as the FEM software for a detailed model of the windings. The timesaving method to study the EM behaviour of transformers subject to GIC proposed in this thesis accurately models the transformer in the saturation region that should enable conducting EM studies furthermore to winding loss calculation with ease.Electrical Engineering | Electrical Power Engineerin
Artistic rendering in computer graphics
No full textArtistic Rendering in Computer Graphics is an advancing area under image processing domain. It is used to generate artistic images from photographs. Artistic Rendering is also called Non-Photorealistic Rendering (NPR) because it produces images which are more art based and not true to life, possessing no resemblance to photographs which are true to life. NPR finds applications in many areas such as painterly rendering of images, designing games graphics, cartoon animation, oil paintings, and colored pencil drawings. As part of the project, the author designed and developed a software called as “PhotoMagine” which takes an image as input, applies various artistic effects to it and outputs the images produced as a result of adding each of the effects. The software was designed to exhibit an interactive and user friendly Graphical User Interface with important functionalities such as history box to keep track of the algorithms applied by the user over a particular image. The author further contributed to the project by implementing and incorporating important functionalities such undo and redo effects to enable user to be able to undo/redo a particular effect at any time. The amount of time taken by various effects to apply to the input image was also computed as part of the software and displayed on the interface. The algorithms related to artistic rendering were therefore studied by the author and included as part of the software to carry out several experiments. The detailed description of the phases in the software development life cycle, ranging from requirements analysis, designing of the graphical user interface, implementation and testing of algorithms is described as part of the report.Bachelor of Engineering (Computer Engineering
