All Questions
Tagged with linear-algebra convex-optimization
121 questions
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
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
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
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
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
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
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
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 ...
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
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
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{...
0
votes
0
answers
614
views
Hadamard / matrix product adjoint
First of all I would like to thank everyone over here at mathoverflow for their amazing generosity and help (for both pros and newbies like myself).
I apologize if this question seems dumb; I'm a new ...
- 1
0
votes
0
answers
80
views
Finding gradient of an optimization
I am trying to find the gradient of the following optimization problem and then add to objective, but I got some trouble in computing. Could you please help me?
Assume that we have an optimization ...
- 161
0
votes
0
answers
52
views
Dense Matrix Estimation
I have a matrix $X \in \mathbb{R}^{m\times n}$ and I want to estimate it with a dense matrix $Y^{m\times n}$ such that $Y$ is still close to $X$ in some distance measure. Is this doable in a ...
- 137
0
votes
1
answer
2k
views
Finding linearly independent columns of a large sparse rectangular matrix
I have a problem that necessitates solving a large non-negative least-squares
problem. My matrix A is large, sparse, highly rectangular (num rows >> num cols)
and nearly binary. However, A is not ...
- 103
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
-1
votes
1
answer
137
views
Does a half plane contain intersection of some other half planes? [closed]
I'm doing research in Optimization and I have found this obstacle in the way.
If we have set of half planes like $c_ix\leq b_i$ where $i\in \{1,\ldots ,k\}$ there is an algorithm(it would be better ...
- 19
-1
votes
1
answer
175
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