Solving a mixture of many random linear equations by tensor decomposition and alternating minimization.

Details

• Alternative Title:
  Project title : models for high dimensional mixed regression.
• Creators:
  Yi, Xinyang ; Caramanis, Constantine ; Sanghavi, Sujay
• Corporate Creators:
  University of Texas at Austin. Data-Supported Transportation Operations & Planning Center (D-STOP)
• Corporate Contributors:
  University Transportation Centers Program (U.S.)
• Subject/TRT Terms:
  • Linear equations
  • Linear regression analysis
  • Tensor analysis
  • Mixed random linear equations
  • mixed linear regression
• Publication/ Report Number:
  D-STOP/2016/109 ; Technical Report 109
• Resource Type:
  Tech Report
• Geographical Coverage:
  United States
• TRIS Online Accession Number:
  1643696
• Corporate Publisher:
  University of Texas at Austin. Data-Supported Transportation Operations & Planning Center (D-STOP)
• Abstract:
  We consider the problem of solving mixed random linear equations with k components. This is the noiseless setting of mixed linear regression. The goal is to estimate multiple linear models from mixed samples in the case where the labels (which sample corresponds to which model) are not observed. We give a tractable algorithm for the mixed linear equation problem, and show that under some technical conditions, our algorithm is guaranteed to solve the problem exactly with sample complexity linear in the dimension, and polynomial in k, the number of components. Previous approaches have required either exponential dependence on k, or super-linear dependence on the dimension. The proposed algorithm is a combination of tensor decomposition and alternating minimization. Our analysis involves proving that the initialization provided by the tensor method allows alternating minimization, which is equivalent to EM in our setting, to converge to the global optimum at a linear rate.
• Format:
  PDF
• Funding:
  DTRT13-G-UTC58
• Download URL:
  https://rosap.ntl.bts.gov/view/dot/32603/dot_32603_DS1.pdf
• File Type:
  [PDF - 1.01 MB]
• Collection(s):
  University Transportation Centers ; US Transportation Collection
• Main Document Checksum:
  urn:sha256:93e752bc466fa18a145d4e7af9afd56539e293cc2d0f930b351dfa5a9d207d21