Subset Selection via Spectral Objectives

Selecting a small subset of items that captures key properties of a much larger data set is an important problem in a variety of areas, including machine learning, network design, and fair allocation of goods. We use a geometric model for this problem where the items (or their qualities) are represented by d-dimensional vectors. That is, given a large set E, where each element is represented by a real vector, select a small subset S of E with good properties. There are many different possible goals for subset selection problems, and we will focus on objectives obtained by summing the rank-1 matrices formed by the vectors in S, and considering some function of the eigenvalues of the resulting matrix. For example, we may consider the determinant, trace, or minimum eigenvalue. While we could simply limit the number of selected items, we can also have more elaborate constraints. We may instead restrict our attention to subsets S that are bases of a specific matroid. This will allow us to model a much broader class of problems. This work focuses on four problems which can be modeled in the spectral subset selection framework. The first, is determinant maximization under matroid constraints. For this problem, in the case that we number of vectors we are selecting is exactly d, we provide a combinatorial O(d^d)-approximation algorithm based on matroid intersection. Next, we consider the special case of the weighted Nash Social Welfare problem. This problem has its own specially-tailored relaxations, which we use to construct a new approximation algorithm. Then, we turn to the minimum eigenvalue problem with general matroid constraints. By modifying the natural convex program, and randomly rounding the optimal solution, we are able to find (1-epsilon)-approximate solution in polynomial time, when the dimension of the vectors is constant. Finally, we turn to a practical problem in electrical network design called the network reconfiguration problem. After analyzing various convex relaxations for the problem we propose a collection of potential upper and lower bound algorithms, and compare them practically.

Level thesis:degree_level

Doctoral

Department dc:contributor.department

Mathematics

Grantor dc:publisher

Georgia Institute of Technology

Year dc:date.issued

2025

Author dc:creator

• Brown, Adam

Advisor dc:contributor.advisor

• Singh, Mohit

Committee members dc:contributor.committeemember

• Blekherman, Greg
• Dey, Santanu
• Lau, Lap Chi
• Singla, Sahil

• subset selection
• experimental design
• determinant maximization
• fair allocation
• randomized rounding
• electrical flows
• convex programming

Language dc:language.iso

en_US

Handle dc:identifier.uri

https://hdl.handle.net/1853/77861

OAI identifier oai:identifier

oai:repository.gatech.edu:1853/77861