All Questions
Tagged with convex-optimization linear-algebra
121 questions
4
votes
1
answer
175
views
Maximizing trace subject to two equality constraints
I am looking at the following optimization problem
$$\begin{align}
\underset{{\bf X}}{\text{maximize}} \qquad&\mathrm{tr}({\bf AX})\\
\text{subject to} \qquad& \mathrm{tr}({\bf X}) = 1,\\
&...
- 43
0
votes
2
answers
97
views
Optimization algorithms for Kronecker approximation of high-dimensional covariance matrices
I'm working with a high-dimensional covariance matrix and exploring Kronecker product approximations to make it computationally manageable.
Here's the setup:
I have a graph $G$ represented by a $D\...
- 1
0
votes
0
answers
52
views
What are the injective embeddings of R^d into the cone of (semi-) positive definite matrices of dimension d?
How can we characterize the set of all injective functions from $\mathbb{R}^d$ to the set of all symmetric positive definite matrices of dimension d?
- 109
0
votes
0
answers
51
views
Minimizer of forward and reverse Kullback-Leibler divergence with sum constraints on marginals
Consider minimization of the Kullback Leibler divergence between two discrete distributions $p$ and $q$:
\begin{align*}
D_{KL} \left( p \parallel q \right) = \sum_i p_i \log \left( \frac{p_i}{q_i} \...
0
votes
0
answers
72
views
Minimizing the Spectral Norm of the Hadamard Product of a Quadratic Form Using CVX
I am trying to use CVX to minimize the spectral norm of the Hadamard product of two matrices, one of which is in quadratic form. Specifically, I am trying to minimize $\|{\bf A} \odot {\bf XX}^H\|_2$, ...
- 43
2
votes
1
answer
170
views
Equivalence of minimizing trace and determinant over matrix quadratic form in multivariate regression
Consider the multivariate regression model
$$Y = XB + E$$
where $Y$ is $n \times p$ and corresponds to the dependent variables, $X$ is $n \times k$ and corresponds to the independent variables, $B$ is ...
1
vote
0
answers
37
views
When does an optimal input sequence for a discrete-time system exist?
Suppose an LTI discrete-time system is given by the equations
$$
x_{k+1} = Ax_k + Bu_k,\\
y_{k} = Cx_k + Du_k
$$
with $x_k\in\mathbb{R}^{m}$, $y_k\in\mathbb{R}^{n}$ and $u_k\in\mathbb{R}^{p}$ and $\...
1
vote
0
answers
73
views
What is the closed form of a polyhedral cone's dual cone?
A polyhedral cone can be defined as
$$
\mathcal{K} = \{x~|~Ax\preceq 0\},
$$
where $A \in \mathbb{R}^{m \times n}$, $x\in \mathbb{R}^n$ and $\preceq$ denotes component-wise less than and equal to.
The ...
- 71
0
votes
0
answers
30
views
Application of greedy approach for optimization
I want to maximize an objective given by $$\max_{\{q_n,p_n\}} \sum_{n=0}^\infty (\alpha_1 - \beta_1 n) p_n + (\alpha_2 - \beta_2 n) q_n$$
where $\alpha_1 > \beta_1 >0$ and $\alpha_2 > \beta_2 ...
- 23
3
votes
2
answers
215
views
Is there a closed-form solution for $\max_D \operatorname{Tr}(ADBD)$
Is there a closed-form solution for
$$\max_D \operatorname{Tr}(ADBD)$$
where $D$ is a $N\times N$ diagonal matrix with $m<N$ number of $1$'s and the rest are $0$'s, and $A$ and $B$ are real ...
- 433
2
votes
0
answers
119
views
Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$
Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
2
votes
1
answer
423
views
Simple proof for convexity of a real valued matrix function
I am looking for a simple and short proof showing that $X \to \|X X^\top\|_F^2$ is a convex function where $\|\cdot\|_F$ is the Frobenius norm. I have one proof by showing that the derivative is ...
- 407
2
votes
1
answer
159
views
Conic hull of a rectangle
I have a simple question that appeared in research: For a rectangle $S :=[a_1,b_1] \times[a_2,b_2] \times \dots \times [a_n,b_n] \subset \mathbb{R}^n$. Let $p_0 = (a_1,a_2,\dots,a_n)$, and define $p_i ...
- 275
0
votes
0
answers
177
views
Given optimality of L1 norm, prove that absolute value of sum of a vector with proper sign is less than 1?
Problem:
Given a domain $\mathcal{D}\subset\mathbb{R}^{l}$, we can find $l$
points $\boldsymbol{v}_{i}\in\mathcal{D}$, $i=1,\cdots,l$. Each
point is a column vector with dimension $l\times1$. They ...
- 1
2
votes
0
answers
178
views
Can we get the exact solution of large-scale quadratic programming problems (quadratic objective, linear inequality constraints) using KKT condition?
Crossposted at Computational Science SE
Consider a quadratic programming problem with the following format:
$$
\text{min} Q(x) = c^Tx+\frac{1}{2}x^TDx \\
$$
$$
\text{s.t.} Ax\leq b, \\
x\geq 0
$$
...
- 21
6
votes
0
answers
136
views
Minimizing $\det(D)$ for all diagonal matrices $D$ that satisfy $D+B \succeq 0$
Let $A$ be an $n \times n$ real matrix and let $B$ be the block bipartite matrix
$$B = \begin{bmatrix} 0&A \\
A^{T}&0 \end{bmatrix}$$
I came across the following optimization problem, which ...
- 401
0
votes
1
answer
147
views
Is there a redundant constraint in linear programming? [closed]
From wikipedia:
But... Why do we need the $x\ge 0$ part? We can instead do $-x\le 0$, and thus saving a line in the definition (which is not a big deal but nevertheless nice).
(In order to do that, ...
- 3
5
votes
3
answers
496
views
Eigenvectors that are tensor products?
Consider a fixed $N\times N$ positive definite symmetric matrix $A$.
Assume $N=d^r$ for some $d,r\geq 1$.
I wonder if one can find a closed formula for the maximizer/maximum of the function $$f(x):=\...
- 2,135
0
votes
1
answer
80
views
Probability of accurate sparse recovery
Suppose $\mathbf{A}_{k\times n}$ ($k<n$) is a matrix whose entries are generated i.i.d. from Gaussian distribution and $\mathbf{s}_{n\times 1}$ is a sparse vector with $m$ sparsity (i.e., $\|\...
- 287
0
votes
1
answer
67
views
Analytic formula for minimizer of $f(x) := \sqrt{(x-a)^\top S(x-a)}+ r \|x\|_2$
Let $S$ be a positive-definite $n \times n$ matrix and define $\|z\|_S := \sqrt{x^\top S x}$ for any $x \in \mathbb R^n$. Let $a$ be a fixed vector in $\mathbb R^n$ and $r \ge 0$, and consider the ...
- 6,853
1
vote
0
answers
203
views
Matrix relative condition number
I've been working on some distributed optimization problems and faced a bit of a challenge with the following question.
Given $A_1, A_2, .., A_m \in M_n({\mathbb{R})} $ symmetric positive definite ...
- 11
0
votes
0
answers
156
views
Optimal solution of complex optimization problem
Let $Q(x)=a(x)e^{jb(x)}$ be a complex function of $x$. We want to approximate this function with $R(x)=\alpha e^{jx\beta}$ such that
\begin{align}
\text{arg}\min_{\alpha,\beta} \int_{-\frac{A}{2}}^{\...
- 287
2
votes
1
answer
506
views
Effect of duplicated row on singular values and vectors
Let $\mathbf{A}$ be a $n\times n$ matrix with Singular Value Decomposition (SVD) $\mathbf{A}=\mathbf{U}\mathbf{S}\mathbf{V}$ and $\mathbf{a}_1$ be the first row of $\mathbf{A}$. What can we say about ...
- 287
2
votes
2
answers
104
views
Inequality for matrix with rows summing to 1
Let $A$ be real matrix with $M > 1$ rows and $K > 2$ columns, and each entry $a_{m,k} \in (0,1)$, with each row summing to $1$. For all $m$
$$
\sum_{k=1}^{K} a_{m,k} = 1
$$
I want to find out if ...
- 23
1
vote
0
answers
98
views
Solution of a simple optimization problem
Let $\mathbf{U}_1$ and $\mathbf{U}_2$ be two arbitrary unitary matrices and $\mathbf{D}$ be a diagonal matrix. What is the solution of the following optimization problem?
\begin{align}
\min_{\mathbf{...
- 287
0
votes
0
answers
124
views
The best unitary matrices that approximate a matrix product
Let $\mathbf{A}$ be an arbitrary $N\times N$ complex matrix. Moreover, $\mathcal{U}_1$ and $\mathcal{U}_2$ are distinct subsets of all unitary matrices. Suppose the matrices $\mathbf{U}_1$ and $\...
- 287
1
vote
0
answers
52
views
When the summands of a positive definite matrix are positive definite
Let $A,B$ be two real symmetric matrices. Let $C = A+B$ be a positive-definite matrix. Write $C>0$ for $C$ being positive-definite. Suppose that $A>0 \implies C>0$ and $B > 0 \implies C>...
- 71
0
votes
0
answers
137
views
Any technique for linearization, or linear approximation?
Consider the following Matrix constraint:
$$
\begin{bmatrix} -U+\psi\Sigma_b^{-1} & V \\ V^T & -V^TU^{-1}V+\tau_2 -\psi \end{bmatrix} \leq 0
$$
where $\Sigma_b$ is a known positive definite ...
2
votes
1
answer
189
views
Analytic expression for the Moreau envelope of $x \mapsto \|Ax\|$
Given an $m \times n$ matrix $A$ and a vector $c \in \mathbb R^n$, define $\eta(A,c) \ge 0$,
$$
\eta(A,c) := \sup_{u \in \mathbb R^n} u^\top c - \frac{1}{2}\|u\|^2 - \|Au\|.
$$
Note that $\eta(A,c) = \...
- 6,853
1
vote
0
answers
176
views
Maximum mutual information of random unitary transformation
Let $\mathbf{U}$ and $\mathbf{V}$ be random unitary matrices independent of random input vector $\mathbf{x}$. Moreover, $\mathbf{z}$ be random iid complex Gaussian vector with zero mean and identity ...
- 287
1
vote
1
answer
156
views
Matrix reconstruction puzzle
Say a reconstruction of matrix $A$ is $A'$ and it's defined as
$$
A' = PDP^TA
$$
where $P$ is an orthogonal matrix, $D$ is a diagonal binary (1 or 0) matrix. In a trivial case, when all diagonal ...
- 433
20
votes
4
answers
5k
views
Is the pseudoinverse the same as least squares with regularization?
Given a linear system $Ax=b$, the pseudoinverse of $A$ is found as the matrix $A^+$ such that $x=A^+ b$ where $x$ solves the least squares problem $\min \| Ax - b \|^2 $ and $x \perp \mathcal{N}(A)$. ...
- 501
0
votes
1
answer
157
views
Generalization of Dickson's Lemma
Given $\{v^i\}_{i \in \mathbb{N}} \subseteq \mathbb{N}^n$, and $\cup_{k=1, \ldots, m} C_j = \mathbb{N}^n$ for some $m$, where each $C_k$ is a cone generated by rational vectors. My question is: does ...
- 37
2
votes
2
answers
107
views
Solution to a matrix optimisation problem with a particular structure
Does a matrix of the form $A_{ij} = v_i + v_j$ for some arbitrary vector $v$ have a particular name?
I am attempting to find the closed form solution (if it exists, although it looks like it might) ...
- 31
0
votes
0
answers
41
views
Iterative algorithm for obtaining similarity
Let $x_1,x_2,\ldots,x_M$ be $M$ non-negative variables. Moreover, assume that $f_m(x_m)=\frac{x_m}{1+\sum_{n}\beta_{n}^{(m)}x_n}$ be $M$ fractional functions with non-negative constants $\beta_{n}^{(m)...
- 287
3
votes
2
answers
380
views
How to find a solution of a large system of linear diophantine inequalities?
I need to find a solution (all solutions, or at least upper and lower bounds) in positive integer numbers to the system $Ax \ge f$, where $A$ is an integer matrix.
With SageMath, I solved it with the ...
2
votes
0
answers
618
views
block diagonal approximation of (SPD) matrix
I am interested in approximating a symmetric matrix in a block diagonal form, i.e. compute just some entries of the matrix located in blocks around the diagonal. Are there any theoretical guarantees ...
- 335
3
votes
0
answers
122
views
Convex optimization upper bound for a non-linear optimization
Is there any good convex optimization problem based upper-bound for the following non-linear optimization problem?
\begin{align}
\max_{x_1,\ldots,x_N}&\quad \sum_{n=1}^{N} \log(1+\frac{x_n}{1+\...
- 287
0
votes
1
answer
153
views
Difference of two optimization problem's optimal value
Let we have two following optimization problems:
\begin{align}
\text{(P1)}\quad \alpha_1 = \max_{x_1,\ldots,x_M} &\quad \sum_{m=1}^{M}\log(1+f_m(x_1,\ldots,x_M))\\
\textrm{s.t.} &\quad \...
- 287
2
votes
0
answers
46
views
Notion of distance between linear programs
Consider the linear programming problem
\begin{align}
\max_{x}&~c^Tx \\~s.t.~~a^Tx &\leq B~,~0\leq x_i \le1
\end{align}
where $c$ and $a$ are $n \times 1$ given non-negative vectors. $B$ is a ...
- 1,421
4
votes
1
answer
119
views
Is the Loewner maximum uniquely defined?
Given 2 (symmetric) PSD matrices $A,B$, is the following set $S_{A,B}$ non-empty?
$$ S_{A,B} = \{ C: C\succeq A, C\succeq B, \text{ and }\forall D, D\succeq A, D\succeq B \implies D\succeq C \} $$
If ...
- 41
2
votes
1
answer
1k
views
$\arg\max$ in the dual norm of the nuclear norm
Given a matrix $X \in \mathbb{R}^{m \times n},$ then the spectral norm is defined by
$$\left \| X\right\| := \max\limits_{i \in \{1, \dots, \min\{m,n\}\} }\sigma_i (X)$$
whereas the nuclear norm is ...
1
vote
1
answer
234
views
Log Fractional optimization problem
Let $\mathbf{x}$ be a vector of $N$ variables. Then, how can I solve the following optimization problem?
\begin{align}
\max_\mathbf{x}&\quad \sum_{n} \log(1+\frac{x_n}{\alpha+\sum_{m}\beta_m^{(n)}...
- 287
1
vote
0
answers
139
views
Subgradient chain rule
Suppose $$F:\mathbb{R}^n \to \mathbb{R},\; F(x)=\mathrm{max}_\mathrm{eig}(C-\mbox{diag}(x)).$$
I am trying to find a subgradient of $F$ at $x_0$. A subgradient of $\mathrm{max}_\mathrm{eig}$ is given ...
- 11
1
vote
1
answer
336
views
A close-form solution for a simple quadratic optimization problem
Is there any closed form solution for the following optimization problem:
\begin{align}
&\min_{\mathbf{X},\alpha} \mathrm{Tr}[(\mathbf{A}-\mathbf{B}\mathbf{X})(\mathbf{A}-\mathbf{B}\mathbf{X})^{\...
- 287
0
votes
0
answers
136
views
Finding a specific solution to $X^T\Sigma X = D$
I'm looking to solve for a specific $X$ in the following equation:
$$X^T\Sigma X = D,$$
where $\Sigma \succ 0$, $D$ is a diagonal matrix with strictly positive entries, and all matrices are square. It ...
- 41
2
votes
1
answer
344
views
Joint convexity of trace of matrices
Let $\Gamma_{m\times m}$ be a diagonal matrix with positive diagonal entries and $\mathbf{A}_{m\times m}$ be an arbitrary matrix. Then, is the following trace function jointly convex on $\Gamma_{m\...
- 287
1
vote
0
answers
150
views
Minimax optimization of diagonal entries of function of matrix
Let $\mathbf{A}$ and $\mathbf{U}$ be arbitrary complex $M\times N$ and $N\times M$ matrices, respectively. Let denote superscript $(\cdot)^{\dagger}$ and $(\cdot)^{\mathrm{H}}$ as pseudo-inverse and ...
- 287
8
votes
2
answers
809
views
Bounding the spectral gap of a simple symmetric matrix
I have a seemingly innocent linear algebra problem that I cannot solve, and which I hope that you would kindly offer some insight into. Here is the description: Let $\mathbf{a} = (a_1, a_2, \dots, a_d)...
- 333
0
votes
0
answers
121
views
Closed form solution to an equation
Let $X \in \mathbb{R}^{n \times d}, w \in \mathbb{R}^d, y \in \{\pm 1
\}^{n}, \alpha \in (0, 1)$. Consider the equation
$$ X^{\top}(Xw-y)+\alpha \|w\|_{2}X^{\top}\operatorname{sign}(Xw-y)+\alpha\frac{...
