Skip to main content
MathOverflow

Return to Answer

added 5 characters in body
Source Link
Dieter Kadelka
Dieter Kadelka
  • 2.1k
  • 2
  • 11
  • 15

For this special case an explicit solution is possible. To simplify notation let $A := \Sigma^{1/2}$ and let $A^+$ be the pseudoinverse of $A$ (see f.i. Golub/Van Loan: Matrix Computations (1996), 3rd ed., p. 257). Let $y := Ax$, $z := (E - A^+A)x$, thus $x = A^+y +z$ and the problem is $$p^T(A^+y + z) = max!\\p^T(A^+y+z) + \Phi^{-1}(\beta) \cdot \sqrt{y^TAA^+y} \geq \alpha,$$ since $Az = 0$ and $(AA^+y)^T(AA^+y) = y^TAA^+y$. Now assume that $\beta < 0.5$ (the case $\beta = 0.5$ is uninteresting since then $\Phi^{-1}(\beta) = 0$). Let $F$ be the image of $x \to Ax$ and $\mathbb{R}^n = F+G$, $G$ a subspace. If there is some $z \in G$ with $p^T z \not= 0$, then the problem is unsolvable (take $y = 0$ and $x = \lambda z$ with either $\lambda < 0$ or $\lambda > 0$). Of course this only can happen if $A$ is singular.

Now we can assume w.l.o.g. that $A$ is non-singular. Then $AA^+ = E$, the identity matrix and always $z = 0$. Let $q := (A^+)^Tp$, then the problem is $$q^T y = max!\\q^T y + \Phi^{-1}(\beta) \cdot \sqrt{y^Ty} \geq \alpha$$ This problem is much easier to solve. Simply let $y = \lambda q$. Then the problem is $$\lambda = max!\\ \lambda q^Tq + \Phi^{-1}(\beta) \cdot |\lambda| \cdot \|q\|_2 \geq \alpha$$$$\lambda q^Tq = max!\\ \lambda q^Tq + \Phi^{-1}(\beta) \cdot |\lambda| \cdot \|q\|_2 \geq \alpha$$ Which can be solved directly. Also general cases (singular $A$), which are solvable, can be reduced to this special case.

For this special case an explicit solution is possible. To simplify notation let $A := \Sigma^{1/2}$ and let $A^+$ be the pseudoinverse of $A$ (see f.i. Golub/Van Loan: Matrix Computations (1996), 3rd ed., p. 257). Let $y := Ax$, $z := (E - A^+A)x$, thus $x = A^+y +z$ and the problem is $$p^T(A^+y + z) = max!\\p^T(A^+y+z) + \Phi^{-1}(\beta) \cdot \sqrt{y^TAA^+y} \geq \alpha,$$ since $Az = 0$ and $(AA^+y)^T(AA^+y) = y^TAA^+y$. Now assume that $\beta < 0.5$ (the case $\beta = 0.5$ is uninteresting since then $\Phi^{-1}(\beta) = 0$). Let $F$ be the image of $x \to Ax$ and $\mathbb{R}^n = F+G$, $G$ a subspace. If there is some $z \in G$ with $p^T z \not= 0$, then the problem is unsolvable (take $y = 0$ and $x = \lambda z$ with either $\lambda < 0$ or $\lambda > 0$). Of course this only can happen if $A$ is singular.

Now we can assume w.l.o.g. that $A$ is non-singular. Then $AA^+ = E$, the identity matrix and always $z = 0$. Let $q := (A^+)^Tp$, then the problem is $$q^T y = max!\\q^T y + \Phi^{-1}(\beta) \cdot \sqrt{y^Ty} \geq \alpha$$ This problem is much easier to solve. Simply let $y = \lambda q$. Then the problem is $$\lambda = max!\\ \lambda q^Tq + \Phi^{-1}(\beta) \cdot |\lambda| \cdot \|q\|_2 \geq \alpha$$ Which can be solved directly. Also general cases (singular $A$), which are solvable, can be reduced to this special case.

For this special case an explicit solution is possible. To simplify notation let $A := \Sigma^{1/2}$ and let $A^+$ be the pseudoinverse of $A$ (see f.i. Golub/Van Loan: Matrix Computations (1996), 3rd ed., p. 257). Let $y := Ax$, $z := (E - A^+A)x$, thus $x = A^+y +z$ and the problem is $$p^T(A^+y + z) = max!\\p^T(A^+y+z) + \Phi^{-1}(\beta) \cdot \sqrt{y^TAA^+y} \geq \alpha,$$ since $Az = 0$ and $(AA^+y)^T(AA^+y) = y^TAA^+y$. Now assume that $\beta < 0.5$ (the case $\beta = 0.5$ is uninteresting since then $\Phi^{-1}(\beta) = 0$). Let $F$ be the image of $x \to Ax$ and $\mathbb{R}^n = F+G$, $G$ a subspace. If there is some $z \in G$ with $p^T z \not= 0$, then the problem is unsolvable (take $y = 0$ and $x = \lambda z$ with either $\lambda < 0$ or $\lambda > 0$). Of course this only can happen if $A$ is singular.

Now we can assume w.l.o.g. that $A$ is non-singular. Then $AA^+ = E$, the identity matrix and always $z = 0$. Let $q := (A^+)^Tp$, then the problem is $$q^T y = max!\\q^T y + \Phi^{-1}(\beta) \cdot \sqrt{y^Ty} \geq \alpha$$ This problem is much easier to solve. Simply let $y = \lambda q$. Then the problem is $$\lambda q^Tq = max!\\ \lambda q^Tq + \Phi^{-1}(\beta) \cdot |\lambda| \cdot \|q\|_2 \geq \alpha$$ Which can be solved directly. Also general cases (singular $A$), which are solvable, can be reduced to this special case.

Source Link
Dieter Kadelka
Dieter Kadelka
  • 2.1k
  • 2
  • 11
  • 15

For this special case an explicit solution is possible. To simplify notation let $A := \Sigma^{1/2}$ and let $A^+$ be the pseudoinverse of $A$ (see f.i. Golub/Van Loan: Matrix Computations (1996), 3rd ed., p. 257). Let $y := Ax$, $z := (E - A^+A)x$, thus $x = A^+y +z$ and the problem is $$p^T(A^+y + z) = max!\\p^T(A^+y+z) + \Phi^{-1}(\beta) \cdot \sqrt{y^TAA^+y} \geq \alpha,$$ since $Az = 0$ and $(AA^+y)^T(AA^+y) = y^TAA^+y$. Now assume that $\beta < 0.5$ (the case $\beta = 0.5$ is uninteresting since then $\Phi^{-1}(\beta) = 0$). Let $F$ be the image of $x \to Ax$ and $\mathbb{R}^n = F+G$, $G$ a subspace. If there is some $z \in G$ with $p^T z \not= 0$, then the problem is unsolvable (take $y = 0$ and $x = \lambda z$ with either $\lambda < 0$ or $\lambda > 0$). Of course this only can happen if $A$ is singular.

Now we can assume w.l.o.g. that $A$ is non-singular. Then $AA^+ = E$, the identity matrix and always $z = 0$. Let $q := (A^+)^Tp$, then the problem is $$q^T y = max!\\q^T y + \Phi^{-1}(\beta) \cdot \sqrt{y^Ty} \geq \alpha$$ This problem is much easier to solve. Simply let $y = \lambda q$. Then the problem is $$\lambda = max!\\ \lambda q^Tq + \Phi^{-1}(\beta) \cdot |\lambda| \cdot \|q\|_2 \geq \alpha$$ Which can be solved directly. Also general cases (singular $A$), which are solvable, can be reduced to this special case.