First of all I would like to thank everyone over here at mathoverflow for their amazing generosity and help (for both pros and newbies like myself).

I apologize if this question seems dumb; I'm a new masters student trying to learn this topic.

I'm performing a LASSO optimization:

$\min ||\mathbf{A}x - b||_2 \; \; \; \; \mathrm{subject\:to} \;\;\; ||x||_1 \leq \tau$

I'm solving this numerically using a spectral projected gradient solver ("SPGL1", specifically), which requires two matrices $\mathbf{A}$ and $\mathbf{A}^*$ (conjugate transpose).

Because of the large-size of the problem, I'm not representing $\mathbf{A}$ as an explicit matrix. Instead, I'm writing a function in my code that returns the values of the products $\mathbf{A}x$ and $\mathbf{A}^*r$.

$x$ is the vectorization of an original data matrix $\mathbf{X}$ : $x = vec(\mathbf{X})$.

My code that returns $\mathbf{A}x$ can be expressed as follows:

$\mathbf{A}x = \mathbf{R} \, \mathbf{\mathcal{F}}^{-1} (\mathbf{D} \circ \mathbf{S} \circ (\mathcal{F}\mathbf{X}))$

where $\circ$ is the Hadamard product, $\mathbf{R}, \mathbf{S}$ and $\mathbf{D}$ are explicit matrices that I have, and $\mathcal{F}$ is the Fourier transform.

Now to the question:

How can I obtain $\mathbf{A}$ from the above equation in order to define an expression for $\mathbf{A}^*$?

My initial attempt was as follows:

$x^* \mathbf{A}^* = (\mathbf{D}^* \circ \mathbf{S}^* \circ (\mathbf{X}^* \mathcal{F}^{-1})) \; \mathcal{F} \; \mathbf{R}^*$

but I'm clueless as to how to isolate $\mathbf{A}^*$ such that it can be passed to the SPGL solver to perform the implicit matrix multiplication $\mathbf{A}^*r$. Note that I can not afford to store $\mathcal{F}$ as an explicit matrix.

Thank you for your help. Any ideas or suggestions are greatly appreciated.

• I could not parse your definition of the operator A. If D and S are matrices, do you build the Hadamard product with the matrix of the Fourier transform? – Dirk Mar 26 '15 at 20:14
• Hi Dirk... Yes, I take the Fourier transform of x, then perform a Hadamard product of that with D and S – M.Salem Mar 26 '15 at 20:50
• Err... So x is a matrix? – Dirk Mar 26 '15 at 20:51
• well, actually $x$ is a vectorization of an original multidimensional matrix: $x = vec(\hat{x})$ ... so $x$ is a vector not a matrix; and in my code I do the necessary reshaping (from vector to matirx form) whenever necessary – M.Salem Mar 26 '15 at 20:54
• Sorry, but this does not make sense. What is the Hadamard product of the matrix S and the vector Fx? – Dirk Mar 26 '15 at 21:04