Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [positive-semidefinite]

Relating to a symmetric $n\times n $ real matrix $(M)$ such that the scalar $x^TMx\ge 0\ \forall x\in \Bbb{R}^n\backslash \{0\}$

4
votes
0answers
4k views

Checking positive semidefiniteness in MATLAB

Let $\mathbf{A}$ be a $n\times n$ matrix. I want to check in MATLAB if it is PSD or not. Which tests, in MATLAB, should I do for this purpose? I know that if $\mathbf{A}$ is PSD then following holds ...
3
votes
0answers
416 views

Constrained quadratic programming with positive semidefinite matrix

I am facing the following problem: $$\begin{equation*} \begin{aligned} & \underset{z}{\text{minimize}} & & \textbf{z}^T \textbf{Q} \textbf{z} + \textbf{b}^T \textbf{z}\\ & \text{...
2
votes
0answers
11 views

How to show for positive semi-definite, there exist $x \in \mathbb{R}^n$ such that $Bx+c = 0$ and and $\|x\| \leq \Delta$?

Let $B \in \mathbb{R}^{n \times n}$ be symmetric and positive semi-definite such that $B = U\Lambda U^T$, where $U = [u_1,\cdots,u_n]^T$ is an orthogonal matrix with $u_i \in \mathbb{R}^n$, and $\...
2
votes
0answers
62 views

Semidefinite optimization

I'm a physicist and I'm working on a problem that can be reduced to a SDP problem. My problem is: is there a theorem that assures that the result of an optimization saturates the constraint instead of ...
2
votes
0answers
42 views

Minimum of $\langle Ax,x \rangle - 2 \langle b,x \rangle$.

In exercise 5 of section 0 of Fundamentals of convex analysis by Hiriart-Urrut, Lemaréchal, we're supposed to prove that if a self-adjoint linear operator $A:\mathbb{R}^n \rightarrow \mathbb{R}^n$ is ...
2
votes
0answers
78 views

1-norm and symmetry

Define the fidelity function for positive operators by $F(\rho, \sigma) = \lVert \sqrt{\rho}\sqrt{\sigma}\rVert_1$. Here, $\lVert\cdot\rVert_1$ is the Schatten 1-norm and defined as $\lVert A\rVert_1 =...
2
votes
0answers
36 views

Positive semi-definite Matrix 3

I am trying to find the condition on $K$ under which the matrix $$ M=\begin{bmatrix} K-P &KWL^c\\ L^cWK & L^cWKWL^c \end{bmatrix} $$ is positive semidefinite. Where $L^c$ is Laplacian Matrix, ...
2
votes
0answers
21 views

Relating the eigenvalues of two positive semi-definite matrices

Let $A$ be an $n \times n$ positive semi-definite matrix, and let $B$ be an $m \times n$ matrix. Can one say anything relating the eigenvalues of $M_1 := BAB^\top$ and $M_2 := BA^2 B^\top$? In ...
2
votes
0answers
36 views

On approximation of maximization of quadratic function over a convex set

Given a convex function $f : \mathbb{R}^n \to [0,\infty)$. Let $L = \left\lbrace x \in \mathbb{R}^n \mid f(x) \leq 1 \right\rbrace$ be it's sub-level set and suppose that $L$ is not empty as well as ...
2
votes
0answers
53 views

Critetion for positive definiteness of a continuous kernel

Let $K\colon [a,b]\times[a,b]\to\mathbb{R}$ be a continuous function (kernel), such that for any quadratically integrable function $x\colon[a,b]\to\mathbb{R}$ the following condition holds: $$+\infty&...
2
votes
0answers
132 views

Nonlinear optimization over positive semidefinite cone

I am trying to solve the following optimization problem (analytically) $$P^* := \arg\min_{P\succeq 0} \,\,\left( (1-\beta)\log|P+I|+\beta\log|P+R| \right)$$ where all matrices are in $\mathbb{R}^{n \...
2
votes
0answers
186 views

Proof of Strong Duality theorem for semidefinite programs vis Farkas Lemma

I am following Lovasz' notes on semidefinite programming and I want to understand the proof of the Strong Duality theorem using the Farkas Lemma. Lovasz only proves one part of it, and I'm trying to ...
2
votes
0answers
167 views

Does Convolution preserve positive definiteness?

Let $A$ be a symmetric positive semi definite matrix, $A \in SPD^n$, and $K \in \mathbb{R}^{k\times k}$ a kernel. What are the necessary and sufficient conditions over $K$ that will make the ...
2
votes
0answers
119 views

Sufficient conditions for positive semidefiniteness of block matrix

$\newcommand{\Re}{\mathbb{R}}$ I'm looking for sufficient conditions that may guarantee positive semidefiniteness (PSD) of a block matrix $$A = \begin{bmatrix} A_{1,1} & \cdots & A_{1,n} \\ \...
2
votes
0answers
56 views

Condition for positive semidefiniteness for this special block matrix

Consider a finite matrix with the following structure $$ \left( \begin{array}{ccccc} 1 & \vec{u} & \vec{u} & \vec{u} &...\\ \vec{u}^T & X & P & ...
2
votes
0answers
52 views

Iterative test for positive semidefiniteness

I have block matrices of the form $$\begin{pmatrix} A & v \\ v^T & x \end{pmatrix}$$ with scalar $x$ that need to be tested for positive semidefiniteness or positive definiteness. According ...
2
votes
0answers
1k views

Proof of Sylvester's criterion for Hermitian matrices?

Can anyone provide a proof of Sylvester's criterion for positive definiteness for Hermitian matrices? All I can find is this proof and Wikipedia, both about real symmetric matrices.
2
votes
0answers
863 views

A trace inequality for the inverse of a real positive semidefinite Toeplitz matrix.

This might be a simple problem for some. Let there be a real positive semidefinite Toeplitz matrix $\mathbf{R}_m$ of dimension $m+1$. Denoting its diagonal elements as $a_0$, we have Tr$(\mathbf{R}_m)=...
1
vote
0answers
46 views

Can this matrix be negative definite?

Let $d = 12$ and $m = 6$, and denote by $0_n$ and $I_n$ the zero matrix and the identity matrix of size $n \times n$. Let $D_+ \in \mathbb{R}^{m \times m}$ be a diagonal matrix with positive ...
1
vote
0answers
12 views

Semidefinite Matrix in LINGO

Using LINGO, I need to enter the following block matrix as one of my constraints $ M= \left[ {\begin{array}{cc} 1 & x^T \\ x & X \\ \end{array} } \right] $ where x is an n by 1 ...
1
vote
0answers
50 views

Determinant of Hadamard product / sum of matrices (one diagonal)

I am trying to compute the determinant of $\boldsymbol{W}\odot \boldsymbol{S}$, where $\boldsymbol{S} \in PD(p)$ positive semidefinite matrix and $\boldsymbol{W}$ is a matrix whose diagonal entries $...
1
vote
0answers
14 views

Equivalence of semidefinite decomposition?

If we have an $n \times n$ positive semidefinite matrix $A$ and we have two decompositions such that $A = B B^T = C C^T$ for some $n \times n$ matrices $B$ and $C$. Is it true that $B$ and $C$ are ...
1
vote
0answers
109 views

Convexity of a Log Likelihood Function

Goal I would like to proof than the Negative Log Likelihood Function of Sample drawn from a Normal Distribution is convex. Below a Figure showing an example of such function: Motivation of this ...
1
vote
0answers
42 views

Is $E^T X E \preceq X$ if $X \succ 0$ and $\|E\|_F = 1$?

Let $E, X \in M_n(\mathbb R)$. $X \succ 0$ is positive definite and $\|E\|_F = 1$ where $\|\cdot\|_F$ denotes the Frobenius norm and no particular structure is assumed for $E$. I am trying to ...
1
vote
0answers
74 views

Nearest (with respect to weights) symmetric positive semidefinite matrix

I want to compute the nearest symmetric positive semidefinite matrix, similar as Higham did. But here also weights (given by an inverse co-variance matrix) should be taken into account. So the ...
1
vote
0answers
82 views

Relationship between the maximum eigenvalues of a matrix and its row-manipulated form

Let $A \in \mathbb{R}^{n \times n}$ be a symmetric positive semi-definite matrix with sum of each row equals to zero. Is my intuition true that the following inequality always hold? $$\lambda_{\...
1
vote
0answers
70 views

Positive definiteness of a multivariate polynomial function

Consider $x \in \Bbb{R}^n$ and suppose $f_m: \Bbb{R}^n \to \Bbb{R}$ which is defined as: $$f_m(x)=x^TAx+\alpha_{1}x_1^3+\alpha_{2}x_1^2x_2+\dots+\alpha_{r_1}x_n^3+\alpha_{r_1+1}x_1^4+\alpha_{r_1+2}...
1
vote
0answers
34 views

On the positve definiteness of a particular matrix and inverse

I have the following question. Let $M=BAC=M^T$ where $B\in\mathbb{R}^{m\times n}$, $C\in\mathbb{R}^{n\times m}$ and $A\in\mathbb{R}^{n\times n}$ invertible. Suppose $M$ is positive definite, $B$ is ...
1
vote
0answers
22 views

Is there a generalization of Araki-Lieb-Thirring inequality for four matrices?

It is known that $$ Tr[(AB)^n] \leq Tr (A^n B^n)$$ for $A$, $B$ positive semi-definite matrices. I am looking of a generalization of it for a product of $4$ positive semi-definite matrices of the the ...
1
vote
0answers
73 views

Gram matrix in a non-Euclidean space

The Gram matrix of a set of vectors $v_1,\dots,v_n$ with the usual Euclidean dot product is positive semidenifite. Suppose we have a symmetric matrix $A$ that is not positive semidefinite. Can we ...
1
vote
0answers
77 views

Laplace transform of a time varying positive semidefinite matrix

Consider a real, symmetric matrix $M(t)$ with time-varying elements. Each of the elements are zero for $t<0$ and positive for $t\geq 0$. Assume that $M(t)\succeq 0 \;\forall t\geq 0$ (i.e., it is ...
1
vote
0answers
35 views

Is this matrix product positive semidefinite?

Let $A,B\in\mathbb{C}^{p\times p}$ s.t. $A$ and $B$ are contractions and $I_p-AA^*$ and $BB^*$ both are positive semidefinite. I want to show that the matrix $$B(I_p-\sqrt{I_p-AA^*}\sqrt{I_p-AA^*}^*)B^...
1
vote
0answers
39 views

Weighted sums of positive semidefinite matrices are uniformly positive definite

Let $$A_n = \sum_{k=1}^{n} {\bf x}_k{\bf x}_k^T $$ where ${\bf x}_k$ is a $p \times 1$ vector. Suppose that there is a $N \in \mathbb N$ such that the family of matrices $\{ A_n \}$ is uniformly ...
1
vote
0answers
165 views

Projection of a Symmetric Matrix onto the space of Positive Semi-Definite Matrices

Consider the symmetric matrix $A\in\mathbb{R}^{n\times n}$ and the set C of all positive semi-definite matrices in $\mathbb{R}^{n\times n}$. Compute the projection of A onto C under the trace inner ...
1
vote
0answers
19 views

Show that this “1-bordered on top and left” matrix is positive semidefinite

Suppose $x_i\in\mathbb R^n$, $i=1,...,r$, $n>r$ and $x_i^Tx_j=0$ $\forall i\ne j$. I need to show that the matrix: $$ \sum_{k=1}^rx_kx_k^T-\textbf{11}^T\succeq 0. $$ It's easy to see that this is ...
1
vote
0answers
71 views

Solving Quadratic program for finding perfect matching in polynomial time

I am working on a variant of the assignment problem. The original assignment problem is as follows: We are given a bipartite graph with 2n vertices. Each edge has a non-negative integer weight $w_{i,j}...
1
vote
0answers
39 views

Finding bounds for a subset of the positive semidefinite cone

For a finite graph $G$, we say a matrix $B\in \mathbb{R}^{n\times n}$ represents $G$ if $B$ belongs to this set: $$\mathscr{B}=\{ B=(b_{ij}) \mid B\textrm{ is positive semidefinite with trace at most ...
1
vote
0answers
46 views

Is sum of inverse of max a kernel?

For $X$ be a nonempty set, a function $f :X\times X\to\mathbb R$ is called a kernel on $X$ if for all $m\in \mathbb N$ and all $x_1,\cdots,x_m \in X$ $$K_f\equiv\begin{bmatrix} f(x_1,x_1) & \cdots ...
1
vote
0answers
47 views

Sum/Product of two Infinitely Divisible matrices is Infinitely Divisible?

Definition - An entry wise non-negative matrix is said to be ID if $A^{or} = [a_{ij}^r]$ is PSD (positive semi definite) for all $r \geq 0$ i.e r being a non-negative real no. I need to prove or ...
1
vote
0answers
129 views

Relating the eigenvalues of a sum of outerproducts after applying a change of basis

Let $A_1 \in \mathbb{R}^{k\times k}$ be a symmetric and positive definite matrix. Let $x_1,x_2 \in \mathbb{R}^k$. Suppose I have the outer product $x_1 x_1^T$, from this post we know that $x_1$ is an ...
1
vote
0answers
34 views

Move an orthonormal frame towards principal axis of a p.s.d. matrix

Be $\mathcal{W}=\{W=(w_1|\dots|w_p)\in\mathbb{R}^{n\times p}\;:\;W^TW = I\}$ the set of $p$-dimensional orthonormal frames in $\mathbb{R}^n$. Consider $$ L(W) = \mathrm{tr}(MP_W) = \mathrm{tr}(MWW^T) ...
1
vote
0answers
85 views

Simple sufficient conditions for matrix positive semidefiniteness?

I need to show that a complicated $n \times n$ Hermitian matrix is positive semidefinite. I'm wondering if there are simple sufficient conditions that can be used to show this. For instance, if a ...
1
vote
0answers
23 views

Cholsky and Group Structure of Correlation matrices

If $X$ and $Y$ are correlation matrices which are strictly positive definite and $A$, and $B$ are their respective Cholsky decompositions. Then is $$ (AB)(AB)^{\star}, $$ again a strictly positive-...
1
vote
0answers
59 views

To Show This Is Positive Semidefinite

Given that $A\in M_n(\mathbb{R})$ is asymptotically stable and we define $P=\int_{0}^{\infty} e^{A^Tt}Qe^{At}dt$. I need to show that $P$ is positive semidefinite if $Q$ is positive semidefinite. $Q$ ...
1
vote
0answers
141 views

Expected eigenvalues of Gram matrix

Suppose $x \in R^p $ is drawn from some distribution $p(x)$ and $ A \in R^{N \times N} $ is gram matrix formed by dot product of $x_i, x_j$. What are the expected eigenvalues of $A$ when $N$ is finite?...
1
vote
0answers
99 views

positive semidefinite matrix.

Let $X$ be a set, and $d : X × X \to R$ a metric on $X$ (which means that verifies : $d(x, y) \geq 0$ ,$d(x, y) = 0$ if and only if $x = y$ ,$d(x, y) = d(y, x)$ and $d(x, y) \leq d(x, z) + d(z, y)$...
1
vote
0answers
633 views

Properties of Transition Matrix

Let $P$ be a markov transition matrix, that is, all entries of $P$ satisfies $0\le P_{ij}\le 1$, and row sums equal to $1$. Do we have the property that: $v^T(I-P)^2v\ge 0$, for any vector $v$ and I ...
1
vote
0answers
26 views

Semidefinite Programming Representations of two Inequalities

I have two inequalities including trigonometric polynomial: $$ (1) \qquad \sum_{|k| \leq n} u_k e^{i2\pi kt} \leq 1, $$ and $$ (2) \qquad \sum_{|k| \leq n} u_k e^{i2\pi kt} \geq 0. $$ Where the ...
1
vote
0answers
54 views

Second order condition for a unconstrained minium of a function

long time reader first time writer Okay my question is on the following statement: Let $f :R^n\rightarrow \mathbb{R}$ be a twice differentiable function , $\bar{x} \in Dom(f) $ with $\nabla{f(\bar{x}...
1
vote
0answers
37 views

Eigenvalues and positive semidefiniteness of a special matrix

Consider the following $(n+1)\times(n+1)$ real matrix $$A=\begin{pmatrix}a&p^t\\p&D\end{pmatrix},$$ where $D$ is an $n\times n$ diagonal matrix with strictly positive entries, $a>0$, and ...