7
votes
Accepted
Maximize the Euclidean norm of a matrix times a vector on unit sub-spheres
You cannot hope for anything like a closed form solution, or even an exact efficient algorithm for this problem, because it is NP-hard. The reduction is from the max-cut problem. Let's look at the ...
- 757
6
votes
Nearest matrix orthogonally similar to a given matrix
Not a full answer, but some pointers on how to get a numerical method: If $\|\cdot\|_2$ denotes the spectral norm, then, by unitary invariance, your problem is equal to
$$
\min_{T\in O(n)}\|AT-TB\|_2.
...
- 12.7k
4
votes
Nearest matrix orthogonally similar to a given matrix
Depends what you mean by "technique". Your problem is a quadratically constrained quadratic program. To be precise, the objective function is
$$\mbox{tr} (A-TBT^t)(A^t - TB^t T^t) = \mbox{tr} ( AA^t +...
- 96.4k
3
votes
Nearest matrix orthogonally similar to a given matrix
This is really just a very long comment.
First, if you haven't run across the Orthogonal Procrustes Problem before, you may find it interesting. (It's very similar, and has an efficient algorithm.) ...
- 3,979
3
votes
Eigenvalue problem with two quadratic constraints
Generically, your system will have no solution, since $\mathbf{x}^t B \mathbf{x}$ is rarely zero for full-rank matrices. In the special case where $B$ is a degenerate symmetric matrix, then $x$ is in ...
- 96.4k
3
votes
Maximize the Euclidean norm of a matrix times a vector on unit sub-spheres
You can write $AX=\sum_{i=1}^N A_i x_i$ with $A_i\in \mathbb{R}^{r\times m}$. Then we have
$$
\|AX\|^2=(AX)^TAX=\sum_{i,j} x^T_i A_i^TA_jx_j.
$$
The condition for a critical point is
$$
A_i^TAX=\...
- 398
2
votes
Eigenvalue problem with two quadratic constraints
Because no one has offered a solution meeting your ideal of using a standard numerical linear algorithm, I will offer an approach using the global numerical nonlinear optimizer BARON.
Here is a ...
- 1,517
2
votes
Nearest matrix orthogonally similar to a given matrix
Regardless of the objective function, the constraints are non-convex, so the overall optimization problem is non-convex.
Solve it using numerical optimization on matrix manifolds, specifically, the ...
- 1,517
1
vote
Minimizing quadratic objective under orthogonality constraints
This is a special case of the little Grothendieck problem.
Afonso Bandeira, Christopher Kennedy, Amit Singer, Approximating the little Grothendieck problem over the orthogonal and unitary groups [PDF]...
- 161
Only top scored, non community-wiki answers of a minimum length are eligible