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.


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.


There is a solution to your problem:


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

  • $\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 '14 at 20:57
  • $\begingroup$ What are the dimensions of $x$, $A$ and $D$? $\endgroup$ – The Pheromone Kid Jun 8 '14 at 22:16
  • $\begingroup$ Moreover, do you use matlab or python to solve the problem? $\endgroup$ – The Pheromone Kid Jun 10 '14 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.