Suppose the objective I try to maximize is $$\max_{X} \|(I - \alpha X)^{-1}XA\|_F$$ where $X$ is the matrix needs to be pinned down, $\alpha$ is a scalar, and $\|\cdot\|_F$ is the Frobenius norm. Note that $(I-\alpha X)^{-1}$ is invertible only when $\alpha\neq1$, so assume $\alpha<1$. All matrices are $n$ by $n$ square matrices. An extra condition of matrix $X$ is that the vectors $X(:,k)$ for $k=1,\cdots,n$ is selected from identity by the optimization. So $X(:,k)$ is also a standard basis vector and $X$ may have repeated columns, i.e., $X$ is a permutation matrix.

One possible way to obtain the maxima of the objective is to apply the matrix multiplication via random sampling, where the objective is rewritten as

$$\max_{p_k}\left\| \frac{1}{n}\sum_{k=1}^n\frac{1}{p_k}B(:,k)X(k,:)A\right\|_F$$

where $B$ is the inverse and be approximated by Neumann series such that $$B = (I - \alpha X)^{-1} = \sum_{i=0}^n (\alpha X)^k$$

Note that we do not know the form or the specification of $X$ in advance but choose each column of $X$ by random sampling with probability $p_k$.

Now I have 3 questions:

(1) How to compute $B$ when it is random sampling approximation?

(2) Is this method too complex to implement on numerical calculation?

(3) Is there any better way to solve this puzzle?

Thanks in advance!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.