Sparse Matrix Factorization Problem

I am trying to solve the following problem

Is their a name for such sparse factorization or something similar. Can anyone please guide me or refer some text from where I can find methods of solving such problem, or may be modify an existing problem to get this one.

Any help in this regard will be highly appreciated. Thanks.

[John D'Errico]

This is not a factorization problem if A and B are known.

Do you know if A and B are full rank?

[Aqeel Anwar]

My bad. I did not know what else do I call this problem.

Yes A and B are in general full rank.

[Chris Turnes]

What is the norm on

||AXB-C||?

Is this the operator norm, or the Frobenius norm?

[Aqeel Anwar]

It is the frobenius norm.

Answer 1

[John D'Errico]

So you want to solve the problem

A*X*B == C

Subject to minimizing an L_0 norm on X?

You have stated that A and B are full rank. n and m are apparently not equal, but that does not really matter a lot. Assume that

n > m

for no good reason. We have essentially n*m unknowns in X. And we have n*m equations.

This is a linear system in the unknowns, but with full rank matrices. So we have no degrees of freedom to play with.

X = pinv(A)*C*pinv(B);

In general, there will probably be no zero elements in X. That you wish to minimize the L_0 norm, so you wish to minimize the number of non-zeros, (or maximize the number of zeros) is not relevant. As long as A and B are full rank, there will be no flexibility in the solution that I can see.

I wrote the above using pinv. I could also have written it using slash.

X = A\C/B;

In either case, there is simply no flexibility. A and B are full rank, square matrices. For example:

X0 = randn(5,3)
X0 =
     -0.58903       1.6555      0.79142
     -0.29375      0.30754       -1.332
     -0.84793      -1.2571      -2.3299
      -1.1201     -0.86547      -1.4491
        2.526     -0.17653      0.33351
A = randn(5);
B = randn(3);
C = A*X0*B;

X = pinv(A)*C*pinv(B)
X =
     -0.58903       1.6555      0.79142
     -0.29375      0.30754       -1.332
     -0.84793      -1.2571      -2.3299
      -1.1201     -0.86547      -1.4491
        2.526     -0.17653      0.33351

X = A\C/B
X =
     -0.58903       1.6555      0.79142
     -0.29375      0.30754       -1.332
     -0.84793      -1.2571      -2.3299
      -1.1201     -0.86547      -1.4491
        2.526     -0.17653      0.33351

As you can see, in either case, X recovers the original X0.

If it were true that A and(or) B were NOT square matrices, or not full rank, then some things would change. As you have stated it though, there is no way to solve this problem otherwise.

[Torsten]

I guess the constraint is

|||AXB-C||| <= lambda

with a given lambda > 0.

Thus AXB-C does not need to be exactly 0 - a compromise between sparsity and exactness.

Best wishes

Torsten.

[John D'Errico]

That changes things, though it was not stated that way, it makes more sense with some flexibility given.

[Aqeel Anwar]

Yes I dont need an exact solution rather constrained solution as mentioned by Torsten. I guess I forgot to put the constrained when typing in LaTeX.

Also i need the matrix X to be sparse, and the measure of sparsity being controlled by the lambda parameter

Answer 2

[sufyan masood]

hello can any one tell about sparsify subband signal and subband modification of subband signals coeffiects in compressive signal. kindly guide me about it. i will be highly thankful to all for help me counter this problem.