2
$\begingroup$

I am interested in the linear least square problem with the solution constrained to the closed standard simplex:

$$ \min_x \|Ax-b\|^2$$ subject to $x_i \ge 0$ and $\| x \|_1 = 1$.

More precisely, I want to know which conditions on $A$ provides a unique solution to the problem.

I found conditions on the rank of $A$ for equality constraints from chapter 5 of Numerical methods for least square problems by Ake Bjorck, but I don't know if they apply to my case.

$\endgroup$
1
$\begingroup$

Since $x_i \ge 0$, $\|x\|_1 = \sum_i x_i$, and the feasible region is convex (in fact a simplex). If $A$ is injective on $L = \{u: \sum_i u_i = 0\}$, the objective is strictly convex so the minimizer is unique. On the other hand, in order for the minimizer $p$ to be unique there can't be any nonzero $u \in L$ with $Au = 0$ and $p+u$ feasible. Thus if $u \in L$ and $Au = 0$ there must be some index $i$ such that $p_i = 0$ and $u_i < 0$ (so that $p + t u$ is infeasible for all $t > 0$) and some $i$ such that $p_i = 0$ and $u_i > 0$ (so that $p + t u$ is infeasible for all $t < 0$).

$\endgroup$
0
$\begingroup$

Start the linear system $$ \mathbf{A} x = b, $$ where $$ \mathbf{A}\in\mathbb{C}^{m\times n}, \ b\in\mathbb{C}^{m}, \ x\in\mathbb{C}^{n}. $$ When $b\notin\mathcal{N}\left( \mathbf{A}^{*} \right)$, the least squares solution exists and is given by $$ x_{LS} = \mathbf{A}^{\dagger} + \left( \mathbf{I}_{n} + \mathbf{A}^{\dagger}\mathbf{A}\right) y $$ where the arbitrary vector $y\in\mathbb{C}^{n}$ and $\mathbf{A}^{\dagger}$ is the Moore-Penrose pseudoinverse.

When $\mathbf{A}$ has full column rank (number of columns $n$ is the same as the matrix rank $\rho$), then the null space $\mathcal{N}\left( \mathbf{A} \right)$ is trivial and $$ \mathbf{A}^{\dagger}\mathbf{A} = \mathbf{I}_{n}, $$ and the least squares solution is a point. That is, the solution is unique.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.