Publications

Publications

This page is outdated. I will be update this soon with my more recent papers. An updated list of my publications may be found here.

Most of my work has focused on randomized algorithms for matrix operations and their applications. I have also worked on algorithms for computational finance problems and on algorithms for testing electronic circuits.

Randomized algorithms for matrix operations and applications

M. W. Mahoney, M. Maggioni, and P. Drineas, Tensor-CUR decompositions for tensor-based data,

We present an extension of the CUR decomposition of matrices to tensors, and apply it in two domains: hyperspectral analysis of images for cancer classifications, and recommendation systems. Experimental results are reported on data gathered from the Yale Medical School, and publicly available data from Jester.

P. Drineas, M. W. Mahoney, and S. (Muthu) Muthukrishnan, Polynomial time algorithm for column-row based relative error low-rank matrix approximation,

We present an algorithm that computes a relative error approximation of the form CUR to the best rank k approximation of a given matrix A. The presented approximation has a very special form: C consists of a few columns of A and R consists of a few rows of A. The motivation for such an approximation emerges from data applications: the relative error CUR approximation extracts the same structure that the Singular Value Decomposition (SVD) extracts, but is much easier to interpret in data analysis domains, since C and R are subsets of the data instead of linear combinations of the data.

P. Drineas, M. W. Mahoney, and S. (Muthu) Muthukrishnan, Sampling Algorithms for l₂ Regression and Applications,

We present and analyze a randomized algorithm for solving overdetermined least squares problems. Our sampling procedure depends on the left singular vectors of the matrix of the basis vectors as well as on the way that the target vector lies in the subspace perpendicular to the subspace spanned by the basis vectors.

P. Drineas and M. W. Mahoney, A Randomized Algorithm for a Tensor-Based Generalization of the SVD,

We present an algorithm that approximates a (standard) generalization of the Singular Value Decomposition to tensors. When restricted to matrices, our approximamation algorithm provides a low-rank matrix decomposition that is expressed in terms of the columns and rows of the original matrix. Connections with several similar matrix decompositions are discussed.

D. Freedman and P. Drineas, Minimization via graph cuts: k-pixel interactions and approximate algorithms

We discuss the class of energy functions that can be efficiently minimized by graph cuts, by using the adjacency matrices of graphs to solve optimization problems. We also discuss the applicability of recent developments in the design of PTAS for dense Max-SNP problems.

P. Drineas and M. W. Mahoney, On the Nystrom Method for Approximating a Gram Matrix for Improved Kernel-Based Learning,

We develop and analyze an algorithm to compute an easily-interpretable low-rank approximation to a Gram matrix such that computations of interest may be performed more rapidly.The relationships between this algorithm and the Nystrom method from integral equation theory are discussed.

P. Drineas, R. Kannan, and M.W. Mahoney, Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication

This is the first paper in a series of three papers describing and analyzing two randomized algorithms for approximating matrix multiplication. Given two matrices, the first algorithm samples columns and rows from the two input matrices to approximate their product; the second algorithm samples elements from the two matrices.

P. Drineas, R. Kannan, and M.W. Mahoney, Fast Monte Carlo Algorithms for Matrices II: Computing a Low Rank Approximation to a Matrix

This is the second paper in a series of 3 papers describing and analyzing two randomized algorithms for approximating the singular vectors and singular values of a matrix. The first algorithm samples a few columns (rows) of the matrix to approximate the top few left (right) singular vectors and the corresponding singular values in linear time (after preprocessing), whereas the second algorithm employs two levels of sampling in order to approximate a description of the top few left (or right) singular vectors and the corresponding singular values in constant time (after preprocessing).

P. Drineas, R. Kannan, and M.W. Mahoney, Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition

This is the third paper in a series of three papers describing and analyzing two randomized algorithms for computing a decomposition of a matrix A of the form CUR. Here C is a matrix containing a few columns of A, R is a matrix containing a few rows of A, and U is a carefully chosen matrix that makes the error A - CUR provably small. The first algorithm computes U in linear time (after preprocessing), whereas the second algorithm computes U in constant time (after preprocessing).

D. Freedman and P. Drineas, Energy Minimization via Graph Cuts: Settling What is Possible

Preliminary version of "Minimization via graph cuts: k-pixel interactions and approximate algorithms".

P. Drineas and M.W. Mahoney, Approximating a Gram Matrix for Improved Kernel-Based Learning

Preliminary version of "On the Nystrom Method for Approximating a Gram Matrix for Improved Kernel-Based Learning".

P. Drineas, R. Kannan, and M.W. Mahoney, Sampling Sub-problems of Heterogeneous Max-Cut Problems and Approximation Algorithms

Preliminary version of "Sampling Sub-problems of Heterogeneous Max-Cut Problems and Approximation Algorithms", YALEU/DCS/TR-1283.

P. Drineas, R. Kannan, and M.W. Mahoney, Sampling Sub-problems of Heterogeneous Max-Cut Problems and Approximation Algorithms

We present an approximation algorithm for the Max-Cut problem on weighted graphs. The algorithm has an improved error bound for dense graphs with heterogeneous edge weights, and employs the constant-time CUR decomposition and a novel result for sampling subprograms of large linear programs.

P. Drineas, R. Kannan, A. Frieze, S. Vempala, and V. Vinay, Clustering of Large Graphs via the Singular Value Decomposition

We consider the problem of partitioning a set of points in the n-dimensional space so as to satisfy the objective of the k-means clustering algorithm. We prove that the problem is NP-hard and devise a 2-approximation algorithm by using the Singular Value Decomposition to solve a continuous relaxation of the problem. We also prove that choosing a few columns of a given matrix provides good approximations to the top few singular values and left singular values of the matrix.

P. Drineas, Pass-Efficient Algorithms for Approximating Large Matrices, Mathematisches Forschungsinstitut Oberwolfach (MFO) Workshop on Approximation Algorithms for NP-Hard Problems, Oberwolfach, Germany, 2004.

A brief overview of randomized algorithms for matrix operations for a talk presented at Oberwolfach.
P. Drineas, M. Krishnamoorthy, D. Sofka, and B. Yener, Studying E-mail Graphs for Intelligence Monitoring and Analysis in the Absence of Semantic Information, Symposium on Intelligence and Security Informatics, 2004.

A brief study of the spectral characteristics of the email graph of a small community of RPI users.
P. Drineas, E. Drinea, and P. Huggins, An Experimental Evaluation of a Monte-Carlo Algorithm for Singular Value Decomposition

We evaluate the accuracy of sampling-based Singular Value Decomposition algorithms on image matrices. We demonstrate that our sampling-based algorithms are quite accurate, both from a visual and a quantitative perspective.

P. Drineas and R. Kannan, Pass Efficient Algorithm for Large Matrices

Preliminary version of "Fast Monte Carlo Algorithms for Matrices {III}: Computing a Compressed Approximate Matrix Decomposition"

P. Drineas, I. Kerenidis, and P. Raghavan, Competitive Recommendation Systems

We describe a model for recommendation systems and provide algorithms that (provably) accurately recover the user preferences if we assume that the customer - product utility matrix has low numerical rank.

P. Drineas and R. Kannan, Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication

Preliminary version of "Fast Monte Carlo Algorithms for Matrices {I}: Approximating Matrix Multiplication".

P. Drineas, E. Drinea, and P. Huggins, A Randomized Singular Value Decomposition Algorithm for Image Processing

Preliminary version of "An Experimental Evaluation of a Monte-Carlo Algorithm for Singular Value Decomposition".

P. Drineas, R. Kannan, A. Frieze, S. Vempala, and V. Vinay, Clustering in Large Graphs and Matrices

Preliminary version of "Clustering of Large Graphs via the Singular Value Decomposition".

Computational finance

K. Akcoglu, P. Drineas, and M. Kao, Fast Universalization of Investment Strategies with Provably Good Relative Returns

We present a general framework for investment strategies that are universalizable, extending Cover's universal portfolio work. We also present provably good approximation algorithms for implementing universalization algorithms in our framework.

K. Akcoglu, P. Drineas, and M. Kao, Fast Universalization of Investment Strategies with Provably Good Relative Returns

Preliminary version of "Fast Universalization of Investment Strategies with Provably Good Relative Returns".

Testing of Electronic Circuits

The following papers are joint work with Yiorgos Makris. Please check TRELA for a description of our work and links to the papers.

S. Almukhaizim, P. Drineas, and Y. Makris, Entropy-Driven Parity Tree Selection for Low-Overhead Concurrent Error Detection in Finite State Machines, accepted to the IEEE Transactions on Computer-Aided Design of Electronic Circuits and Systems, 2005.
S. Almukhaizim, P. Drineas, and Y. Makris, Compaction-Based Concurrent Error Detection for Digital Circuits, Microelectronics Journal, vol. 36, no. 9, pp. 856--862, Elsevier, 2005.
S. Almukhaizim, P. Drineas, and Y. Makris, Cost-based selection of parity trees, Proc. of the IEEE VLSI Test Symposium, pp 319--324, 2004.
S. Almukhaizim, P. Drineas, and Y. Makris, Concurrent error detection for combinational and sequential logic via output compaction, Proc. of the IEEE International Symposium on Quality Electronic Design, pp. 459--464, 2004.
S. Almukhaizim, P. Drineas, and Y. Makris, On concurrent error detection with bounded latency in FSMs, Proc. of the IEEE Design Automation and Test in Europe Conference, pp. 596--601, 2004.
P. Drineas and Y. Makris, Spare: Selective partial replication for concurrent fault detection in {FSMs}}, IEEE Transactions on Instrumentation and Measurement, vol. 52, no. 6, pp. 1729-1737, 2003.
S. Almukhaizim, P. Drineas, and Y. Makris, On Compaction-based concurrent error detection, Proc. of the IEEE On-Line Test Symposium, pp. 157--161, 2003.
P. Drineas and Y. Makris, On the Compaction of Independent Test Sequences for Sequential Circuits, Proc. of the IEEE International Conference on Computer Design, pp. 380--386, 2003.
P. Drineas and Y. Makris, Non-intrusive concurrent error detection in FSMs through State/Output compaction and monitoring via parity trees, Proc. of the Design Automation and Test in Europe Conference, pp. 1164--1165, 2003.
P. Drineas and Y. Makris, SPaRe: selective partial replication for concurrent fault detection in FSMs, Proc. of the IEEE International Conference on VLSI Design, pp. 84--91, 2003.
P. Drineas and Y. Makris, Concurrent Fault Detection in Random Combinational Logic, Proc. of the IEEE International Symposium on Quality Electronic Design, pp. 425--430, 2003.
P. Drineas and Y. Makris, On the Compaction of Independent Test Sequences for Sequential Circuits, IEEE European Test Workshop, Maastricht, Netherlands, 2003.
P. Drineas and Y. Makris, Non-intrusive design of concurrently self-testable FSMs, Proc. of the IEEE Asian Test Symposium, pp. 33--38, 2002.
P. Drineas and Y. Makris, Non-Intrusive Design of Concurrently Self-Testable FSMs, IEEE North Atlantic Test Workshop, Montauk NY, USA, 2002.