1
vote
2answers
31 views

Max and Min using Lagrange Multipliers

Suppose A is a symmetric matrix. Show that the maximum and minimum of $\mathbf x ^T A \mathbf x$ subject to the constraint $\mathbf x ^T \mathbf x=1$ are the maximum and minimum eigenvalues of A. I ...
0
votes
1answer
34 views

Symmetric Positive Definite Matrix Proof

Suppose that $H^+ = H - (\mathbf y^TH \mathbf y)^{-1} H\mathbf y \mathbf y^T H + (\mathbf y ^T \mathbf s )^{-1}\mathbf s \mathbf s^T $ where H is symmetric and positive definite. Supposing that ...
0
votes
0answers
26 views

l1 minimization with orthogonality constraint

I want to find a rotation (or reflection) for my data which maximizes the space between my points and the basis' margins. I have formulated the problem as follows: Given $X \in \mathbb{R}^{n \times ...
2
votes
2answers
50 views

Minimum of a quadratic form

If $\bf{A}$ is a real symmetric matrix, we know that it has orthogonal eigenvectors. Now, say we want to find a unit vector $\bf{n}$ that minimizes the form: $${\bf{n}}^T{\bf{A}}\ {\bf{n}}$$ How can ...
2
votes
0answers
36 views

Examples of non trivial problems in this structure.

I'm looking for examples of non trivial problems that match with the follow structure. Let the function $$g: U \times V \rightarrow \mathbb{R}$$, where $U$ and $V$ are complex vetorial spaces of ...
1
vote
0answers
46 views

Maximizing the product of first Eigenvalues of rank-1 hermitian matrices

Suppose we have $L$ complex vectors $\mathbf{a}_{l}$ with dimension $N\times 1$ I want to solve this optimization problem $\mathbf{x}_{\mathrm{opt}}=\arg ...
0
votes
1answer
178 views

How to calc $\min ||J\Delta\tau + D||_*$

How to calculate $$ \min_{\tau} ||J_1 \tau_1 + \cdots + J_p \tau_p + D ||_* $$ where $\tau_1, \cdots, \tau_p \in \mathbb{R}$ $J_1, \cdots, J_p, D \in \mathbb{R}^{m \times n}$ $||\cdot||_*$ is sum ...
0
votes
2answers
49 views

Minimizing the following objective function with matrices

Suppose $A$ and $B$ are known matrices, and we are to find matrix $X$ that minimizes the following function, $$\frac{1}{2}||X||^2+\frac{1}{2}||X^TAX-B||^2$$ Taking the relevant derivative w.r.t $X$ ...
0
votes
2answers
44 views

Minimize Frobenius norm with constraints

As a follow-up on my previous question, I would like to solve the following optimization problem: $\min \Vert MA-B \Vert_F^2-x^HMy\;\;s.t.\;\;M^HM=I$ where $A$ and $B$ are $N\times L$ complex ...
0
votes
1answer
31 views

A simple optimization problem

$$f = x^Tx$$ $$g = Ax-b $$ The constraint is $Ax-b = 0$ I calculated $J' = f'+\lambda g'$ which is $2x^T+\lambda A^T = 0 $ and $Ax-b=0$ . I dont know what to do next please help me out .
3
votes
1answer
60 views

Minimize Frobenius norm with unitary constraint

I am trying to find a unitary tramsformation, $M$, that minimizes $\Vert MA-B \Vert_F^2$ where $A$ and $B$ are $N\times L,\;L\ge N$. I know how to solve it without the unitary constraint. I thought ...
0
votes
1answer
48 views

Largest eigenvalue of symmetric matrix

I am trying to understand why the $\lambda_{\max}$ function is convex given an $n\,x\,n$ symmetric matrix, let's call it $A$. I know from elementary property of eigenvalues that all the eigenvalues of ...
2
votes
1answer
60 views

A Matrix Optimization Problem

Given an $n\times d$ matrix $Y$, I am looking for an algorithm to find an $n$-vector $\mathbf{v}$ ($0\le \mathbf{v}_i\le 1$ for all $i$) that minimizes $\sum_{i:X_i<0}X_i$, where $X:= \mathbf{v} ...
0
votes
0answers
11 views

Matrix Optimal Strategy Problem

(B) What is the expected value of the game for R if the bank R always chooses TV and bank C uses its optimum strategy? E= _ (type fully reduced fraction or mixed number) (C) What is the expected ...
1
vote
1answer
61 views

How to show this algorithm on positive semidefinite matrices converges to a global maximum determinant

I'm dealing with an algorithm which is supposed to converge to the maximum determinant of certain positive semidefinite matrices. The problem is that we have such a matrix, and we vary certain ...
1
vote
1answer
47 views

Minimum Eigenvalue of the Rank One update to a Positive Semi-Definite matrix

Let $\mathbf{A}$ be a $N\times N$ positive semi-definite hermitian matrix. Let $\mathbf{b}$ be a $N\times 1$ complex vector. For any given constant $t$, I interested in the minimum eigenvalue of the ...
0
votes
1answer
33 views

Sample Variance in Principle Components Analysis

I was reading this Why is the eigenvector of a covariance matrix equal to a principal component?. And in the top answer, the poster mentions that if the covariance matrix of the original data points ...
0
votes
1answer
35 views

Positive, Negative definite and indefinite matrix

A symmetric matrix is positive definite iff all eigenvalues are positive. I have been given a 3X3 symmetric matrix. I have calculated the eigenvalues two of which are negative. Does this mean this ...
0
votes
0answers
64 views

Minimizing the Kullber-Leibler divergence between two multivariate normal distributions

Take two zero-mean multivariate normal distributions: $p=\mathcal{N}(\mathbf{0},\boldsymbol\Sigma)$ and $q=\mathcal{N}\left(\mathbf{0},\left(\mathbf{A}^{T} \boldsymbol\Omega ...
1
vote
1answer
73 views

Finding minimum of the trace of the matrix equals finding maximum of the trace of the inverse matrix?

Let $K$ be a positive definite, symmetric matrix. Let $C$ be a nondegenerate matrix of the same order. Elements of $K$ and $C$ depend on some parameter $a.$ Is it true to say that $$ ...
1
vote
0answers
80 views

Area optimization: Packing rectangles inside rectangle

Background: I am scrambling to figure out the optimization algorithm to build sprite image, which is essentially a big container rectangular image, with multiple rectangular images. I have found an ...
3
votes
2answers
62 views

Matrix which when multiplied, gives a maximal minimum of elements of result.

I'm working on an optimization problem and am stuck at this particular step. Let $\bf{A}$ be a matrix with 4 columns and a finite number of rows, consisting of elements which are either 0 or 1. Let ...
1
vote
1answer
63 views

What is matrix inequality such as $A>0$ or $A\succ 0$?

I am trying to gather here different meanings of the same symbol, inequality symbol or the succ symbol. I find many other use them so many different ways. Sometimes, $A>0$ means $\bar x^T A \bar x ...
0
votes
0answers
31 views

Help with Optimization Problem

Can someone please help me with this optimization problem? I am clueless! :(
0
votes
0answers
25 views

How to get a low rank solution?

Given an optimization problem with a non-zero semi-definite matrix variable $X$, how can I get a low rank solution? To add any penalty in the objective? i.e. min $f(X)$ s.t. $g(X)=0$; $h(X)<0$; ...
0
votes
2answers
59 views

gradient descent with respect to a matrix

I am trying to solve a maximize a scalar function f(X), where X is a matrix. I want to solve this using gradient descent, I have taken the derivative of f(X) w.r.t X. This seems a naive question, but ...
0
votes
0answers
30 views

Optimization objective modification for matrix factorization.

I have the following optimization objective: Here A is an mXn user-item rating matrix. W is a nXn weight vector that I am trying to learn. beta and lambda are parameters passed in. ...
1
vote
0answers
28 views

Decomposition of a symmetric semi-definite matrix into sums of sparse symmetric semi-definite matrix

I'll first provide the background. Let $x\in\mathbb{R}^N$ be decomposed into $n$ non-overlapping blocks of variables $x^{(1)},\ldots,x^{(n)}$. We say that $f:\mathbb{R}^N\rightarrow\mathbb{R}$ is ...
1
vote
1answer
307 views

Deducing that a matrix is indefinite using only its leading principal minors

$A$ is indefinite iff $A$ fits none of the above criteria. Equivalently, $A$ has both positive and negative eigenvalues. Also equivalently, $x^TAx$ is positive for at least one $x$ and ...
0
votes
1answer
91 views

Low-rank matrix approximation in terms of entry-wise $L_1$ norm

According to the Eckart–Young theorem, the low-rank matrix approximation problem $$\min_{\tilde{A}} \quad \| A - \tilde{A} \|_F \quad \text{s.t.} \quad \text{rank}(\tilde{A}) \le r$$ is given by the ...
0
votes
0answers
51 views

DFP rank-two update formula

when I am studying the DFP rank-two update formula, described as: $$B_{k+1}=(I-\rho_{k}y_{k}s_{k}^{T})B_{k}(I-\rho_{k}s_{k}y_{k}^{T})+\rho_{k}y_{k}y_{k}^{T},$$ where $$\rho_{k} = ...
3
votes
1answer
195 views

What are non-orthogonal eigenvectors?

Given a symmetric matrix $A$, the maximum of the trace, $Tr(Z^TAZ)$ under the assumption that $Z^TZ=I$ occurs when $Z$ has the eigenvectors of $A$, as $Tr(U^TAU)= \lambda_1 +\lambda_2+...\lambda_ d$ ...
1
vote
0answers
36 views

How to solve linear system of equations in 1 and inf-norm?

I have the problem to find a linear program that is equivalent to solving the problem that finds a minimum for $||Ax-b||_1$ and $||Ax-b||_{\infty}$. We defined a linear program as follows: $min_{x} ...
1
vote
1answer
32 views

Minimization of $\text{tr} (W^TMW)-\text{tr}(NW)$ subject to $W^TW=I$

Is there a closed-form solution for finding W that minimizes the objective function: $\text{tr} (W^TMW)-\text{tr}(NW)$ subject to $W^TW=I$ where $M$ and $N$ are fixed matrices. I find it difficult to ...
3
votes
2answers
96 views

Maximize the determinant

Over the class $S$ of symmetric $n$ by $n$ matrices such that the diagonal entries are +1 and off diagonals are between $-1$ and $+1$ (inclusive/exclusive), is $$\max_{A \in S} \det A = \det(I_n)$$ ...
0
votes
1answer
50 views

Extremum of a multidimensional quadratic function

I have the following function: $$ g(h) = h'\Sigma\Sigma'h-h'm-r, $$ where $h$ is a vector in $\mathbb{R}^M$, $\Sigma$ is a $M\times K$ matrix such that $\Sigma\Sigma'$ is positive definite and has ...
0
votes
1answer
56 views

Monotonically Increasing Mapping?

$\mathbf{h}_1, \mathbf{h}_2\in\mathbb{C}^{n}$ are given column vectors and $a>0$ is a given constant. Consider the matrix ...
1
vote
1answer
156 views

Estimate Euler angles between rotated coordinate system via Newton-method based on position vectors

I've got $N$ position vectors $\mathbf{a}_i = \begin{pmatrix} a_{i,x} \\ a_{i,y} \\ a_{i,z} \end{pmatrix}$ in one coordinate system and $N$ corresponding position vectors $\mathbf{b}_i = ...
0
votes
1answer
53 views

Minimisation of Concave Function

$f\left(\mathbf{x}\right):\mathbb{R}_+^n\rightarrow\mathbb{R}_+$ is a concave monotonically increasing function to be minimised over the feasible region $\sum_{i=1}^n x_i=1$ and $x_i\geq ...
1
vote
1answer
120 views

Optimization problem to find an optimal matrix

I need to find a $n\times m$ matrix $N$ with binary values $(0,1)$ which will maximize an objective function. N(i,j)=0 or 1 indicates whether jth offer is made to ith customer $m$ represents number ...
6
votes
2answers
133 views

What is the maximum possible value of determinant of a matrix whose entries either 0 or 1?

My question is simply the title: What is the maximum possible value of determinant of a matrix whose entries either 0 or 1 ?
3
votes
1answer
189 views

Finding the smallest subset of a set of vectors which contains another vector in the span

Consider a set $S=\{ \underline{v_1},\dots , \underline{v_n} \} $ of vectors of dimension $d<n$. Suppose for some vector $\underline{b}$ that the solution space for the matrix equation $\left[ ...
2
votes
2answers
92 views

positive semidefiniteness: a psd matrix substracted by another rank 1 psd matrix

Given that $A$ is a positive semidefinite matrix, $x$ is a vector, $\lambda_0 \in [0, +\infty) $ is a real non-negative number. I want to know the answer to the following optimization problem. $$ ...
0
votes
0answers
55 views

Least square distance between matrices under linear constraints

I have got a set of $n$ elements and a square matrix I = $ \begin{bmatrix} I_{11} & I_{12} & \dots & I_{1n} \\ I_{21} & I_{22} & \dots & I_{2n} \\ \vdots & \vdots & ...
0
votes
1answer
82 views

Notation minimum of a column vector

I'd like to know the notation to express the minimum of a column vector. Is this notation correct? \begin{equation} \min \left[\matrix{ \left|b_{n}-b_{n+1}\right| \cr ...
2
votes
1answer
58 views

Ask a question about an example in a course note on optimization problem with equality constraint

I have two difficulties on understanding the solution to an example in a course I took this semester on optimization. This example is given to illustrate the usage of Lagrange multiplier method ...
0
votes
1answer
80 views

Efficient (approximate) projection onto the special orthogonal group

I need to carry out an optimization on the special orthogonal group $SO(n)$. For the line search I use a simple back-projection method $$\mbox{minimize}_\tau f(\pi(X+\tau Z))$$ where $X\in SO(n)$ ...
0
votes
2answers
270 views

Transpose of matrix inverse: $(AA^T)^{-1}A^Tb \stackrel{?}{=} (A^TA)^{-1}A^Tb$

Given the matrix equation: $$ x^TA^TA = b^TA $$ I'm trying to find the least squares solution (i.e.; trying to minimize $r=||Ax-b||$). The matrix $A$ is not necessarily symmetric. When I solve it ...
2
votes
0answers
59 views

Use of low rank approximation of a matrix

I am trying to figure out why do we need a low rank approximation of a matrix. Why is it used and where? Any insights?
0
votes
1answer
97 views

Solve: This System of equations for $X$ (does a real solution, exist?)

How can I solve $AX + diag(X)[I-c]=0$ for $X$? All matrices have real entries, $diag(X)$ is a diagonal matrix with the diagonal entries being the diagonal entries of $X$, and $c$ is a constant, real ...