Multivariate Least-Quantile Squares Estimator

Given a set P={p1,,pn}P = \{p_1, \dots, p_n\} of points in Rd\mathbb R^d, where pi=(xi,1,xi,2,,xi,d)p_i = (x_{i, 1}, x_{i, 2}, \dots, x_{i, d}), and a parameter d+1knd+1\leq k\leq n, compute the parameter vector θ=(θ1,θ2,,θd)\theta = (\theta_1, \theta_2, \dots, \theta_d) that minimizes the kkth smallest squared residual (where a residual is defined as xi,d(xi,1θ1++xi,d1θd1+θd)x_{i, d}-(x_{i, 1}\theta_1 + \dots + x_{i, d-1}\theta_{d-1} + \theta_d)).

Parameters

  • nn: number of points in PP
  • dd: dimension of points
  • kk: quantile parameter

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table