Technical Reports

## 2008 UBC CS Technical Report Abstracts

TR-2008-01 Probing the Pareto frontier for basis pursuit solutions, January 28, 2008 Ewout van den Berg and Michael P. Friedlander, 23 pages

The basis pursuit problem seeks a minimum one-norm solution of an underdetermined least-squares problem. Basis pursuit denoise (BPDN) fits the least-squares problem only approximately, and a single parameter determines a curve that traces the optimal trade-off between the least-squares fit and the one-norm of the solution. We prove that this curve is convex and continuously differentiable over all points of interest, and show that it gives an explicit relationship to two other optimization problems closely related to BPDN. We describe a root-finding algorithm for finding arbitrary points on this curve; the algorithm is suitable for problems that are large scale and for those that are in the complex domain. At each iteration, a spectral gradient-projection method approximately minimizes a least-squares problem with an explicit one-norm constraint. Only matrix-vector operations are required. The primal-dual solution of this problem gives function and derivative information needed for the root-finding method. Numerical experiments on a comprehensive set of test problems demonstrate that the method scales well to large problems.

TR-2008-02 Fast Marching Methods for Stationary Hamilton-Jacobi Equations with Axis-Aligned Anisotropy, August 08, 2008 Ken Alton and Ian M. Mitchell, 33 pages

The Fast Marching Method (FMM) has proved to be a very efficient algorithm for solving the isotropic Eikonal equation. Because it is a minor modification of Dijkstra's algorithm for finding the shortest path through a discrete graph, FMM is also easy to implement. In this paper we describe a new class of Hamilton-Jacobi (HJ) PDEs with axis-aligned anisotropy which satisfy a causality condition for standard finite difference schemes on orthogonal grids and can hence be solved using the FMM; the only modification required to the algorithm is in the local update equation for a node. This class of HJ PDEs has applications in anelliptic wave propagation and robotic path planning, and brief examples are included. Since our class of HJ PDEs and grids permit asymmetries, we also examine some methods of improving the efficiency of the local update that do not require symmetric grids and PDEs. Finally, we include explicit update formulas for variations of the Eikonal equation that use the Manhattan, Euclidean and infinity norms on orthogonal grids of arbitrary dimension and with variable node spacing.

TR-2008-03 Computation with Energy-Time Trade-Offs: Models, Algorithms and Lower-Bounds, April 10, 2008 Bradley D. Bingham and Mark R. Greenstreet, 11 pages

Power consumption has become one of the most critical concerns for processor design. This motivates designing algorithms for minimum execution time subject to energy constraints. We propose simple models for analysing algorithms that reflect the energy-time trade-offs of CMOS circuits. Using these models, we derive lower bounds for the energy-constrained execution time of sorting, addition and multiplication, and we present algorithms that meet these bounds. We show that minimizing time under energy constraints is not the same as minimizing operation count or computation depth.

TR-2008-04 Supporting Transitions in Work: Informing Groupware Design by Understanding Whiteboard Use, April 24, 2008 Anthony Tang, Joel Lanir, Saul Greenberg and S. Sidney Fels, 10 pages

Many groupware tools focus on supporting collaborative real-time work; yet in practice, work spans many different modes: from collaborative to independent activity, and from synchronous, real-time activity to asynchronous activity. How can we design tools that allow users to transition between these modes of activity smoothly in their work? We consider how the common office and domestic whiteboard are used for both independent and asynchronous activity, showing how users employ the whiteboard to transition between these and other modes of activity. Our findings suggest that the whiteboard does so by being a contextually located display with visually persistent content, facilitating transitions because it is a flexible, common tool enabling the creation of representations that are useful across modes. We explore the design implications of these findings with respect to interactive whiteboard tools, and discuss how they can be applied more generally to inform the design of groupware tools.

TR-2008-05 Coupled CRFs for estimating the underlying ground surface from airborne LiDAR data, May 21, 2008 Wei-Lwun Lu, Kevin P. Murphy, James J. Little, Alla Sheffer and Hongbo Fu, 7 pages

Airborne laser scanners (LiDAR) return point clouds of millions of points imaging large regions. It is very challenging to recover the bare earth, i.e., the surface remaining after the buildings and vegetative cover have been identified and removed; manual correction of the recovered surface is very costly. Our solution combines classification into ground and non-ground with reconstruction of the continuous underlying surface. We define a joint model on the class labels and estimated surface, $p(\vc,\vz|\vx)$, where $c_i \in \{0,1\}$ is the label of point $i$ (ground or non-ground), $z_i$ is the estimated bare-earth surface at point $i$, and $x_i$ is the observed height of point $i$. We learn the parameters of this CRF using supervised learning. The graph structure is obtained by triangulating the point clouds. Given the model, we compute a MAP estimate of the surface, $\arg \max p(\vz|\vx)$, using the EM algorithm, treating the labels $\vc$ as missing data. Extensive testing shows that the recovered surfaces agree very well with those reconstructed from manually corrected data. Moreover, the resulting classification of points is competitive with the best in the literature.

TR-2008-06 An Exploratory Study on How Can Diagramming Tools Help Support Programming Activities?, May 28, 2008 Seonah Lee, Gail C. Murphy, Thomas Fritz and Meghan Allen, 8 pages

Programmers often draw diagrams on whiteboards or on paper. To enable programmers to use such diagrams in the context of their programming environment, many tools have been built. Despite the existence and availability of such tools, many programmers continue to work predominantly with textual descriptions of source code. In this paper, we report on an exploratory study we conducted to investigate what kind of diagrammatic tool support is desired by programmers, if any. The study involved 19 professional programmers working at three different companies. The study participants desired a wide range of information content in diagrams and wanted the content to be sensitive to particular contexts of use. Meeting these needs may require flexible, adaptive and responsive diagrammatic tool support.

TR-2008-08 Uncovering Activity and Patterns in Video using Slit-Tear Visualizations, July 31, 2008 Anthony Tang, Joel Lanir, Saul Greenberg and S. Sidney Fels, 8 pages

In prior work, we introduced a visualization technique for analyzing fixed position video streams called slit-tear visualizations. This technique supports exploratory data analysis by interactively generating views about the video stream that can provide insight into the spatial/temporal relationships of the entities contained within. These insights are necessarily grounded in context of the specific video being analyzed, and in this paper, we provide a general typology of the kinds of slit-tears an analyst may use. Further, we discuss the kinds of analytic primitives that often signal relevant events given these slit-tear types. The work is relevant to human-centered computing because the technique provides the most insight in the presence of human interpretation.

TR-2008-09 Group sparsity via linear-time projection, June 06, 2008 Ewout van den Berg, Mark Schmidt, Michael P. Friedlander and Kevin Murphy, 11 pages

We present an efficient spectral projected-gradient algorithm for optimization subject to a group one-norm constraint. Our approach is based on a novel linear-time algorithm for Euclidean projection onto the one- and group one-norm constraints. Numerical experiments on large data sets suggest that the proposed method is substantially more efficient and scalable than existing methods

TR-2008-10 Collison in Unrepeated, First-Price Auctions with an Uncertain Number of Participants, August 04, 2008 Kevin Leyton-Brown, Moshe Tennenholtz, Navin A. R. Bhat and Yoav Shoham, 30 pages

We identify a self-enforcing collusion protocol (a bidding ring'') for non-repeated first-price auctions. Unlike previous work on the topic such as that by McAfee & McMillan [1992] and Marshall & Marx [2007], we allow for the existence of multiple cartels in the auction and do not assume that non-colluding agents have perfect knowledge about the number of colluding agents whose bids are suppressed by the bidding ring. We show that it is an equilibrium for agents to choose to join bidding rings when invited and to truthfully declare their valuations to a ring center, and for non-colluding agents to bid straightforwardly. Furthermore, even though our protocol is efficient, we show that the existence of bidding rings benefits ring centers and all agents, both members and non-members of bidding rings, at the auctioneer's expense.

TR-2008-11 Efficient Dynamic Programming for Optimal Multi-Location Robot Rendezvous with Proofs, August 06, 2008 Ken Alton and Ian M. Mitchell, 8 pages

We present an efficient dynamic programming algorithm to solve the problem of optimal multi-location robot rendezvous. The rendezvous problem considered can be structured as a tree, with each node representing a meeting of robots, and the algorithm computes optimal meeting locations and connecting robot trajectories. The tree structure is exploited by using dynamic programming to compute solutions in two passes through the tree: an upwards pass computing the cost of all potential solutions, and a downwards pass computing optimal trajectories and meeting locations. The correctness and efficiency of the algorithm are analyzed theoretically, while a continuous robot arm problem demonstrates the algorithm's practicality.

TR-2008-13 Action-Graph Games, September 08, 2008 Albert Xin Jiang, Kevin Leyton-Brown and Bhat Navin A.R., 54 pages

Representing and reasoning with games becomes difficult once they involve large numbers of actions and players, because utility functions can grow unmanageably. Action-Graph Games (AGGs) are a fully-expressive game representation that can compactly express utility functions with structure such as context-specific (or strict) independence, anonymity, and additivity. We show that AGGs can be used to compactly represent all games that are compact when represented as graphical games, symmetric games, anonymous games, congestion games, and polymatrix games. We further show that AGGs can compactly represent additional, realistic games that require exponential space under all of these existing representations. We give a dynamic programming algorithm for computing a player's expected utility under an arbitrary mixed-strategy profile, which can achieve running times polynomial in the size of an AGG representation. We show how to use this algorithm to achieve exponential speedups of existing methods for computing sample Nash and correlated equilibria. Finally, we present the results of extensive experiments, showing that using AGGs leads to a dramatic increase in the size of games accessible to computational analysis.

TR-2008-14 Reducing Code Navigation Effort with Differential Code Coverage, September 08, 2008 Kaitlin Duck Sherwood and Gail C Murphy, 11 pages

Programmers spend a significant amount of time navigating code. However, few details are known about how this time is spent. To investigate this time, we performed a study of professional programmers performing programming tasks. We found that these professionals frequently needed to follow execution paths in the code, but that they often made faulty assumptions about which code had executed, impeding their progress. Earlier work on software reconnaissance has addressed this problem, but has focused on whether the technique could provide the correct information to a programmer, not on whether the technique reduces or improves navigation. We built a tool, called Tripoli, that provides an approximation to software reconnaissance via differential code coverage and reran a subset of the initial study. We found that Tripoli had a positive effect on code navigation: less experienced programmers with Tripoli were often more successful in less time than experienced programmers without.

TR-2008-15 Non-von Neumann-Morgenstern expected utility maximization models of choice from behavioural game theory, September 23, 2008 James Wright, 6 pages

I survey a number of papers that describe models of choice from behavioural game theory. These models are alternatives to expected utility maximization, the standard game-theoretic model of choice [Von Neumann and Morgenstern, 1944].

TR-2008-17 Guaranteed Voronoi Diagrams of Uncertain Sites, December 31, 2008 William Evans and Jeff Sember, 13 pages

In this paper we investigate the Voronoi diagram that is induced by a set of sites in the plane, where each site's precise location is uncertain but is known to be within a particular region, and the cells of this diagram contain those points guaranteed to be closest to a particular site. We examine the diagram for sites with disc-shaped regions of uncertainty, prove that it has linear complexity, and provide an optimal algorithm for its construction. We also show that the diagram for uncertain polygons has linear complexity. We then describe two generalizations of these diagrams for uncertain discs. In the first, which is related to a standard order-k Voronoi diagram, each cell is associated with a subset of k sites, and each point within the cell is guaranteed closer to any of the sites within the subset than to any site not in the subset. In the second, each cell is associated with the smallest subset guaranteed to contain the nearest site to each point in the cell. For both generalizations, we provide tight complexity bounds and efficient construction algorithms. Finally, we examine the Delaunay triangulations that can exist for sites within uncertain discs, and provide an optimal algorithm for generating those edges that are guaranteed to exist in every such triangulation.