Function Repository Resource:

NearestKroneckerProductSum

Source Notebook

Approximate a numerical matrix as sum of Kronecker products

Contributed by: Jan Mangaldan

ResourceFunction["NearestKroneckerProductSum"][m,{p1,q1},{p2,q2},n]

gives a decomposition of a numerical matrix m into a sum of n Kronecker products of matrices of dimensions p1×q1 and p2×q2.

ResourceFunction["NearestKroneckerProductSum"][m,{p1,q1},{p2,q2},UpTo[n]]

gives the decomposition for n Kronecker products, or as many as are available.

Details

ResourceFunction["NearestKroneckerProductSum"] returns a list of pairs of matrices {{u1,v1},{u2,v2},}, each of dimensions p1×q1 and p2×q2, such that is minimized, where is KroneckerProduct[a,b] and is Norm[mat,"Frobenius"].
The lists {p1,q1} and {p2,q2} must be commensurate, and satisfy Dimensions[m]={p1p2,q1q2}.
ResourceFunction["NearestKroneckerProductSum"] takes the same options as SingularValueDecomposition.

Examples

Basic Examples (2) 

Compute a Kronecker product approximation of a small matrix:

In[1]:=
mat = {{1., 2.}, {3., 4.}};
kps1 = ResourceFunction["NearestKroneckerProductSum"][
  mat, {2, 1}, {1, 2}, 1]
Out[1]=

Form the approximant to the original matrix:

In[2]:=
approx1 = Total[KroneckerProduct @@@ kps1]
Out[2]=

Using two terms gives a much better approximant:

In[3]:=
kps2 = ResourceFunction["NearestKroneckerProductSum"][
  mat, {2, 1}, {1, 2}, 2]
Out[3]=
In[4]:=
approx2 = Total[KroneckerProduct @@@ kps2]
Out[4]=

The Frobenius norm of the remainder matrix is on the order of machine precision:

In[5]:=
Norm[approx2 - mat, "Frobenius"]
Out[5]=

Define a 10×12 matrix:

In[6]:=
mat = N[{{26, -23, -20, 10, 1, 17, 5, 17, 28, -16, -44, 20}, {5, 0, -1, -27, 37, -42, -11, -21, -8, 0, 8, -32}, {-22, 35, -2, 7, 13, 1, -15, 17, 17, -23, 11, -2}, {-2, -17, 5, 12, 17, -22, -3, -25, 20, -3, -11, -16}, {35, -20, -55, 25, 5, -15, -5, -8, -1, 5, -11, 4}, {-10, 0, 10, -40, -18, 23, 5, 6, -8, 1, 5, 0}, {14, -4, -4, 13, -2, -1, 16, -4, -16, 16, 26, -5}, {25, -23, -8, -25, 13, -6, -7, 1, 17, -15, -8, 11}, {23, -29, -25, 1, -21, 24, 17, -3, -5, -11, -7, -16}, {-19, 24, 7, -13, 6, -12, -2, 16, -40, 41, 13, 24}}];

Express the matrix as a sum of three Kronecker products of matrices of dimensions 5×3 and 2×4:

In[7]:=
Map[MatrixForm, kps = ResourceFunction["NearestKroneckerProductSum"][
   mat, {5, 3}, {2, 4}, 3], {2}]
Out[7]=

Check the difference between the original matrix and the sum of the Kronecker products:

In[8]:=
Norm[Total[KroneckerProduct @@@ kps] - mat, "Frobenius"]
Out[8]=

Scope (3) 

A 10×12 matrix with approximate numerical values:

In[9]:=
mat = RandomVariate[NormalDistribution[], {10, 12}]
Out[9]=

Express the matrix as a sum of up to seven Kronecker products of matrices of dimensions 2×3 and 5×4:

In[10]:=
kps = ResourceFunction["NearestKroneckerProductSum"][
  mat, {2, 3}, {5, 4}, UpTo[7]]
Out[10]=

Check the difference between the original matrix and the sum of the Kronecker products:

In[11]:=
Norm[Total[KroneckerProduct @@@ kps] - mat, "Frobenius"]
Out[11]=

An arbitrary-precision 10×12 matrix:

In[12]:=
mat = RandomVariate[NormalDistribution[], {10, 12}, WorkingPrecision -> 20]
Out[12]=

Express the matrix as a sum of up to seven Kronecker products of matrices of dimensions 2×3 and 5×4:

In[13]:=
kps = ResourceFunction["NearestKroneckerProductSum"][
  mat, {2, 3}, {5, 4}, UpTo[7]]
Out[13]=

Check the difference between the original matrix and the sum of the Kronecker products:

In[14]:=
Norm[Total[KroneckerProduct @@@ kps] - mat, "Frobenius"]
Out[14]=

Decompose a random complex-valued 10×12 matrix into a sum of two Kronecker products of matrices of dimensions 2×3 and 5×4:

In[15]:=
ResourceFunction["NearestKroneckerProductSum"][
 RandomComplex[{0, 1 + I}, {10, 12}], {2, 3}, {5, 4}, 2]
Out[15]=

Possible Issues (4) 

NearestKroneckerProductSum is left unevaluated for symbolic input:

In[16]:=
ResourceFunction[
 "NearestKroneckerProductSum"][{{a, b}, {c, d}}, {2, 1}, {1, 2}, 2]
Out[16]=

NearestKroneckerProductSum is left unevaluated for exact input:

In[17]:=
ResourceFunction["NearestKroneckerProductSum"][
 mat = {{1, 2}, {3, 4}}, {2, 1}, {1, 2}, 2]
Out[17]=

Numericize the input to get a result:

In[18]:=
ResourceFunction["NearestKroneckerProductSum"][
 mat // N, {2, 1}, {1, 2}, 2]
Out[18]=

NearestKroneckerProductSum is left unevaluated if the specified dimensions are incommensurate:

In[19]:=
ResourceFunction["NearestKroneckerProductSum"][\!\(\*
TagBox[
RowBox[{"(", "", GridBox[{
{
RowBox[{"-", "7"}], "8", 
RowBox[{"-", "11"}], "14"},
{
RowBox[{"-", "10"}], "5", 
RowBox[{"-", "10"}], "5"},
{"1", 
RowBox[{"-", "4"}], 
RowBox[{"-", "10"}], "10"},
{
RowBox[{"-", "10"}], "5", 
RowBox[{"-", "20"}], "10"},
{
RowBox[{"-", "3"}], "2", 
RowBox[{"-", "12"}], "12"},
{
RowBox[{"-", "10"}], "5", 
RowBox[{"-", "24"}], "12"}
},
GridBoxAlignment->{"Columns" -> {{Center}}, "Rows" -> {{Baseline}}},
GridBoxSpacings->{"Columns" -> {
Offset[
          0.27999999999999997`], {
Offset[0.7]}, 
Offset[0.27999999999999997`]}, "Rows" -> {
Offset[0.2], {
Offset[0.4]}, 
Offset[0.2]}}], "", ")"}],
Function[BoxForm`e$, 
MatrixForm[BoxForm`e$]]]\), {5, 2}, {1, 2}, 2]
Out[19]=

The decomposition of a matrix into a sum of Kronecker products is not unique:

In[20]:=
ml = N[{{( {
       {2, 1},
       {4, 5},
       {3, 6}
      } ), ( {
       {1, -2},
       {-2, 1}
      } )}, {( {
       {3, 4},
       {1, 5},
       {2, 6}
      } ), ( {
       {-3, 4},
       {-2, 1}
      } )}}];
In[21]:=
Map[MatrixForm, ResourceFunction["NearestKroneckerProductSum"][
  Total[KroneckerProduct @@@ ml], {3, 2}, {2, 2}, 2], {2}]
Out[21]=

Version History

  • 1.0.0 – 25 January 2021

Source Metadata

Related Resources

License Information