Adaptive temporal compressive sensing for video

This paper introduces the concept of adaptive temporal compressive sensing (CS) for video. We propose a CS algorithm to adapt the compression ratio based on the scene's temporal complexity, computed from the compressed data, without compromising the quality of the reconstructed video. The temporal adaptivity is manifested by manipulating the integration time of the camera, opening the possibility to realtime implementation. The proposed algorithm is a generalized temporal CS approach that can be incorporated with a diverse set of existing hardware systems. © 2013 IEEE.

Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

Phase Locked Loop and Modulo Games, The Dogma Loops; and “Finding Ibrida”

This dissertation consists of two independent musical compositions and an article detailing the process of the design and assembly of an electric guitar with particular emphasis on the carefully curated suite of embedded effects.

The first piece, 'Phase Locked Loop and Modulo Games' is scored for electric guitar and a single echo of equal volume less than a beat away. One could think of the piece as a 15 minute canon at the unison at the dotted eighth note (or at times the quarter or triplet-quarter), however the compositional motivation is more about weaving a composite texture between the guitar and its echo that is, while in theory extremely contrapuntal, in actuality is simply a single [superhuman] melodic line.

The second piece, 'The Dogma Loops' picks up a few compositional threads left by ‘Phase Locked Loop’ and weaves them into an entirely new tapestry. 'Phase Locked Loop' is motivated by the creation of a complex musical composite that is for the most part electronically transparent. 'The Dogma Loops' questions that same notion of composite electronic complexity by essentially asking a question: "what are the inputs to an interactive electronic system that create the most complex outputs via the simplest musical means possible?"

'The Dogma Loops' is scored for Electric Guitar (doubling on Ukulele), Violin and Violoncello. All of the principal instruments require an electronic pickup (except the Uke). The work is in three sections played attacca; [Automation Games], [Point of Origin] and [Cloning Vectors].

The third and final component of the document is the article 'Finding Ibrida.' This article details the process of the design and assembly of an electric guitar with integrated effects, while also providing the deeper context (conceptual and technical) which motivated the efforts and informed the challenges to hybridize the various technologies (tubes, transistors, digital effects and a microcontroller subsystem). The project was motivated by a desire for rigorous technical and hands-on engagement with analog signal processing as applied to the electric guitar. ‘Finding Ibrida’ explores sound, some myths and lore of guitar tech and the history of electric guitar distortion and its culture of sonic exploration.