# Solving regularized least squares problem using black-box computation of $\mathbf{A}\mathbf{x}$ and $\mathbf{A}^T\mathbf{x}$

Let $$\mathbf{A} \in \mathbb{R}^{n \times n}$$. I'm working in a problem where I have a black-box algorithmic solution to compute the products $$\mathbf{A}\mathbf{x}$$ and $$\mathbf{A}^T \mathbf{x}$$ given an input $$\mathbf{x} \in \mathbb{R}^n$$. Knowing that I can't access the value of $$\mathbf{A}$$ directly, what are some examples of algorithms for solving the regularized linear least square problem

\begin{align} \min_{\mathbf{x}} \frac{1}{2} \| \mathbf{y} - \mathbf{A} \mathbf{x}\|^2 + \lambda \phi(\mathbf{x}) \end{align}

that only rely in the computation of $$\mathbf{A}\mathbf{x}$$ and $$\mathbf{A}^T\mathbf{x}$$? Here, $$\lambda >0$$ is a given regularization parameter. I'm more interested in the likelihood $$\frac12 \|\mathbf{y} - \mathbf{A} \mathbf{x}\|^2$$ updates so we can assume pretty much anything we want for $$\phi$$ for the sake of this question. If it makes the problem more concrete, you can assume that $$\phi$$ is convex lower semicontinuous, so that $$\text{prox}_{\lambda\phi}$$ exists and is single valued.

For instance, if $$\phi$$ is differentiable, given a stepsize $$\mu>0$$, the gradient descent update \begin{align} \mathbf{x}^{i+1} &= \mathbf{x^i} - \mu \mathbf{A}^T(\mathbf{A}\mathbf{x^i} - \mathbf{y}) - \mu \lambda \nabla \phi(\mathbf{x^i}) \end{align} can be implemented in my system. What are some other examples?

EDIT: If it makes it more concrete, the prior $$\phi$$ of my problem is the total variation function for 2d signals.

• You will get better answers at or.stackexchange.com Apr 8, 2023 at 20:49
• thank you very much!
– mlbj
Apr 8, 2023 at 21:25
• @mlbj, Could you share $\phi \left( \cdot \right)$?
– Royi
Apr 9, 2023 at 8:38
• @Royi $\phi$ is the total variation function in my problem, so I believe a method that works for generic convex lsc prior would work.
– mlbj
Apr 9, 2023 at 12:21
• @mlbj, I gave you the answers for the general cases. Now that we know the regularization things are easier. Could you add that to the question? Is your problem about 2D signals or 1D signals?
– Royi
Apr 9, 2023 at 12:24

## 1 Answer

If the problem is only given by:

$$\arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2}$$

Then you can use the Conjugate Gradient (Or even better, Preconditioned Conjugate Gradient).

For instance, if $$A$$ stands for convolution matrix, in practice all you need is convolution and correlation.
See my answer and MATLAB code at Automatic Image Enhancement of Images of Scanned Documents (Auto Whitening).

For the regularized problem we need to know more on $$\phi \left ( \cdot \right)$$.
If it is a projection onto a convex set, you may use the alternating projection method. If it is a quadratic function of $$\boldsymbol{x}$$ you may use some specialized solvers.

I also think that the ADMM can also work in some cases.

• I wrote down the ADMM iterations, but then get a term the needs the calculation of $(A^TA + \mu I)^{-1}$, where $I$ is the identity matrix, and I am not able to compute it, since I only know how to operate $A$ and $A^T$ on a vector $x$.
– mlbj
Apr 9, 2023 at 12:25
• $A$ is related to 2d convolution, but it is not exactly circulant nor doubly block circulant. Actually, if you want specifics, $A$ is a sum of several diagonal times doubly block circulant factors. I wrote a question in math.stackexchange.com/questions/4675207/… with the complete specification, but couldn't get anything yet.
– mlbj
Apr 9, 2023 at 12:31
• The question to your answer depends on the fact whether you have an efficient prox() for $\phi \left( \boldsymbol{x} \right)$. Pay attention that we don't have an efficient prox() for $\phi \left( \boldsymbol{x} \right) = {\left\| D x \right\|}_{1}$ if we did, then your question would be easy.
– Royi
Apr 9, 2023 at 19:46
• @mlbj, You may find this interesting: dsp.stackexchange.com/questions/87500.
– Royi
Apr 13, 2023 at 6:10
• @mlbj, You may also have a look at dsp.stackexchange.com/questions/87542.
– Royi
Apr 16, 2023 at 7:35