1
$\begingroup$

First time poster...apologies for formatting.

I am trying to devise a solution to a familiar linear algebra equation, Ax=b, where all elements in A are non-negative and all the elements in b are positive. My constraint is that the difference between the L1 norm of Ax and L1 norm of b must be minimized (ie min (||Ax||_1 - ||b||_1)). In english, I want the coefficients that make the sum of the elements in b "closest" to the sum of the elements in Ax.

Hoping to find out whether there is an algorithmic solution to this problem, preferably in Python.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Are you sure that is the objective? If it is, an optimal solution is $x=0$. If you meant to minimize $\left|\|Ax\|_1 - \|b\|_1\right|$, just take any $y$ with $Ay \ne 0$ and let $x = \dfrac{\|b\|_1}{\|Ay\|_1 }y$ to make the objective value $0$. Or did you mean to minimize $\|Ax - b \|_1$? $\endgroup$
    – Robert Israel
    Commented Apr 18, 2019 at 21:16
  • $\begingroup$ Thanks @RobertIsrael. I do want \begin{equation} |||Ax||_1 - ||b||_1|_1 \end{equation}. (the other would be l1 regression). The solution you proposed gives x as a scalar, correct? x is a vector, though. Rusty in my linear algebra, been quite a few years. Much appreciate the help $\endgroup$
    – Jason
    Commented Apr 18, 2019 at 21:25
  • $\begingroup$ For more context...Suppose I'm in retail and I sell a number of SKUs that are oftentimes sold together. Each x is the cost of an individual SKU, but is unknown because of said bundling. The costs are a function of what's in A (which has M buyers of N SKUs), and b is the total dollars for each of my buyers. I want to find the average cost for each SKU. $\endgroup$
    – Jason
    Commented Apr 18, 2019 at 21:33
  • 2
    $\begingroup$ No, $x$ is a vector, as is $y$. $y$ is any vector such that $Ay \ne 0$. Then you scale $y$, i.e. multiply it by a scalar, chosen to make $\|Ax\|_1$ equal to $\|b\|_1$. $\endgroup$
    – Robert Israel
    Commented Apr 18, 2019 at 22:02
  • $\begingroup$ I don't understand the question. Perhaps what you mean is that for given $A$ and $b$, you want to find some $x$, such that $\|Ax-b\|_1$ becomes minimal? $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Apr 19, 2019 at 9:28

0

Reset to default

Browse other questions tagged .