Guy B. Oldaker

Guy B. Oldaker, Maria Emelianenko

Clustering algorithms remain valuable tools for grouping and summarizing the most important aspects of data. Example areas where this is the case include image segmentation, dimension reduction, signals analysis, model order reduction, numerical analysis, and others. As a consequence, many clustering approaches have been developed to satisfy the unique needs of each particular field. In this article, we present a family of data-adaptive partitioning algorithms that unifies several well-known methods (e.g., k-means and k-subspaces). Indexed by a single parameter and employing a common minimization strategy, the algorithms are easy to use and interpret, and scale well to large, high-dimensional problems. In addition, we develop an adaptive mechanism that (a) exhibits skill at automatically uncovering data structures and problem parameters without any expert knowledge and, (b) can be used to augment other existing methods. By demonstrating the performance of our methods on examples from disparate fields including subspace clustering, model order reduction, and matrix approximation, we hope to highlight their versatility and potential for extending the boundaries of existing scientific domains. We believe our family's parametrized structure represents a synergism of algorithms that will foster new developments and directions, not least within the data science community.

Samuel S. Mendelson, Robert W. Strand, Guy B. Oldaker et al.

In the NISQ-era of quantum computing, we should not expect to see quantum devices that provide an exponential improvement in runtime for practical problems, due to the lack of error correction and small number of qubits available. Nevertheless, these devices should be able to provide other performance improvements, particularly when combined with existing classical machines. In this article, we develop several hybrid quantum-classical clustering algorithms that can be employed as subroutines on small, NISQ-era devices. These new hybrid algorithms require a number of qubits that is at most logarithmic in the size of the data, provide performance improvement and/or runtime improvement over their classical counterparts, and do not require a black-box oracle. Consequently, we are able to provide a promising near-term application of NISQ-era devices.