{"604798":{"#nid":"604798","#data":{"type":"event","title":"Fully Approximation algorithms for optimal design problems ","body":[{"value":"\u003Cp\u003EACO Student Seminar - Uthaipon (Tao) Tantipongpipat\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAbstract:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWe study the $A$-optimal design problem where we are given vectors $v_1,\\ldots, v_n\\in \\R^d$, an integer $k\\geq d$, and the goal is to select a set $S$ of $k$ vectors that minimizes the trace of $\\left(\\sum_{i\\in\u0026nbsp; S} v_i v_i^{\\top}\\right)^{-1}$. Traditionally, the problem is an instance of optimal design of experiments in statistics (\\cite{pukelsheim2006optimal}) where each vector corresponds to a linear measurement of an unknown vector and the goal is to pick $k$ of them that minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. The problem also finds applications in sensor placement in wireless networks~(\\cite{joshi2009sensor}), sparse least squares regression~(\\cite{BoutsidisDM11}), feature selection for $k$-means clustering~(\\cite{boutsidis2013deterministic}), and matrix approximation~(\\cite{de2007subset,de2011note,avron2013faster}). In this paper, we introduce \\emph{proportional volume sampling} to obtain improved approximation algorithms for $A$-optimal design.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nGiven a matrix, proportional volume sampling involves picking a set of columns $S$ of size $k$ with probability proportional to $\\mu(S)$ times $\\det(\\sum_{i \\in S}v_i v_i^\\top)$ for some measure $\\mu$. Our main result is to show the approximability of the $A$-optimal design problem can be reduced to \\emph{approximate} independence properties of the measure $\\mu$. We appeal to hard-core distributions as candidate distributions $\\mu$ that allow us to obtain improved approximation algorithms for the $A$-optimal design. Our results include a $d$-approximation when $k=d$, an $(1+\\epsilon)$-approximation when $k=\\Omega\\left(\\frac{d}{\\epsilon}+\\frac{1}{\\epsilon^2}\\log\\frac{1}{\\epsilon}\\right)$ and $\\frac{k}{k-d+1}$-approximation when repetitions of vectors are allowed in the solution. We also consider generalization of the problem for $k\\leq d$ and obtain a $k$-approximation. The last result also implies a restricted invertibility principle for the harmonic mean of singular values.\u0026nbsp; We also show that the $A$-optimal design problem is $\\NP$-hard to approximate within a fixed constant when $k=d$.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cbr \/\u003E\r\n\u0026nbsp;\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EAbstract:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWe study the $A$-optimal design problem where we are given vectors $v_1,\\ldots, v_n\\in \\R^d$, an integer $k\\geq d$, and the goal is to select a set $S$ of $k$ vectors that minimizes the trace of $\\left(\\sum_{i\\in\u0026nbsp; S} v_i v_i^{\\top}\\right)^{-1}$. Traditionally, the problem is an instance of optimal design of experiments in statistics (\\cite{pukelsheim2006optimal}) where each vector corresponds to a linear measurement of an unknown vector and the goal is to pick $k$ of them that minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. The problem also finds applications in sensor placement in wireless networks~(\\cite{joshi2009sensor}), sparse least squares regression~(\\cite{BoutsidisDM11}), feature selection for $k$-means clustering~(\\cite{boutsidis2013deterministic}), and matrix approximation~(\\cite{de2007subset,de2011note,avron2013faster}). In this paper, we introduce \\emph{proportional volume sampling} to obtain improved approximation algorithms for $A$-optimal design.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nGiven a matrix, proportional volume sampling involves picking a set of columns $S$ of size $k$ with probability proportional to $\\mu(S)$ times $\\det(\\sum_{i \\in S}v_i v_i^\\top)$ for some measure $\\mu$. Our main result is to show the approximability of the $A$-optimal design problem can be reduced to \\emph{approximate} independence properties of the measure $\\mu$. We appeal to hard-core distributions as candidate distributions $\\mu$ that allow us to obtain improved approximation algorithms for the $A$-optimal design. Our results include a $d$-approximation when $k=d$, an $(1+\\epsilon)$-approximation when $k=\\Omega\\left(\\frac{d}{\\epsilon}+\\frac{1}{\\epsilon^2}\\log\\frac{1}{\\epsilon}\\right)$ and $\\frac{k}{k-d+1}$-approximation when repetitions of vectors are allowed in the solution. We also consider generalization of the problem for $k\\leq d$ and obtain a $k$-approximation. The last result also implies a restricted invertibility principle for the harmonic mean of singular values.\u0026nbsp; We also show that the $A$-optimal design problem is $\\NP$-hard to approximate within a fixed constant when $k=d$.\u003C\/p\u003E\r\n","format":"limited_html"}],"field_summary_sentence":[{"value":"ACO Student Seminar - Uthaipon (Tao) Tantipongpipat"}],"uid":"27628","created_gmt":"2018-04-06 12:02:20","changed_gmt":"2018-04-09 19:43:52","author":"Kathy Huggins","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-04-06T14:00:00-04:00","event_time_end":"2018-04-06T15:00:00-04:00","event_time_end_last":"2018-04-06T15:00:00-04:00","gmt_time_start":"2018-04-06 18:00:00","gmt_time_end":"2018-04-06 19:00:00","gmt_time_end_last":"2018-04-06 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"602673","name":"TRIAD "}],"categories":[],"keywords":[{"id":"177641","name":"Approximation"},{"id":"5660","name":"algorithms"},{"id":"177642","name":"opimal design"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}