Timeline for When does the metric projection operator have a closed form?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 15, 2021 at 16:34 | comment | added | dohmatob | Hum, any reference for this statement ? Also ,what "active set" are you talking about ? Remember, the question is about projection onto a closed convex set in an arbitrary Hilbert space. | |
| May 15, 2021 at 14:29 | comment | added | Richard Zhang | @dohmatob a numerical algorithm can find an exact solution, rather than simply an $\epsilon$-accurate one, in $O(n^{3.5})$ time. This is by rounding off the solution once $\epsilon$ is sufficiently small to reveal the active set. | |
| May 15, 2021 at 6:34 | comment | added | dohmatob | @EldacarHyarmendacil Short answer is No. Indeed, think of the proxy question Does $C$ contain the origin ? You can certainly form a convex set $C$ descriptively (say, defined as the intersection of infiitely many abstractly defined convex sets), for which the answer to that question is not the truth value of a predicate with an "analytic" form. | |
| May 15, 2021 at 6:31 | comment | added | dohmatob | @RichardZhang What do you mean by Exactly ? | |
| May 14, 2021 at 23:28 | comment | added | Richard Zhang | Say $C$ is a polytope, like a cube or a tetrahedron, in $n$-dimensions. Then the closed-form solution is to exhaustively enumerate all the corners, but most polytopes have an exponential number of corners (e.g. a hypercube has $2^n$ corners). On the other hand, a numerical algorithm can exactly solve this projection as a quadratic program in $n^{3.5}$ time. Why look for a closed-form solution? | |
| May 14, 2021 at 22:16 | comment | added | Sin Nombre | That is one way to sharpen the question. yes | |
| May 14, 2021 at 22:14 | comment | added | alvarezpaiva | So the question is "for what convex bodies in a Hilbert space, besides affine subspaces and quadrics, does the projection function admit a closed form?" ? | |
| May 14, 2021 at 21:50 | comment | added | Sin Nombre | @alvarezpaiva Ok. I am asking because currently what I see in optimization related research is a disclaimer: "$C$ has to be simple", but I do not quite understand what types of sets this "simple" definition encompass. | |
| May 14, 2021 at 21:44 | comment | added | alvarezpaiva | In finite dimensions at least the formula for the distance to an ellipsoid is known. They use this quite a bit in geodesy. | |
| May 14, 2021 at 21:16 | history | asked | Sin Nombre | CC BY-SA 4.0 |