Suppose $\Omega \subset \Bbb R^n$ be a domain such that $|\Omega|<\infty$, $f\in L^1(\Omega)$. Let $Y= \text{span}\{g_1,\dots, g_k\}$.

Is there a characterization of the set of projections of $f$ onto $Y$, i.e. the set $M$ of all $g\in Y$ such that $$ \int_\Omega |f(x) - g(x)|dx = \inf_{h\in Y} \int_\Omega |f(x) - h(x)|dx, $$ or, equivalently, $M = \text{argmin} \{ \int_\Omega |f(x) - g(x)|dx : g \in Y\}$?

Similar problem in $L^2$ (minimizing $\int_\Omega |f(x) - g(x)|^2 dx$) is very easy to solve since we have inner product there. However, as $L^1$ norm is not strictly convex, our set $M$ need to contain a unique element in general.

The solution to the $1$-dimensional case $Y = \text{span}\{1\}$ is well known, i.e. $g=c$ where $c\in \Bbb R$ is any median of $f$. Is there a complete treatment of this kind of problem anywhere?

Thank you in advance.

  • $\begingroup$ You have the same property: for every $g'\in Y$, the sets where $(f-g)g'> 0$ and $(f-g)g'<0$ have measure at most $\frac12|\Omega|$ but I'm not sure if that can be called a "characterization": it is not easy to verify except in the most trivial cases. What are you really after? $\endgroup$ – fedja May 14 at 14:49
  • $\begingroup$ @fedja Knowing general properties of $M$ would be a starter, e.g. if it is closed, convex, $G_\delta$ etc. I do agree that the property you mentioned seems hard to verify. Regardless, I still find it quite interesting. Do you perhaps have a reference to that or something similar that I could read? $\endgroup$ – BigbearZzz May 14 at 14:55
  • $\begingroup$ Closed and convex are (almost) obvious properties. The property I mentioned follows from looking at what happens if you add $g'$ to $g$ (assuming that everything is real valued). As I said, what may be useful to you depends on what you really want. $\endgroup$ – fedja May 14 at 15:03
  • 2
    $\begingroup$ @fedja What I'm looking for is a somewhat effective way to actually compute the projection like how we compute $L^2$ projection. Computing need not mean an explicit formula. A fixed point iteration or a method to find a sequence that converges to a solution would be fine. $\endgroup$ – BigbearZzz May 14 at 15:10
  • 1
    $\begingroup$ I talked to our numerical analysis professor and he said something about alternating direction method of multipliers (ADMM). You may want to look it up and see if it gives you anything useful. As of now, I'd rather wait for what MO numerical experts say before thinking of how I would approach the problem myself... $\endgroup$ – fedja May 14 at 17:01

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.