I have a problem that in some ways is quite simple and in other ways is quite hard. I feel that there is probably an algorithm out there that is better suited to solving my problem than the one I am currently using (active set line search from the NMath library for C#). I imagine the structure of it could be exploited to solve the problem in an efficient way, but I haven't managed to find anything online.
The basic outline of the problem is as follows. I have a matrix $A$ and a vector $b$ and I want to find another vector $x$ such that $A \cdot x$ is very close to $b$ ($|Ax-b|$ within a pre-defined tolerance for example), while also minimising $|x-y|$ where $y$ is some other vector that I know. The matrix $A$ is relatively sparse and maps from $\mathbb{R}^{52} \to \mathbb{R}^{12}$. Each row of the matrix has 4-5 non-zero entries and they are located along the 'diagonal'. I write 'diagonal' because as the matrix is not square it's not really the diagonal I am referring to, but rather an imaginary line from the (1,1) element to the (12,52) element.
I have expressed the problem is a least squares minimisation subject to the constraints that $A \cdot w = b \pm \varepsilon$, where $w$ is the candidate solution. This effectively leads to a minimisation of $|w-y|$ with 12 linear constraint equations.
Given the relatively sparsity of $A$ is there an efficient method for solving this problem? Please feel free to clarify anything that I haven't explained clearly enough.
Thanks for your help
You might consider solving your problem as follows: find $x$ such that $$ |b-Ax|^2 + \lambda^2|x-y|^2=\min_{x} $$ for some scaling parameter $\lambda>0$. By choosing a proper $\lambda$, you might put more "preference" to minimizing the norm of $b-Ax$ or the norm of $x-y$. This is equivalent to solving the least squares problem $$ \left| \begin{bmatrix}b \\ \lambda y\end{bmatrix} -\begin{bmatrix}A\\\lambda I\end{bmatrix} x \right|=\min_{x} $$ and is recognized as a special form of the Tikhonov regularization in the context of ill-posed problems.
Even though your problem is sparse, the dimensions are quite small so I would not hesitate to treat the problem as if the matrix $A$ (and everything else) was dense.