2
$\begingroup$

I need to solve the following problem (preferably in python but any other suggestion is welcome)

$$ \min_x||Ax - b||_2 $$ $$ s.t. \: Dx = Dy $$

everything except x is known. $A$ and $D$ are square sparse matrices, $x$,$y$ and $b$ are vectors. From what I understand, without the constrain the problem is solvable using the pseudo-inverse, however I am having trouble incorporating the constrain.

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

There is a solution to your problem:

http://inst.eecs.berkeley.edu/~ee127a/book/login/l_ols_variants.html

To bring your problem to the form they are using, replace $Dy$ by some vector.

$\endgroup$
3
  • $\begingroup$ Thank you very much for your answer. Unfortunately my D matrix is too big to estimate its null space. Is there an alternative maybe using frobenius norms and the pseudo-inverse? $\endgroup$
    – ikassi
    Jun 8, 2014 at 20:57
  • $\begingroup$ What are the dimensions of $x$, $A$ and $D$? $\endgroup$
    – The Pheromone Kid
    Jun 8, 2014 at 22:16
  • $\begingroup$ Moreover, do you use matlab or python to solve the problem? $\endgroup$
    – The Pheromone Kid
    Jun 10, 2014 at 8:10
0
$\begingroup$

The problem is given by:

$$ \begin{alignat*}{3} \arg \min_{x} & \quad & \frac{1}{2} \left\| A x - b \right\|_{2}^{2} \\ \text{subject to} & \quad & D x = e \end{alignat*} $$

Where $ e = D y $.

The Lagrangian is given by:

$$ L \left( x, \nu \right) = \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + {\nu}^{T} \left( D x - e \right) $$

From KKT Conditions the optimal values of $ \hat{x}, \hat{\nu} $ obeys:

$$ \begin{bmatrix} {A}^{T} A & {D}^{T} \\ D & 0 \end{bmatrix} \begin{bmatrix} \hat{x} \\ \hat{\nu} \end{bmatrix} = \begin{bmatrix} {A}^{T} b \\ e \end{bmatrix} $$

Now all needed is to solve the above with any Linear System Solver.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .