1
$\begingroup$

Given a vector $x \in \mathbb{R}^{n}_{0+}$ such that $x = \sum^{k}_{i=1} \alpha_{i}v_{i}$, the vectors $(v_{1},...,v_{k}) \in \mathbb{R}^{n}_{0+}$ are an independent set, $k < n$, and $\alpha_{i} > 0$, it can be seen by simple combinatorial argument that for at least one vector $v_{i}$, $\frac{||x - \alpha_{i}v_{i}||_{2}}{||x||_{2}} \geq \frac{1}{k}$ (assume the opposite, then we have that the maximum value of $\frac{||x - \alpha_{i}v_{i}||_{2}}{||x||_{2}} < \frac{1}{k}$ but this implies that $||x - \sum^{k}_{i=1} \alpha_{i}v_{i}||_{2} > 0$ which is a contradiction).

Say we have an additional vector $y \in \mathbb{R}^{n}_{0+}$ such that $(v_{1},...,v_{k},y)$ is an independent set. What can be said about $\frac{||x - \beta y||_{2}}{||x||_{2}}$ where $\beta$ is the result of minimizing $||x-y\beta||_{2}$ subject to $\beta \geq 0$? If $(v_{1},...,v_{k},y)$ is orthogonal then $\frac{||x - \beta y||_{2}}{||x||_{2}} = 1$, but bounds in the absence of orthogonality don't seem as obvious. If we impose the additional requirement that $x - y\beta \geq 0$ element-wise are there stronger conclusions that can be drawn?

P.S. Apologies if the title I chose for this question is not perfectly representative of what I actually asked, I was unable to determine if there is a common technical term for this sort of question.

EDIT: Removed silly equivocation about the case when $(v_{1},...,v_{k},y)$ is orthogonal.

EDIT 2: Further research revealed a flaw in the reasoning presented here. I'm in the process of reformulating the question and examining if I can come to any conclusions myself in the meantime. I may repost at a later date if I can't make further progress, but as written here this question is ill-posed.

$\endgroup$
  • $\begingroup$ I don't get your point concerning orthogonality. If $(v_1,\ldots,v_k,y)$ is orthogonal, then $x$ is orthogonal to $y$. This implies $\beta = 0$. Thus, $\|x -\beta\,y\|/\|x\| = 1$? $\endgroup$ – gerw Feb 6 '19 at 12:47
  • $\begingroup$ Yes, I was equivocating when I wrote the post in case I missed something stupid (and in the process wrote something vacuously true). I'll edit that section accordingly. $\endgroup$ – nick.schachter Feb 6 '19 at 15:08
  • $\begingroup$ You have written "=0", but it should be "=1"? $\endgroup$ – gerw Feb 6 '19 at 15:19
  • $\begingroup$ Just fixed it, thanks for the heads up. $\endgroup$ – nick.schachter Feb 6 '19 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.