All Questions
Tagged with matrices oc.optimization-and-control
107 questions
4
votes
0
answers
82
views
Non-singularity of a series of matrices
Let $A_1$, $A_2$ be $n\times n$ real matrices. Suppose that $A_1$ and $A_2$ are Schur stable (i.e., their eigenvalues are strictly inside the unit circle in the complex plane). Let $B_1$, $B_2$ be two ...
- 2,712
2
votes
1
answer
456
views
Constrained optimization over a trace functional
Let $A\in\mathbb{R}^{n\times n}$ be a stable matrix (i.e., the eigenvalues of $A$ have negative real parts). Consider the following optimization problem in $X \in \mathbb{R}^{n \times n}$
$$\begin{...
- 2,712
9
votes
1
answer
847
views
Maximizing a ratio of determinants
Let $D\in\mathbb{R}^{n\times n}$ be a diagonal positive definite matrix s.t. $D\leq I$ ($I$ denotes the $n$-dim. identity matrix) and let $\alpha$ be a strictly positive real number. Consider the ...
- 2,712
2
votes
1
answer
1k
views
Is the sum of two stable matrices also stable?
Let $A$ and $B$ be two arbitrary real matrices of the same dimension. If the eigenvalues of $A$ and $B$ are all in the left half of the complex plane, can we estimate the the location of the ...
- 23
7
votes
1
answer
271
views
Closest point in $SU(n) \otimes SU(n)$ to $SU(n^2)$
What is the closest $V_1 \otimes V_2 \in SU(n)\otimes SU(n)$ in the squared trace inner product to a given $U \in SU(n^2)$? I.e. minimize over $V_1, V_2$:
$\min_{V_1, V_2} | V_1 \otimes V_2 - U|$ in ...
- 2,099
3
votes
0
answers
298
views
Singular value decomposition of a low rank weak diagonally dominant M-matrix. When is the unitary polar matrix positive semi-definite?
Let $A$ be an $n \times n$, non-symmetric, real, weak diagonally dominant M-Matrix. Its diagonal is strictly positive, its off-diagonal is negative or zero and all its columns sum to zero. $A$ has ...
- 323
8
votes
1
answer
2k
views
Finding Toeplitz matrix nearest to a given matrix
For an arbitrary $N\times N$ Hermitian matrix $A$, I want to derive a Toeplitz matrix from $A$ such that the eigenvectors of both matrices have minimal change.
Specifically I want find the Toeplitz ...
- 495
1
vote
1
answer
606
views
The state-transition-matrix of a physical system,
Here's a simple but potential research problem that I am learning about.
Let's say I am studying a physical system that is governed by N objects. At each time, each object is either "active" and ...
- 1
3
votes
1
answer
730
views
Computational complexity of low rank SDP
Suppose we are given a general semidefinite program (SDP) of the form with an additinal rank requirement
\begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{...
- 1,503
1
vote
0
answers
141
views
For of a special case of $Ax>=b$, are there always integer solutions?
The input consists of two integers $n\geq 2$ and $K\geq 2$, and a vector of positive integers $b$ of size $n$. We assume that $\sum_i b_i$ is a multiple of $K$.
The output is a matrix $A(n\times n)$ ...
- 123
2
votes
0
answers
90
views
Singularities of the Quantum propagator (baby version)
Given $a,b \in \mathfrak{su}(4)$ which are taken to generate the whole algebra, consider the following map $V:\mathbb{R}^{2} \rightarrow SU(4)$:
$V : (w_1, w_{2}) \mapsto e^{(a+w_2 b)} e^{(a+w_1 b)}$
...
- 2,099
2
votes
0
answers
172
views
Optimization with random matrix
Consider $J$ a random matrix of size $n\times n$ with i.i.d. Gaussian entries $J_{ij} \sim \mathcal{N}(0,\sigma^2/n)$. Let $f(x)=tanh(x)$, and for $x\in\mathbb{R}^n$, $f(x)$ denotes the vector where $...
- 840
2
votes
1
answer
2k
views
Finding permutation matrix $P$ that minimizes the trace of $P C P^T D$
I have a problem that is really important for my thesis and i am not studding math so i will be very glad if you help me in this case...
thanks for your help in advance
I want to find permutation ...
- 59
3
votes
0
answers
149
views
Copositivity under tensor products
Is there any symmetric real matrix $A$ such that $A^{\otimes n}$ is copositive for all positive integers $n$, but such that A is neither positive semidefinite nor has just non-negative entries?
...
- 31
1
vote
2
answers
1k
views
Are there some algorithms to solve the diagonal matrix $X$ to the following matrix equation?
Suppose $X$ is an unknown $m \times m$ diagonal matrix. Given a scalar $0<c<1$, and a matrix $A$ of $m \times m$ size whose entries $0<A_{i,j}<1$. Are there some algorithms to find the ...
- 241
2
votes
2
answers
606
views
Solving a matrix equation $X=c \cdot AXA' +I$ with a diagonal corrections
I am now struggling to solve the matrix $X \in R^{n \times n}$ in the following equation:
$X=c \cdot AXA' - diag(c \cdot AXA')+ I$,
where
(1) $A \in R^{n \times n}$ is a given matrix whose element ...
- 241
4
votes
1
answer
538
views
Rank 1 Approximation of Elementwise Inverse Matrix
I'm wondering whether there is a good way to solve the following optimisation problem.
Given a strictly positive quadratic matrix $A$, find two diagonal matrices $D_1$ and $D_2$ so that
$$ \| D_1 A ...
- 909
2
votes
1
answer
1k
views
derivative of sum of singular values
can someone point me to the direction how to calculate the derivatives of a sum of singular values of a matrix?
I am trying to minimize
$$\min_A \parallel A \parallel_*+ \cdots $$ where $\parallel A \...
- 125
2
votes
0
answers
1k
views
Incoherence of the row/column span
Due to V.Chandrasekaran., et al (p.11) : In general for any $k$-dimensional subspace of $A_{n×n}$ we have that:
$$\sqrt{(k/n)} \leq incoherence(A)\leq 1$$
where the lower bound is achieved (for ...
- 21
0
votes
1
answer
203
views
Eigenvalues of a given parametrized matrix.
Let $\mathbf{A}$ and $\mathbf{B}$ be two complex rank-one $N\times N$ positive semi-definite matrices. Let the matrix $\mathbf{C}$ be defined as
\begin{align}
\mathbf{C}=\left(\mathbf{I}*\frac{1}{\...
- 1,421
2
votes
2
answers
765
views
Why eigenvectors optimize this orthogonally constrained nonlinear minimization problem?
Given a $p \times p$ positive definite matrix $\Sigma$, why eigenvectors of $\Sigma$, stacked as columns of a matrix $R \equiv [r_1 \, r_2 \, \ldots \, r_p]$, optimize the following orthogonally ...
- 362
7
votes
3
answers
2k
views
Optimization problem on trace of rotated positive definite matrices
Given two $n \times n$ symmetric positive definite matrices $A$ and $B$, I am interested in solving the following optimization problem over $n \times n$ unitary matrices $R$:
$$
\mathrm{arg}\max_R \,\...
- 362
3
votes
1
answer
2k
views
Fast algorithm for maximizing smallest eigenvalue of linear combination of hermitian matrices
I have an engineering back ground. Due to work, I came across this problem
\begin{align}
&\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\
s.t.~&\left(\mathbf{A}_0+\sum_{i=1}^{K}y_i\mathbf{A}_i\...
- 1,421
0
votes
1
answer
2k
views
eigen-decomposition solution? is it unique?
Assume an N*N covariance matrix (Q) which is a positive definite matrix. The decoder X is assumed to be N*s, where s<=N. X is calculated to be s eigenvectors corresponding to s minimum eigenvalues. ...
- 1
3
votes
0
answers
466
views
An optimization problem over real symmetric matrices
Given an $n\times s$ matrix $P$ of positive real numbers and $T\geq n$, find (either by a formula or an algorithm) the real symmetric $n\times n$ Z-matrix $A$ which maximizes $\min\limits_{1\leq i<...
- 767
4
votes
1
answer
286
views
Explicit formula for an LMI solution
Suppose we have a linear matrix inequality (aka LMI aka spectahedron aka linear matrix pencil):
$$A_{0}+x_{1}A_{1}+x_{2}A_{2}+\ldots+x_{m}A_{m} \succeq 0.$$
(The notation $X \succeq Y$ means that $X-...
- 6,962
5
votes
3
answers
3k
views
A nice necessary and sufficient condition on positive semi-definiteness of a matrix with a special structure
Let
$$
A =
\begin{pmatrix}
\sum_{j\ne 1}a_{1j} & -a_{12} & \cdots & -a_{1n}\\
-a_{21} & \sum_{j\ne 2}a_{2j} & \cdots & -a_{2n}\\
\vdots & \vdots & \ddots & \...
4
votes
2
answers
359
views
A certain type of constrained Rayleigh-Ritz ratio
Let $\mathbf{A_1}$ and $\mathbf{A_2}$ be two hermitian matrices. Consider the problem
\begin{align}
\max_{\mathbf{u}^H\mathbf{u}=1}~\mathbf{u}^H\mathbf{A}_1\mathbf{u} \\\
\mathbf{u}^H\mathbf{A}_2\...
- 1,421
3
votes
0
answers
125
views
Copositivity in matrix pencils
Given two square symmetric matrices $A,B$ of the same order, the matrix pencil $P(A,B)$ is the set of linear combinations of $A$ and $B$. Finsler's theorem gives an elegant criterion for $P(A,B)$ to ...
- 6,962
-1
votes
1
answer
174
views
Regularized Gradient with respect to a matrix (with a specific structure)
Suppose we have a typical logdet function $\mathcal{L}$
$$
\mathcal{L} = \log\vert \mathbf{I} + \mathbf{A}\mathbf{S} \vert - \mathbf{q}^T(\mathbf{A}^{-1} + \mathbf{S})^{-1} \mathbf{q},
$$
where $\...
- 125
8
votes
1
answer
2k
views
Symplectic block-diagonalization of a real symmetric Hamiltonian matrix
Given a $2n\times 2n$ real, symmetric, Hamiltonian matrix $W$ (anticommutes with the symplectic metric), is there an orthogonal, symplectic matrix $R$ such that $R^\top WR$ is block-diagonal?
Being ...
- 315
4
votes
2
answers
1k
views
Minimum eigenvalue of a Affine Combination of two Hermitian matrices
Consider two $N \times N$ hermitian indefinite matrices $A_1$ and $A_2$. Consider their affine combination
\begin{align}
M(t)=(1-t)A_1+tA_2
\end{align}
I am interested in the minimum eigenvalue of $M(...
- 1,421
2
votes
1
answer
299
views
Rayleight Ritz Ratio and smallest eigenvalue for a set of given matrices
I am familiar with Rayleigh Ritz Ratio for hermitian matrices. Let $A_1$ be a given $N \times N$ hermitian matrix. Then the smallest eigenvalue of $A_1$ is given by
\begin{align}
\lambda_{min}(A_1)=\...
- 1,421
6
votes
1
answer
1k
views
Solve equation with matrix variable
I want to solve a matrix $\Omega$ from a equation $\sum_k (\Omega + \Theta_k)^{-1} = Q$. The $Q$ and $\Theta, \forall k=1,\ldots,K$ are known, and are positive definite matrices. $\Omega$ also has to ...
- 173
5
votes
2
answers
429
views
Simultaneous maximization of two Generalized Rayleigh Ritz Ratios
Consider hermitian positive semi-definite matrices $A_1$ and $A_2$. Consider also positive definite matrices $B_1$ and $B_2$. I want to maximize the minimum of the two Generalized Rayleigh Ritz ratios ...
- 1,421
12
votes
5
answers
9k
views
Solving Lyapunov-like equation
The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...
- 121
0
votes
1
answer
180
views
(probably simple) optimization question
Suppose you have a concave function defined over a non-polyhedral convex cone and you are interested in the infimum. What would be standard approaches to tackle the question? (The cone is actually PSD ...
- 6,962
2
votes
0
answers
240
views
Copositive matrix?
I want to check under what conditions a matrix of the form $\alpha J -Q$ is copositive, where $J$ is the all-ones matrix and $Q$ is doubly nonegative (i.e. entrywise nonnegative and positive ...
- 6,962
3
votes
1
answer
1k
views
What is the minimum of the Frobenius norm in the intersection of positive semidefinite cones?
For scalar variables $x$, we have a simple solution for the following problem.
\begin{eqnarray}
\min_x&&\alpha(x-a)^2+\beta(x-b)^2 \\\
\mathrm{s.t. }&&x\leq a\\\
&&...
- 607
3
votes
1
answer
523
views
Linear and Isometric Automorphism Groups of the PSD Cone
Let $S_+$ be the cone of psd matrices ($n\times n$ real symmetric positive semidefinite matrices). This cone is a metric space induced from the inner product $\langle A,B\rangle = tr (AB)=tr(BA)$.
...
user2529
3
votes
1
answer
3k
views
How do I optimize over (or take derivative wrt) a square diagonal matrix?
I would like to solve the following optimization problem in $k$-vector $w_i$
$$ \min_{w_i} \quad \left\|P_i - X \mbox{diag} (w_i) Y^T \right\|_F^2 $$
where $P_i$ is a $6 \times 6$ matrix, $X$ and $Y$ ...
- 33
5
votes
2
answers
1k
views
Is a solution of a linear system of semidefinite matrices a convex combination of rank 1 solutions?
The cone of symmetric positive semidefinite $n\times n$ matrices is the convex hull of rank $1$ matrices. That is, every symmetric positive semidefinite matrix is a convex combination of rank 1 ...
user2529
6
votes
1
answer
1k
views
Eigenspace of Euclidean distance matrix.
What is the necessary and sufficient condition (if there is any) that $n$ orthonormal vectors $v_1,v_2,\cdots,v_n$ are eigenvectors of a Euclidean distance matrix. When $n=2$, the orthonormal ...
- 1,858
7
votes
2
answers
486
views
The odd power of copositive matrix
If $A$ is copositive, what about $A^3$? Is it also copositive? More generally,
my question is whether the odd power of a copositive matrix is still copositive.
Any reference is appreciated
- 1,858
7
votes
3
answers
6k
views
Minimize trace of inverse of convex combination of matrices.
Hello! (First question--please forgive me if its unclear.)
I am interested in efficient/approximate optimization techniques for minimizing a norm of a convex combination of symmetric, positive semi-...
- 181
1
vote
2
answers
513
views
Optimizing directly on the eigenspectrum of a matrix
I have an application where I want to the eigenvalues of the graph to be involved in the objective and constraints in a flexible way (moreso than just the nuclear or frobenius norm). Whats a good ...
- 2,383
4
votes
3
answers
1k
views
cayley transform for non-square matrices
Hi,
I am optimizing a function over a matrix $U$, where $U \in \mathbb{R}^{m \times n}$ and $U^TU = I$. I do not want to run a constrained maximization program, since employing the constraint $U^TU = ...
- 263
4
votes
1
answer
7k
views
Matrix optimization problem
This is (probably) an easy one:
Given a positive definite matrix $M$, find the positive definite matrix $X$, which minimizes $\textrm{tr}(X M)$ subject to $\det(X) = 1$.
Looking for how to find X, ...
- 379
4
votes
4
answers
703
views
efficient way to compute the inversion of the following matrix
Hi, there
I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special ...
- 41
5
votes
2
answers
680
views
Finding the solution to b = Ax that minimizes the Hamming weight (everything over the field F_2).
Is there an efficient algorithm for finding the solution $x$ of
$b = Ax$
that minimizes the Hamming weight of $x$, where
$A$ is a nxm-matrix over the field $\mathbb{F}_2$ ("integer matrix modulo 2")...
- 141