3
$\begingroup$

Given an invertible matrix $A \in \mathbb{C}^{n\times n}$. How to find

$$ U^* = \max_{\text{$U$ with $U^H U = I$}} \lVert U A\rVert_1, $$ where $\lVert\cdot\rVert_1$ is the entrywise 1-norm, i.e., $\lVert A\rVert_1 = \sum_{i,j} \lvert A_{ij}\rvert$ and $\cdot^H$ denotes the complex conjugate transpose?

For $A = I$, the solution is any complex Hadamard matrix, e.g., a scaled discrete Fourier matrix.

$\endgroup$
  • $\begingroup$ I'm not familiar with the notation $A^H$ -- is this what I would call "conjugate transpose"? If so, then isn't $A^H A$ always positive (semi)definite? $\endgroup$ – Yemon Choi Apr 30 '20 at 19:37
  • 1
    $\begingroup$ Also, when you say "find", are you asking for an algorithm to find the exact value, or would you still be interested in upper and lower bounds in terms of e.g. the singular values of A? $\endgroup$ – Yemon Choi Apr 30 '20 at 19:40
  • 1
    $\begingroup$ @YemonChoi Yes, conjugate transpose. And the positive definite was unnecessary, $A$ needs to be invertible. Yes, I'm mainly asking for an algorithm, but I'd be interested in bounds as well. $\endgroup$ – Sebastian Schlecht Apr 30 '20 at 20:09
  • 1
    $\begingroup$ @LSpice Thanks for the edit $\endgroup$ – Sebastian Schlecht May 5 '20 at 7:24
1
$\begingroup$

Too long to comment:

You might want to try out the following sub-optimal approaches, as the original problem is likely to be in NP-class (citations needed!). I am also going to assume that $A$ has only real entries, for simplicity.

1) Take a look at the paper "Orthogonalization of vectors with minimal adjustment" in Biometrika. The first optimality criterion might be a good surrogate for your cost function. Intuitively, it finds the an orthogonal basis which has least deviation (in terms of dot product) from the a given set of vectors (here columns of $A$).

2) You might also want to investigate the sub-optimality of $Q$ where $A=QR$ (QR decomposition). Changing the order in which Gram-Schmidt is done will yield different QR decompositions, and so you might also want to use this degree of freedom judiciously.

3) Lastly, the greedy way. Intuitively, suppose one were to find a unit vector $q_1$ such that $||q_1A||_1$ is maximized. Post this, one can find a unit vector maximizing $||q_2A||_1$, subject to the additional constraint $q_1q^\top_2=0$. This can be done till one obtains a orthonormal matrix. What remains now is: $$ \max_{q\in R^{n\times 1}} ||qA||_1~\mbox{subject to}~qq^\top = 1 ~\&~ qC = 0. $$ Intuitively, a unit vector has highest 1-norm if all its entries are equal in magnitude, or its alignment along on of the vectors $[\pm 1,\cdots, \pm 1]$ is maximum. This can be used in the following iterative routine. Choose any unit vector $q^{(0)}$ such that $q^{(0)}C=0$. Run the following convex routine iteratively till convergence (there is no guarantee of convergence): $$ q^{(k+1)} = \arg \max_{qA\in R^{n\times 1}} q\left({\mbox{sign}(q^{(k)})}^\top\right) ~\mbox{subject to}~ qq^\top\leq 1 ~\&~ qC=0. $$

(4) One could also try the following simpler idea. Note that $\begin{bmatrix} I & X\\X^\top &I \end{bmatrix} \succeq 0 $ is a convex relaxation to orthonormal constraint (using Schur complement). And a the maximum of a linear cost functional with this relaxed constraint will always yeild an optima at its boundary, which is the set of orthonormal matrix. Using the same logic as in point (3), one can write the code below:

import numpy as np

import cvxpy as cvx

X = cvx.Variable((N,N))

Q,R = np.linalg.qr(np.random.randn(N,N))

Q = np.sign(Q@A)

count = 0

while(count<=20):

constraints = [cvx.vstack((cvx.hstack((np.eye(N),X)),cvx.hstack((X.T,np.eye(N))))) >> 0]

prob = cvx.Problem(cvx.Maximize(cvx.trace((X @ A)@(Q.T))), constraints)

prob.solve()

Q = np.sign((X.value)@A)

count = count + 1

print(np.sum(np.abs(X.value @ A)))

Z,R = np.linalg.qr(np.random.randn(N,N))

print(np.sum(np.abs(Z@A)))

Hope this helps.

$\endgroup$
  • $\begingroup$ Thanks. I'm going through the paper in 1). That's a side question for 2), but could $R$ of the QR decomposition to be the minimum 1-norm? Regarding 3), I'm missing the definition of $C$. It might not change the method, but restricting to real matrices might change the maximum, right (as for example Hadamard matrices do not exist of $n = 3$)? $\endgroup$ – Sebastian Schlecht May 1 '20 at 8:27
  • $\begingroup$ Regarding 1) How about $A = I$? The orthogonalization would yield $U = I$, which is clearly not a good solution. The suggested surrogate only maximizes the diagonal elements of $UA$. $\endgroup$ – Sebastian Schlecht May 1 '20 at 8:41
  • $\begingroup$ @SebastianSchlecht, thanks for the comment. (1) Would $R$ serve as a solution for minimum 1-norm, I have no reason to believe that. As I mentioned earlier, there are $n!$ ways of doing QR depending on the ordering for Gram-Schmidt; which one to choose needs investigation. (2) $C$ is made up by stacking row vectors obtained till that point of iteration of the greedy algorithm (not the one used to solve the inner opt-routine), (3) I agree with your observation for A=I, but not sure if that would as bad for a general A (its all sub-optimal afterall). $\endgroup$ – DSM May 1 '20 at 11:03
  • $\begingroup$ @SebastianSchlecht, had a few more thoughts for special cases, but just pointers. Would your idea of using DFT matrix for $A=I$ also work if $A$ were circulant? And secondly, in case you have $A=I+S$, where I is identity matrix and $S$ is skew-symmetric, would Cayley transform of $S$, given by $(I-S)(I+S)^\top$, be a decent solution? $\endgroup$ – DSM May 1 '20 at 11:07
  • $\begingroup$ Ok, I got now your argument with the QR. Unfortunately, I have trouble with the definition of $C$. Could you please be so kind and be more explicit there? Yes, I believe that the circulant matrix works in a similar manner. $\endgroup$ – Sebastian Schlecht May 2 '20 at 15:11
0
$\begingroup$

Here an alternative solution, which outperformed @DSM solution (4) in all tested cases.

Without loss of generality, we assume that $\lVert A \rVert_F = 1$. The optimal value for the $\ell_1$ norm is attained by the unitary Hadamard matrix $H$, e.g., DFT matrix.

As a proxy cost function, we use therefore

$$ \hat{U} = \min_U \| |U A| - |H| \|_F, $$ where $|\cdot|$ is the element-wise absolute values. This is equivalent for an optimal set of phases $\hat{P}$ with $|\hat{P}_{ij}| = 1$ such that $$ \hat{U} = \min_U \| U A - |H| \circ \hat{P} \|_F, $$ where $\circ$ denotes the element-wise (Hadamard) product. This can be solved iteratively by unitary Procrustes solution such that $$ U^{(i+1)} = \min_U \| U A - |H| \circ P^{(i)} \|_F \\ P^{(i+1)} = U^{(i+1)}A \oslash |U^{(i+1)}A|, $$ where $\oslash$ is the element-wise (Hadamard) division. These iterations are guaranteed to converge:

Because of the Procrustes solution is the global minimum for the Frobenius norm, we have

$$ \| U^{(i+1)} A - |H| \circ P^{(i)} \|_F \leq \| U^{(i)} A - |H| \circ P^{(i)} \|_F $$

Then, updating the phase also reduces the error

$$ \| U^{(i+1)} A - |H| \circ P^{(i+1)} \|_F \leq \| U^{(i+1)} A - |H| \circ P^{(i)} \|_F, $$ which is essentially a element-wise version of $$ \phi = \min_\theta \left(a e^{\imath \phi} - b e^{\imath \theta} \right)^2, $$ where $a$, $b$, $\phi$, $\theta$ are real valued.

$\endgroup$
  • $\begingroup$ That's very nice, and thanks for posting your solution. Seems like your algorithm tends to move towards a Hadamard matrix. Why should this be the case for a general A? And, which Hadamard matrix would you choose to begin with (there are many of a given order)? I'd also like to learn about your proof of convergence/optimality for the Procrustes problem. $\endgroup$ – DSM May 5 '20 at 5:44
  • $\begingroup$ @DSM I added a normalization of $A$, I think, this should make the equal magnitude solution optimal. The Hadamard property is not used, it depends only on the initial phases $P^{(0)}$. I haven't found any dependency on the initial phase, thus the choice of which Hadamard matrix is not relevant. But, maybe you're right, I should replace the Hadamard just with the equal magnitude condition? I added more to the convergence, hope that helps. $\endgroup$ – Sebastian Schlecht May 5 '20 at 8:08

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.