Source author record

Quentin F. Stout

Quentin F. Stout appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computation Distributed, Parallel, and Cluster Computing Information Retrieval Machine Learning

Catalog footprint

What is connected

5works

5topics

2close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

$L_0$ Isotonic Regression With Secondary Objectives

We provide algorithms for isotonic regression minimizing $L_0$ error (Hamming distance). This is also known as monotonic relabeling, and is applicable when labels have a linear ordering but not necessarily a metric. There may be exponentially many optimal relabelings, so we look at secondary criteria to determine which are best. For arbitrary ordinal labels the criterion is maximizing the number of labels which are only changed to an adjacent label (and recursively apply this). For real-valued labels we minimize the $L_p$ error. For linearly ordered sets we also give algorithms which minimize the sum of the $L_p$ and weighted $L_0$ errors, a form of penalized (regularized) regression. We also examine $L_0$ isotonic regression on multidimensional coordinate-wise orderings. Previous algorithms took $Θ(n^3)$ time, but we reduce this to $o(n^{3/2})$.

preprint2021arXiv

Generating Artificial Core Users for Interpretable Condensed Data

Recent work has shown that in a dataset of user ratings on items there exists a group of Core Users who hold most of the information necessary for recommendation. This set of Core Users can be as small as 20 percent of the users. Core Users can be used to make predictions for out-of-sample users without much additional work. Since Core Users substantially shrink a ratings dataset without much loss of information, they can be used to improve recommendation efficiency. We propose a method, combining latent factor models, ensemble boosting and K-means clustering, to generate a small set of Artificial Core Users (ACUs) from real Core User data. Our ACUs have dense rating information, and improve the recommendation performance of real Core Users while remaining interpretable.

preprint2015arXiv

An Algorithm for $L_\infty$ Approximation by Step Functions

An algorithm is given for determining an optimal $b$-step approximation of weighted data, where the error is measured with respect to the $L_\infty$ norm. For data presorted by the independent variable the algorithm takes $Θ(n + \log n \cdot b(1+\log n/b))$ time and $Θ(n)$ space. This is $Θ(n \log n)$ in the worst case and $Θ(n)$ when $b = O(n/\log n \log\log n)$. A minor change determines an optimal reduced isotonic regression in the same time and space bounds, and the algorithm also solves the $k$-center problem for 1-dimensional weighted data.

preprint2015arXiv

Optimal component labeling algorithms for mesh-connected computers and VLSI

Given an undirected graph $G$ of $n$ weighted edges, stored one edge per processor in a square mesh of $n$ processors, we show how to determine the connected components and a minimal spanning forest in $Θ(\sqrt{n})$ time. More generally, we show how to solve these problems in $Θ(n^{1/d})$ time when the mesh is a $d$-dimensional cube, where the implied constants depend upon $d$.

preprint2014arXiv

Optimal Reduced Isotonic Regression

Isotonic regression is a shape-constrained nonparametric regression in which the regression is an increasing step function. For $n$ data points, the number of steps in the isotonic regression may be as large as $n$. As a result, standard isotonic regression has been criticized as overfitting the data or making the representation too complicated. So-called "reduced" isotonic regression constrains the outcome to be a specified number of steps $b$, $b \leq n$. However, because the previous algorithms for finding the reduced $L_2$ regression took $Θ(n+bm^2)$ time, where $m$ is the number of steps of the unconstrained isotonic regression, researchers felt that the algorithms were too slow and instead used approximations. Other researchers had results that were approximations because they used a greedy top-down approach. Here we give an algorithm to find an exact solution in $Θ(n+bm)$ time, and a simpler algorithm taking $Θ(n+b m \log m)$ time. These algorithms also determine optimal $k$-means clustering of weighted 1-dimensional data.