Wireless spectrum sharing techniques have become very important due to the increasing demand for spectrum. Hence, there is growing interest in using real-time auctions for economically incentivizing users to share their excess spectrum. However, the communication and control requirements of real-time secondary spectrum auctions would be overwhelming for wireless networks. Prior literature has not considered critical communication constraints such as bid price quantization and error prone bid revelation. These schemes also have high overheads which cannot be accommodated in wireless standards. We propose auction schemes where a central clearing authority auctions spectrum to bidders, while explicitly accounting for these communication constraints. Our techniques are related to the posterior matching scheme, which is used in systems with channel output feedback. We consider several scenarios where the clearing authority's objective is to award spectrum to bidders who value spectrum the most. We prove that this objective is asymptotically attained by our scheme when bidders are nonstrategic with constant bids. We propose separate schemes to make strategic users reveal their private values truthfully, auction multiple subchannels among strategic users, and track slowly time-varying bid prices. We provide extensive simulation results to illustrate the performance and effectiveness of our algorithms.

We propose a quantitative framework for constructing optimal policies to manage systemic risk in financial networks. We analyze borrower-lender networks where all the loan amounts and cash flows are known, and where some nodes may default in the absence of external intervention. Given a fixed amount of cash to be injected into the system, we address the problem of allocating it among the nodes to minimize the overall amount of unpaid liabilities. We show that this problem is equivalent to a linear program. In addition, we address the problem of allocating the cash injection amount so as to minimize the number of nodes in default. For this problem, we develop an approximate algorithm which uses reweighted ℓ1minimization. We illustrate this algorithm using two synthetic network structures for which the optimal solution can be calculated exactly. We show through numerical simulations that the solutions calculated by our algorithm are close to optimal.

Many securities markets are organized as double auctions where each incoming limit order - i.e., an order to buy or sell at a specific price - is stored in a data structure called the limit order book. A trade happens whenever a marketable order arrives. This order flow is visible to every market participant in real time. We propose a novel non-parametric approach to short-term forecasting of the mid-price change in a limit order book (i.e., of the change in the average of the best offer and the best bid prices). We construct a state characterizing the order book at each time instant and compute a feature vector for each value of the state. The features get updated during the course of a trading day, as new order flow information arrives. Our prediction rules at every time instant during the trading day are based on the feature vector of the state observed at that time instant. The distinction of our approach from the previous ones is that it does not impose a restrictive parametric model. Implicit assumptions of our method are very mild. Initial experiments with real order book data from NYSE suggest that our algorithms show promise. We illustrate their usage in a practical application of executing a large trade.

We introduce the hypothesis selection filter (HSF) as a new approach for image quality enhancement. We assume that a set of filters has been selected a priori to improve the quality of a distorted image containing regions with different characteristics. At each pixel, HSF uses a locally computed feature vector to predict the relative performance of the filters in estimating the corresponding pixel intensity in the original undistorted image. The prediction result then determines the proportion of each filter used to obtain the final processed output. In this way, the HSF serves as a framework for combining the outputs of a number of different user selected filters, each best suited for a different region of an image. We formulate our scheme in a probabilistic framework where the HSF output is obtained as the Bayesian minimum mean square error estimate of the original image. Maximum likelihood estimates of the model parameters are determined from an offline fully unsupervised training procedure that is derived from the expectation-maximization algorithm. To illustrate how to apply the HSF and to demonstrate its potential, we apply our scheme as a post-processing step to improve the decoding quality of JPEG-encoded document images. The scheme consistently improves the quality of the decoded image over a variety of image content with different characteristics. We show that our scheme results in quantitative improvements over several other state-of-the-art JPEG decoding methods.

We propose the use of large tree-structured dictionaries of tilings for video compression. Our first contribution is the construction of a rate-distortion cost function that admits fast search algorithms to select the optimal tiling for the motion compensation stage of a video coder. The computation of the cost is enabled through novel algorithms to approximate the bit rate and the distortion. Our second contribution is an efficient arithmetic coding algorithm to encode the selected tree-structured tiling. We illustrate the effectiveness of our approach by showing that a H.264/AVC-like video coder utilizing one of the proposed tiling selection methods results in up to 16% savings in bit rate for several standard video sequences as compared to H.264/AVC. This is accomplished with only a modest increase in the computation time at the encoder.

One of the consequences of the Capital Asset Pricing Model (CAPM) is that the expected excess return of a financial instrument is proportional to the expected excess market return. The proportionality constant, called the instrument's beta, is the coefficient in the linear least-squares fit of the excess return of the instrument with the excess return of the market. CAPM therefore implies that stocks with larger empirical estimates of beta will tend to produce larger returns. Following the testing procedure from a 2006 study by Grantham, we analyze this hypothesis using the stock return data for the S&P 500 constituents from 1965 to 2009. We obtain several statistically significant results inconsistent with the hypothesis.

Modern portfolio theory dates back to a seminal 1952 paper by H. Markowitz and has been very influential both in academic finance and among practitioners in the financial industry. Given a set of assets, the theory can be used to compute the amount to be invested in each asset in order to construct an optimally diversified portfolio. One of the parameters required in this calculation is the covariance matrix of asset returns which, in any practical application, is unknown and must be estimated from historical data. Due to the fact that financial data is often nonstationary, basing the estimates on historical data over a very long time period may not be advisable. This renders the problem of covariance estimation difficult, especially for large portfolios. A large body of literature exists proposing different covariance estimators. We focus on one frequently cited paper by Ledoit and Wolf which proposes a covariance estimation method and purports to show that this method leads to statistically significant improvements over several other methods. We show that this is not the case: in fact, their method does not exhibit statistically significant differences from three other methods.

The JPEG standard is one of the most prevalent image compression schemes in use today. While JPEG was designed for use with natural images, it is also widely used for the encoding of raster documents. Unfortunately, JPEG's characteristic blocking and ringing artifacts can severely degrade the quality of text and graphics in complex documents. We propose a JPEG decompression algorithm which is designed to produce substantially higher quality images from the same standard JPEG encodings. The method works by incorporating a document image model into the decoding process which accounts for the wide variety of content in modern complex color documents. The method works by first segmenting the JPEG encoded document into regions corresponding to background, text, and picture content. The regions corresponding to text and background are then decoded using maximum a posteriori (MAP) estimation. Most importantly, the MAP reconstruction of the text regions uses a model which accounts for the spatial characteristics of text and graphics. Our experimental comparisons to the baseline JPEG decoding as well as to three other decoding schemes, demonstrate that our method substantially improves the quality of decoded images, both visually and as measured by PSNR.

We investigate the automated segmentation of microstructures of a nickel-based superalloy using digital microscopy data. We study the combination of a region merging segmentation method called the stabilized inverse diffusion equation (SIDE), and a stochastic segmentation method, the expectation-maximization/maximization of the posterior marginals (EM/MPM) algorithm. We use the SIDE algorithm to segment the grain boundaries and we use the EM/MPM algorithm to classify two phases of the material within each grain. Experimental results demonstrate the effectiveness of our approach.

We propose a stochastic context-free grammar model whose structure can alternatively be viewed as a graphical model, and use it to model time series. We use the inside-outside algorithm to estimate the model parameters. We assume that the time series is a finite-order Markov process generated by our model, and develop an algorithm to forecast the conditional variance of the process. We use this algorithm to forecast the volatility of the S&P 500 index, achieving results that outperform both standard and more recent approaches.

This paper describes a real-time, strip-based, low-complexity document page classification algorithm, which can be used as a copy mode selector in the copy pipeline. The benefits of such a copy mode selector include improving copy quality, simplifying user interaction, and increasing copy rate.

We propose a new model for event-related functional magnetic resonance imaging (fMRI), and develop a new set of tools for activation detection. A novel feature of our framework is the explicit modeling of the spatial correlation introduced by the scanner. We propose simple, efficient algorithms to estimate model parameters. We develop an activation detection algorithm which consists of two parts: image restoration and least-squares estimation of the parameters of the hemodynamic response function. During the image restoration stage, a total-variation-based approach is employed to restore each data slice, for each time index. The amplitude of the least-squares fit of the hemodynamic response function is then thresholded to yield an estimate of the activation map. We illustrate the promise of our method through several experiments with synthetic data as well as one example with real data.

We present a novel probabilistic model for the hierarchal structure of an image and its regions. We call this model spatial random tree grammars (SRTGs). We develop algorithms for exact computation of likelihoods and MAP estimates and exact EM updates for model-parameter estimation. We collectively call these algorithms the center-surround algorithm. We use the center-surround algorithm to automatically estimate the ML parameters of SRTGs, classify images based on their likelihood and based on the MAP estimate of the associated hierarchal structure. We apply our method to the task of classifying natural images and demonstrate that the addition of hierarchal structure significantly improves upon the performance of a baseline model that lacks such structure.

We introduce a novel nonlinear diffusion equation for images defined on an arbitrary graph and taking values on a circle. We use this nonlinear diffusion to develop an effective segmentation algorithm for such images. We apply this algorithm to segmenting texture images based on the orientation feature defined as the angle of the gradient.

We build on our previous work on best basis selection algorithms in large tree-structured dictionaries, previously used to construct effective image coders based on block and lapped transforms. In the present paper, we use such algorithms to select the optimal tiling for the motion compensation step in video compression. We illustrate the effectiveness of this approach by showing that our tiling selection method results in up to 18% savings in bit rate as compared to the H.264 tiling selection, for several standard video sequences.

We propose a novel family of nonlinear diffusion equations and apply it to the problem of segmentation of multivalued images. We show that this family can be viewed as an extension of stabilized inverse diffusion equations (SIDEs) which were proposed for restoration, enhancement, and segmentation of scalar-valued signals and images in [39]. Our new diffusion equations can process vector-valued images defined on arbitrary graphs which makes them well suited for segmentation. In addition, we introduce novel ways of utilizing the shape information luring the diffusion process. We demonstrate the effectiveness of our methods on a large number of segmentation tasks.

We address the best basis problem--or, more generally, the best representation problem: Given a signal, a dictionary of representations, and an additive cost function, the aim is to select the representation from the dictionary which minimizes the cost for the given signal. We develop a new framework of multitree dictionaries, which includes some previously proposed dictionaries as special cases. We show how to efficiently find the best representation in a multitree dictionary using a recursive tree-pruning algorithm. We illustrate our framework through several examples, including a novel block image coder, which significantly outperforms both the standard JPEG and quadtree-based methods and is comparable to embedded coders such as JPEG2000 and SPIHT.

We develop a new class of hierarchical stochastic image models called spatial random trees (SRTs) which admit polynomial-complexity exact inference algorithms. Our framework of multitree dictionaries is the starting point for this construction. SRTs are stochastic hidden tree models whose leaves are associated with image data. The states at the tree nodes are random variables, and, in addition, the structure of the tree is random and is generated by a probabilistic grammar. We describe an efficient recursive algorithm for obtaining the maximum a posteriori estimate of both the tree structure and the tree states given an image. We also develop an efficient procedure for performing one iteration of the expectation-maximization algorithm and use it to estimate the model parameters from a set of training images. We address other inference problems arising in applications such as maximization of posterior marginals and hypothesis testing. Our models and algorithms are illustrated through several image classification and segmentation experiments, ranging from the segmentation of synthetic images to the classification of natural photographs and the segmentation of scanned documents. In each case, we show that our method substantially improves accuracy over a variety of existing methods.

We use the framework of multitree dictionaries (Huang et al. (2003)) to design a novel DCT-based image coder which significantly outperforms both the standard JPEG and the quadtree-based approach of Ramchandran et al. (1993).

We propose a novel family of nonlinear diffusion equations and apply it to the problem of texture segmentation. This family can be viewed as an extension of stabilized inverse diffusion equations (SIDEs) which were proposed for restoration, enhancement, and segmentation of scalar-valued signals and images in I. Pollak et al. (2000). Our new diffusion equations can process vector-valued images defined on arbitrary graphs. In addition, we introduce novel ways of utilizing the shape information during the diffusion process. We demonstrate the effectiveness of our methods by showing that they outperform state-of-the-art algorithms on a large number of texture segmentation tasks.

We generalize our results of [Y. Huang et al, 2005 and 2003] and propose a new framework of multitree dictionaries which include many previously proposed dictionaries as well as many new, very large, tree-structured dictionaries. We present an efficient, globally optimal algorithm to find the best tree in such a dictionary. We describe a novel block image coder based on our framework, which is an improvement over our image coder presented in Y. Huang et al, (2005).

We build a multitree dictionary of local cosine bases and develop a novel image coder that extracts the best basis in such a dictionary with respect to a rate-distortion cost. This dictionary is much larger than standard quadtree-based dictionaries, and therefore, our algorithm needs more overhead bits to encode the basis selection. Despite this, we show that the resulting algorithm outperforms an existing quadtree local cosine image compression algorithm. We also show that our multitree local cosine coder outperforms both SPIHT and a multitree block-DCT method previously developed by us, on several textured images.

We propose a best basis search algorithm for local cosine dictionaries. We improve upon the classical best local cosine basis selection based on a dyadic tree (Coifman, R.R. and Wickerhauser, M.V., IEEE Trans. Inf. Th., vol.38, no.2, p.713-18, 1992), by considering a larger dictionary of bases. This results in more compact representations, lower costs, and approximate shift-invariance. We also provide a version of our algorithm which is strictly shift-invariant.

A new class of multiscale multidimensional stochastic processes called spatial random trees is introduced. The model is based on multiscale stochastic trees with stochastic structure as well as stochastic states. Procedures are developed for exact likelihood calculation, MAP estimation of the process, and estimation of the parameters of the process. The new framework is illustrated through a simple binary image classification problem.

A new class of multiscale multidimensional stochastic processes called spatial random trees was recently introduced in J. Pollak et al. (2003). The model is based on multiscale stochastic trees with stochastic structure as well as stochastic states. In this work, we describe a method for estimating the parameters of the process.

Summary form only given, as follows. Building on our image restoration and segmentation algorithms developed in Pollak et al. (2000), we present a very simple nonlinear diffusion equation and show its utility both for image segmentation and for the detection of abrupt changes in 1-D. We show that it may be interpreted as a variant of the Perona-Malik (1990) equation, as the steepest descent equation for the total variation (Bouman and Sauer 1991, Rudin et al. 1992), and-in 1-D-as a solver of a simple version of the Mumford-Shah (1985) problem. The analysis of our equation in 1-D reveals it to be an exact solver of certain maximum likelihood detection/estimation problems. The major advantage over other methods to solve these problems is O(N log N) computational complexity in one spatial dimension. Finally, we show our method to be a robust estimator (in the spirit of H-infinity estimation (Nagpal and Khargonekar 1991)) for a restricted class of 1-D problems. Experiments suggest that the 2-D version of our algorithm retains robustness properties of the 1-D version. Moreover, if only a binary segmentation is required, the computational complexity of our 2-D algorithm is still O(N log N). A remaining challenge is to extend our probabilistic analysis of the 1-D algorithm to 2-D, designing fast and optimal image segmentation algorithms.

We introduce a family of first-order multidimensional ordinary differential equations (ODEs) with discontinuous right-hand sides and demonstrate their applicability in image processing. An equation belonging to this family is an inverse diffusion everywhere except at local extrema, where some stabilization is introduced. For this reason, we call these equations "stabilized inverse diffusion equations" (SIDEs). Existence and uniqueness of solutions, as well as stability, are proven for SIDEs. A SIDE in one spatial dimension may be interpreted as a limiting case of a semi-discretized Perona-Malik equation. In an experiment, SIDE's are shown to suppress noise while sharpening edges present in the input signal. Their application to image segmentation is also demonstrated.

A nonlinear diffusion process known to be effective for image segmentation is analyzed in 1-D. It is shown that it optimally solves certain edge detection problems. A fast implementation of the algorithm is introduced.