Back to search

Cornell University

A Probabilistic Analysis Of Low-Rank Approximations In Optimization Problems With Ellipsoidal Constraints

Abstract

dc:description.abstract

Low-rank matrix approximations have been used in many applications, because they provide compact representations of the data and reveal the underlying structure. This dissertation is concerned with applications of low-rank approximations in optimization problems. Motivation comes from a recent effort in designing radiotherapy treatment plans for patients with cancer. The problem was formulated as a second-order cone program. Due to the size of the problem, low-rank matrices were used in order to create a computationally tractable approximation. This work is an attempt to theoretically explain the success of low-rank approximations in such problems. The main vehicle for this analysis is a stylized optimization problem with randomly sampled ellipsoidal constraints. We consider two different matrix approximations, one based on the Singular Value Decomposition and one based on column sampling, and apply them to the matrices in the stylized problem. We provide results about the probability distributions of the optimal values of these problems as well as their relative difference. Since the focus is on problems with large number of constraints, we provide asymptotic results, when the number of constraints tends to infinity. We finally compare the performance of the two approximations and discuss the implications of our results.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Schismenos, Spyridon

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
6711583

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Schismenos, Spyridon. A Probabilistic Analysis Of Low-Rank Approximations In Optimization Problems With Ellipsoidal Constraints. 2009. https://hdl.handle.net/1813/13872