Caratheodory cubature measures
<p>We introduce an efficient algorithm for computing Carathéodory cubature measures, which are defined as interpolatory cubature measures with positive weights, whose cardinality grows polynomially with dimension, as proved in [16]. We discuss two Carathéodory cubature problem formulations. Bo...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
2016
|
| _version_ | 1797086302850514944 |
|---|---|
| author | Tchernychova, M |
| author2 | Lyons, T |
| author_facet | Lyons, T Tchernychova, M |
| author_sort | Tchernychova, M |
| collection | OXFORD |
| description | <p>We introduce an efficient algorithm for computing Carathéodory cubature measures, which are defined as interpolatory cubature measures with positive weights, whose cardinality grows polynomially with dimension, as proved in [16]. We discuss two Carathéodory cubature problem formulations. Both are based on thinning the support of the Cartesian product cubature measure, whose cardinality grows exponentially with dimension, via a formulation of a suitable feasibility LP (Linear Programming) problem. A basic feasible solution to the latter fully characterises a Carathéodory cubature measure.</p> <p>The first problem formulation, initially presented in [48], employes the Simplex Algorithm or Interior Point Method to construct a basic feasible solution to the aforementioned LP problem. The complexity of this method is dependent on the number of nodes in the Cartesian product cubature and thus grows exponentially with dimension.</p> <p>The second problem formulation constitutes the main contribution of the present work. Starting from the LP problem, arising from the Cartesian product cubature construction, we employ a hierarchical cluster representation of the underlying constraint matrix and the strictly feasible solution, arising from the weights of the Cartesian product cubature. Applying the Recombination Algorithm, introduced in [96], to this hierarchical data structure, we recursively generate a sequence of smaller LP problems. We construct a basic feasible solution to each LP problem in turn, by employing a novel algorithm, based on the SVD (Singular Value Decomposition) of the constraint matrix, culminating in a basic feasible solution for the original LP problem. The complexity of this algorithm, is independent of the number of nodes in the Cartesian product cubature, and can be shown to grow polynomially rather than exponentially with dimension. Moreover, the novel SVD-based method for computing basic feasible solutions, produces a one order of magnitude speed-up of the overall algorithm, when compared to the algorithm in [96], and is therefore preferable.</p> |
| first_indexed | 2024-03-07T02:20:08Z |
| format | Thesis |
| id | oxford-uuid:a3a10980-d35d-467b-b3c0-d10d2e491f2d |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:20:08Z |
| publishDate | 2016 |
| record_format | dspace |
| spelling | oxford-uuid:a3a10980-d35d-467b-b3c0-d10d2e491f2d2022-03-27T02:28:20ZCaratheodory cubature measuresThesishttp://purl.org/coar/resource_type/c_db06uuid:a3a10980-d35d-467b-b3c0-d10d2e491f2dORA Deposit2016Tchernychova, MLyons, T<p>We introduce an efficient algorithm for computing Carathéodory cubature measures, which are defined as interpolatory cubature measures with positive weights, whose cardinality grows polynomially with dimension, as proved in [16]. We discuss two Carathéodory cubature problem formulations. Both are based on thinning the support of the Cartesian product cubature measure, whose cardinality grows exponentially with dimension, via a formulation of a suitable feasibility LP (Linear Programming) problem. A basic feasible solution to the latter fully characterises a Carathéodory cubature measure.</p> <p>The first problem formulation, initially presented in [48], employes the Simplex Algorithm or Interior Point Method to construct a basic feasible solution to the aforementioned LP problem. The complexity of this method is dependent on the number of nodes in the Cartesian product cubature and thus grows exponentially with dimension.</p> <p>The second problem formulation constitutes the main contribution of the present work. Starting from the LP problem, arising from the Cartesian product cubature construction, we employ a hierarchical cluster representation of the underlying constraint matrix and the strictly feasible solution, arising from the weights of the Cartesian product cubature. Applying the Recombination Algorithm, introduced in [96], to this hierarchical data structure, we recursively generate a sequence of smaller LP problems. We construct a basic feasible solution to each LP problem in turn, by employing a novel algorithm, based on the SVD (Singular Value Decomposition) of the constraint matrix, culminating in a basic feasible solution for the original LP problem. The complexity of this algorithm, is independent of the number of nodes in the Cartesian product cubature, and can be shown to grow polynomially rather than exponentially with dimension. Moreover, the novel SVD-based method for computing basic feasible solutions, produces a one order of magnitude speed-up of the overall algorithm, when compared to the algorithm in [96], and is therefore preferable.</p> |
| spellingShingle | Tchernychova, M Caratheodory cubature measures |
| title | Caratheodory cubature measures |
| title_full | Caratheodory cubature measures |
| title_fullStr | Caratheodory cubature measures |
| title_full_unstemmed | Caratheodory cubature measures |
| title_short | Caratheodory cubature measures |
| title_sort | caratheodory cubature measures |
| work_keys_str_mv | AT tchernychovam caratheodorycubaturemeasures |