2
$\begingroup$

I have matrix $A$ that is $(M \times M)$ square matrix, $x$ $(M \times N)$ matrix, $b$ is $(M \times N)$ matrix. Knowing $A$ and $b$ I would like to get the $x$ from the equation $Ax=b$. $N=p \times q$, so consider $x$ as an $M$ number of $p \times q$ pixel images. These images are sparse when we take total variational $TV(x)$. I would like to solve the following minimization problem for $x$;

Define an operator $g(x)=\parallel x^T\parallel_2,$ or $g(x)=\parallel x^T\parallel_1,$ that maps $M \times N \mapsto N \times 1$.

$$\min \frac{1}{2}\parallel Ax-b\parallel^2_2+k\parallel z\parallel_1,$$ subject to $Fg(x)-z=0$.

$F$ is the difference matrix to take numerical gradient of pixels.

Unlike in the deblurring+denoising problem, my matrix $A$ and $x$ are in different sizes.

The ADMM (Alternating Direction Method of Multipliers) solution to my minimization problem is given as:

$$x^{k+1}=(A^TA+pF^TF)^{-1}(A^Tb+pF^T(z^k-u^k))$$

$$z^{k+1}=S_{t/p}(Fx^{k+1}+u^{k})$$

$$u^{k+1}=u^k+Fx^{k+1}-z^{k+1}$$

When calculating $x^{k+1}$ the matrix dimensions are not compatible in my case. Gradient matris should be applied to total number of pixels $N$, $F$ matrix should have $N$ columns. So the term $(A^TA+pF^TF)$ is not proper way to add 2 matrices.

How can I overcome this and find a solution to my problem?

$\endgroup$
10
  • $\begingroup$ Which matrix multiplication exactly causes the dimension mismatch? At first glance they do look okay. $p$ is a scalar, right? $\endgroup$ – Florian Mar 3 '20 at 7:51
  • $\begingroup$ Yes $p$ is scalar. The dimension mismatch is addition of $A^TA$ and $F^TF$. $F$ is a scalar gradient operator which should be applied to all pixels of $x$. Since total number of pixels in $x$ is $N$, $F$ should be $NxN$. $\endgroup$ – johanson Mar 3 '20 at 11:10
  • $\begingroup$ @Florian what do you think about my question? $\endgroup$ – johanson Mar 4 '20 at 19:24
  • $\begingroup$ I don't understand the source of mismatch. $A$ multiplies $x$ in your cost function and $F$ multiplies $x$ in your constraint. Hence $A$ and $F$ have the same number of columns. Hence $A^T A$ and $F^T F$ are exactly the same size. $\endgroup$ – Florian Mar 5 '20 at 8:11
  • $\begingroup$ A is not applied to pixels in x. Thats why it is $M \times M$ @Florian $\endgroup$ – johanson Mar 5 '20 at 13:44
1
$\begingroup$

The Error in the Model

The problem is in the dimensions of the Linear Operator $ A $ in your model compared to the Data Matrix $ X $. The number of columns of the matrix $ A $ must match the number of pixels in each column of $ X $ (Each image). While in your case it matches the number of images.

Matrix Form of 2D Linear Operator

Let's try to build the model correctly. Assume our data (Images) is given by the set of 2D matrices $ {\left\{ {X}_{i} \right\}}_{i = 1}^{m} $ where $ {X}_{i} \in \mathbb{R}^{p \times q} $. Given a Linear Operator $ \mathcal{A}: \mathbb{R}^{p \times q} \to \mathbb{R}^{k \times l} $ and we have $ {B}_{i} = \mathcal{A} \left( {X}_{i} \right) $.

In order to create the matrix form we should represent the Linear Operator by the matrix $ A \in \mathbb{R}^{\left( k l \right) \times \left( p q \right)} $ which is the matrix which applies the operator on the Column Stacked (See Vectorization Operator) vectors. So we have $ \boldsymbol{x}_{i} = \operatorname{Vec} \left( {X}_{i} \right) $ and $ \boldsymbol{b}_{i} = \operatorname{Vec} \left( {B}_{i} \right) $.

By defining $ X = \left[ \boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \ldots \boldsymbol{x}_{m} \right] $ and $ B = \left[ \boldsymbol{b}_{1}, \boldsymbol{b}_{2}, \ldots \boldsymbol{b}_{m} \right] $ we have $ A X = B $.

With this definition everything will work as expected. Same logic will work for $ F $.

Remark

If you want $ F $ to work along the rows of $ X $ then set $ Z = F {X}^{T} $.

ADMM for the Vector Case

First, pay attention that the ADMM works on vectors (You can work with Matrices but then you need to update the Prox operations accordingly.

So $ \boldsymbol{x} \in \mathbb{R}^{n}, A \in \mathbb{R}^{m \times n}, \boldsymbol{b} \in \mathbb{R}^{m} $ and $ F \in \mathbb{R}^{o \times n} $ where $ o $ is set to match the operation of TV on the image columns and rows which $ \boldsymbol{x} $ is a column stack of.

So now the terms do align propely: $ {\left( {A}^{T} A + p {F}^{T} F \right)}^{-1} \in \mathbb{R}^{n \times n} $ and $ \left( {A}^{T} \boldsymbol{b} + p {F}^{T} \left( \boldsymbol{x} - \boldsymbol{u} \right) \right) \in \mathbb{R}^{n} $. So the calculation of $ \boldsymbol{x}^{k} $ is well defined.

Given that $ \boldsymbol{z} \in \mathbb{R}^{o} $ and $ \boldsymbol{u} \in \mathbb{R}^{o} $ their calculation is also well defined.

I guess something in your code doesn't match. But if the code have the terms $ A \boldsymbol{x} - \boldsymbol{b} $ and $ F \boldsymbol{x} $ well defined then everything else will work.

$\endgroup$
12
  • $\begingroup$ Yes with dimensions you gave it should work. But I have different dimensions. So how can I solve the problem with matrices that i stated in my question? $\endgroup$ – johanson Mar 3 '20 at 10:48
  • $\begingroup$ It works with your dimensions the same way. Again, once you have $ A X - B $ working and $ F X $ well defined all the rest will work. $\endgroup$ – Royi Mar 3 '20 at 10:51
  • $\begingroup$ Total number of pixels in $x$ is $N$ and I need to apply F to take gradient of pixels values in $x$. So $F$ should be $NxN$ Matrix which cannot add to $A^TA$ because it is $MxM$ $\endgroup$ – johanson Mar 3 '20 at 10:58
  • $\begingroup$ This is what you miss. The right way to do this is column stack the image. If the image is $ p \times q $ then your vector $ \boldsymbol{x} $ has the length $ n = p \times q $. From there follow what's in my answer. $\endgroup$ – Royi Mar 3 '20 at 11:27
  • $\begingroup$ If the image is $p \times q$ my $x$ is $M \times p \times q$. Then taking $N=p \times q$ I can write $x$ as $M x N$. Am I missing anything? $\endgroup$ – johanson Mar 3 '20 at 11:37

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.