Geométricas Mediana Problema con un twist

Question

Dados dos vectores $x, y$ $\mathbb{R}^n$ y escalares $\alpha$, ¿cuál es el valor de $\alpha$ que minimiza $||\alpha x - y ||_1$? Dar un algoritmo para encontrar el mínimo.

He intentado un par de ejemplos con la mano, pero no llego a ninguna parte. No es más que el valor de $|\alpha x_i - y_i|$ que domina la función o la mediana. Es allí una manera sistemática para obtener la solución?

Answer 1

La clave para resolver este problema es tener en cuenta que el $\|ax-y\|_1$ es un modelo lineal por tramos, en función convexa de $a$. Cualquier seccionalmente lineales convexas de la función que está delimitado a continuación se minimiza en uno de sus "problemillas" o vértices. Si usted puede identificar la ubicación de los kinks, una simple búsqueda será suficiente.

(Es posible que por tramos lineales convexas de la función para alcanzar su mínimo entre dos kinks; por ejemplo, $f(a)=\max\{|a|-1,0\}$. Pero tenga en cuenta que los dos vértices circundantes son también minimizers. Así que el método de búsqueda es siempre válida.)

Así que ¿dónde están los kinks? En este caso, es exactamente el conjunto de puntos donde la $ax_i-y_i$ cambia de signo: $$a \in \{ y_i / x_i ~|~ i=1,2,\dots, n,~x_i\neq 0\}.$$ Por lo tanto, la solución es $$a = y_q / x_q, \quad q = \mathop{\textrm{argmin}}_{i:x_i\neq 0} \sum_j |x_jy_i/x_i - y_j| .$$ Usted puede buscamos todos los $n$ puntos si se quiere, por $O(n^2)$ complejidad. o usted puede ordenar e iniciar la búsqueda de la mediana del valor de $a$. Que todavía sería $O(n^2)$ peor de los casos.

Answer 2

Esto se reduce a una geometría Euclidiana problema, por la restricción para el subespacio generado por $x$$y$.

dado un polígono convexo $C$ contiene $0$ y una línea en el plano, encontrar el más pequeño de $b$ tal que $bC$ cruza la línea.

Hay dos casos, donde la línea se hace/no se cruzan $C$, que debe ser similar a los tipos que se describen a partir de ejemplos. Nonintersecting caso es el problema de encontrar líneas de apoyo paralela a la dada.