VTechWorks staff will be away for the winter holidays starting Tuesday, December 24, 2024, through Wednesday, January 1, 2025, and will not be replying to requests during this time. Thank you for your patience, and happy holidays!
 

Approximate Positively Correlated Distributions and Approximation Algorithms for D-optimal Design

Simple item page
dc.contributor.authorSingh, Manojen
dc.contributor.authorXie, W.en
dc.contributor.departmentIndustrial and Systems Engineeringen
dc.date.accessioned2018-07-25T20:44:42Zen
dc.date.available2018-07-25T20:44:42Zen
dc.date.issued2018-02-26en
dc.description.abstractExperimental design is a classical problem in statistics and has also found new applications in machine learning. In the experimental design problem, the aim is to estimate an unknown vector x in m-dimensions from linear measurements where a Gaussian noise is introduced in each measurement. The goal is to pick k out of the given n experiments so as to make the most accurate estimate of the unknown parameter x. Given a set S of chosen experiments, the most likelihood estimate x' can be obtained by a least squares computation. One of the robust measures of error estimation is the D-optimality criterion which aims to minimize the generalized variance of the estimator. This corresponds to minimizing the volume of the standard confidence ellipsoid for the estimation error x-x'. The problem gives rise to two natural variants depending on whether repetitions are allowed or not. The latter variant, while being more general, has also found applications in the geographical location of sensors. In this work, we first show that a 1/e-approximation for the D-optimal design problem with and without repetitions giving us the first constant factor approximation for the problem. We also consider the case when the number of experiments chosen is much larger than the dimension of the measurements and provide an asymptotically optimal approximation algorithm.en
dc.description.notes23 pagesen
dc.format.mimetypeapplication/pdfen
dc.identifier.doihttps://doi.org/10.1137/1.9781611975031.145en
dc.identifier.orcidXie, W [0000-0001-5157-1194]en
dc.identifier.urihttp://hdl.handle.net/10919/84392en
dc.language.isoenen
dc.relation.urihttp://arxiv.org/abs/1802.08372v1en
dc.relation.urihttp://dx.doi.org/10.1137/1.9781611975031.145en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectstat.MLen
dc.subjectcs.DSen
dc.titleApproximate Positively Correlated Distributions and Approximation Algorithms for D-optimal Designen
dc.title.serialProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018en
dc.typeArticle - Refereeden
dc.type.dcmitypeTexten
pubs.organisational-group/Virginia Techen
pubs.organisational-group/Virginia Tech/All T&R Facultyen
pubs.organisational-group/Virginia Tech/Engineeringen
pubs.organisational-group/Virginia Tech/Engineering/COE T&R Facultyen
pubs.organisational-group/Virginia Tech/Engineering/Industrial and Systems Engineeringen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
1802.08372v1.pdf
Size:
270.5 KB
Format:
Adobe Portable Document Format
Description:
Submitted Version
Download
License bundle
Now showing 1 - 1 of 1
Name:
VTUL_Distribution_License_2016_05_09.pdf
Size:
18.09 KB
Format:
Adobe Portable Document Format
Description:
Download

Collections

All Faculty Deposits
Scholarly Works, Industrial and Systems Engineering