Choose diagonal matrix $D$ to make $DB$ as orthonormal as possible

Question

Let $B\in \mathbb{R}^{m\times n}$, $m>n$. How can I choose $d_1,\dots,d_m$ such that $DB$, with $D_{ij} = d_i \delta_{ij}$, $1\leq i,j\leq m$, is not far from orthonormal, i.e., $\|B^{T}D^{T}DB-\text{Id}\|$ is small?

For some choices of matrix norm, the minimizer can maybe worked out using a singular value decomposition. I haven't succeeded in this, but I am more interested in a cheap solution anyway, even if it does not provide the exact minimum. Hence, I also do not care to specify the exact matrix norm.

Answer 1

We can recast minimizing $\Vert B^TD^TDB - I\Vert_F$ as a constrained least squares problem of the form $\min_x \Vert f-Ax\Vert_2$, $x\geq 0$ so that it can be solved with any standard non-negative least squares software package. I'm sure there are better solutions than this, but it seems to work reasonably well in practice.

Note that, $$ (B^TD^TDB)_{i,j} = \sum_{k=1}^{m} d_k^2 b_{k,i}b_{k,j} $$

Thus, let $x$ be the $m\times 1$ vector with $k$-th entry $d_k^2$ and let $A$ be the $n^2\times k$ matrix with rows of the form, $$ A_{\ell,:} = \begin{bmatrix} b_{1,i}b_{i,j} & b_{2,i}b_{2,j} & \cdots & b_{m,i}b_{m,j} \end{bmatrix} $$ where $\ell = (i-1)\cdot n + j$ and $i,j=1,\ldots,n$.

Finally set $f$ to be the $n^2\times 1$ vector where the $\ell$ entry is one if $i=j$ and 0 otherwise; i.e. 1 when $\ell = 1, n+2, \ldots, (n-1)\cdot n+n=n^2$ and 0 otherwise.

Then, $$ \Vert f - Ax \Vert_2^2 = \sum_{i=j} \left( \sum_{k=1}^m d_k^2 b_{k,i}^2 - 1 \right)^2 + \left(\sum_{i\neq j} d_k^2 b_{k,i}b_{k,j}\right)^2 = \Vert B^TD^TDB - I\Vert_F^2 $$

Here is a numpy implementation which seems to work reasonably well.

import numpy as np
import scipy as sp
from scipy import optimize

m,n = 100,10
B = np.random.randn(m,n) # generate random test matrix B

i = np.repeat(np.arange(n),n) 
j = np.tile(np.arange(n),n)

A = B.T[i]*B.T[j] # rows are pointwise product of all pairs of rows of B
f = (i==j) # set f = 1 if i=j and 0 otherwise

x,_ = sp.optimize.nnls(A,f)
D = np.diag(np.sqrt(x))

print(np.linalg.norm(f-A@x))
print(np.linalg.norm([email protected]@[email protected](n)))

EDIT: I misread the original problem as picking $B$ given $D$.

Suppose $B$ is also diagonal. Then $DB$ is diagonal with entry $d_ib_i$ in the $i,i$ position. Thus, choosing $b_i = 1/d_i$ gives the first $n$ columns of the $m\times m$ identity so that $(DB)^T(DB) = I_n$.

Did you by chance mean when $n>m$?