# Tag Info

• 39.9k

### Is the pseudoinverse the same as least squares with regularization?

Yes, they are connected. The first problem is a special case of the second when $\lambda=0$, if the first problem has a unique solution (i.e., $\ker A = 0$), or if the second is also formulated as a ...
• 18.9k
Accepted

• 57.9k
Accepted

### Current state of the Komlos conjecture on vector balancing

For fixed $d$, one can actually achieve a bound independent of $n$. More precisely, $K=K(d)=O(\sqrt{d})$ is fine, uniformly in $n$. Proof : the unit ball of $\mathbb{R}^d$ can be covered by $2C^d$ ...
• 7,169
Accepted

### Is KL divergence $D(P||Q)$ strongly convex over $P$ in infinite dimension

$\newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\ep}{\varepsilon}$ Take any probability measures $P_0,P_1$ absolutely continuous with respect (w.r.) to $Q$. We shall prove the ...
• 106k
Accepted

### Is the pseudoinverse the same as least squares with regularization?

Here's one way to see this directly. I will assume that $A$ is $m \times n$. Let $$A = U \Sigma V^T$$ be the SVD for A. Recall that the regularized solution to the least squares problem $Ax = b$ is ...
• 2,495

### Bounding the spectral gap of a simple symmetric matrix

Let $x$ be the smallest nonzero eigenvalue of $A$. It is the reciprocal of the largest root of $$f(t)=-\det(t(D-aa^\top)-I),$$ where $D$ is the diagonal matrix. By the matrix determinant lemma, \begin{...
• 1,573

### Is the pseudoinverse the same as least squares with regularization?

TL;DR : Yes, the two problems are equivalent in the limit $\lambda \rightarrow 0$ ! One freely available reference is the following (excellent in my opinion) review paper : https://arxiv.org/abs/1110....
• 199

### Is this geometrically-defined minimum an algebraic number?

By Carathéodory's theorem, if the origin in $\mathbb{R}^{32}$ is contained in the convex hull of the set $$X_c = \{\,(x, y, x^2 - 1, \ldots, y^8 - 14) \mid -2 \le x, y \le 2, x + y \ge c\,\}$$ then ...
• 24.5k
Accepted

### Nuclear norm (convex) minimization with complex-valued matrices?

Yes, the same approach can be used for complex matrices, with the constraint becoming $\left[ \begin{array}{rr} W_{1} & X \\ X^{H} & W_{2} \\ \end{array} \right] \succeq 0$ Here, the ...
• 3,874

### An intuition for three different types of subgradients (proximal, regular, limiting)

This might not be a satisfying answer, but this is how I personally deal with this issue (at least in the topic of optimization). I think these concepts are not made for actually computing them but ...
• 181
Accepted

• 3,147
Accepted

### Inf of Jensen's inequality

Jensen's inequality $\int c(f)\,d\mu \ge c(\int f\,d\mu)$ is always equality when $f$ is constant, so you know that taking $dz/dt$ constant would saturate it. That means $z(t)$ has to be linear, and ...
• 28.6k
Accepted

• 2,226
Accepted

### L-infinity-norm regularized proximity problem

This is indeed a classic problem. Recall the more general problem of computing the prox operator of an lsc convex function $f$, i.e., \begin{equation*} \text{prox}_f(y) := \operatorname{argmin}\quad \...
• 28.2k

### algorithm for finding the minimizer of a almost convex function

How abou trying to apply the Golden Search algorithm?
• 332
Accepted

### Is the solution of this optimization problem always positive semidefinite?

No, it is not always attained at a positive semidefinite matrix. The simplest example I have been able to find to demonstrate this is as follows: \begin{align*} U = \{ (1,0), (0,1), \tfrac{1}{\...
• 5,463

Only top scored, non community-wiki answers of a minimum length are eligible