User bart - MathOverflow

Answer by Bart for Bandwidth reduction of multiple matrices

2012-04-07T08:25:00Z

If you use the typical reorderings (like reverse Cuthill-McKee ordering), $P^T A P$ will have a smaller bandwidth (in general, not tridiagonal though). Since $P$ is a permutation matrix, all $P^T D_i P$ will remain diagonal too.

Bart

Answer by Bart for Numerical linear algebra: how to compute $b^TA^{-1}b$ efficiently

2011-08-27T14:19:03Z

This is possibly an answer from a practical point of view: If you use the CG method for solving $x=A^{-1}b$ then $b^T A^{-1}b$ can be obtained along the way. However, it has been shown that computing $b^T A^{-1}b$ during the iteration can converge faster than first solving for $x$ and then multiplying $b^T x$. See "Z. Strakos and P. Tichy, On efficient numerical approximation of the bilinear form c*A-1b , SIAM Journal on Scientific Computing (SISC), 33, 2011, pp. 565-587" and the references therein for the positive definite case.

Smoothness along rays sufficient for global smoothness

2011-08-24T09:20:48Z

Hi,

Suppose I have a function $f:\mathbb{R}^d \to \mathbb{R}$ and I know that $f$ is smooth ($C^\infty$) along each ray $t \mapsto f(td)$ on $t \in [-\epsilon, \epsilon]$ and all directions $d \in \mathbb{R}^d$.

Is smoothness along these rays sufficient for $f$ to be smooth around $0$ as a multivariate function (all partial derivatives exist)?

Thanks.

Answer by Bart for Is any $(n-1)\times (n-1)$ submatrix of an $n \times n$ Vandermonde matrix invertible?

2011-04-07T13:42:15Z

No. Take $n=2$ and $\alpha_1=0, \alpha_2=1$. Then the Vandermonde matrix \[ \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \] is invertible, but the upper-right submatrix is not.

Answer by Bart for Explanation of $y = x \exp(\triangle)$ for a Lie Group

2011-04-01T17:11:59Z

The answer of Theo basically says it all what the exponential is concerned, but I maybe can shed some light regarding the optimization perspective.

Let $M$ be your Lie group and suppose it is a subgroup of $\textrm{GL}_n$. Now, if you want to solve \[ \min f(x) \quad \textrm{s.t. $x \in M$} \] by an iterative method, one usually uses a so-called smooth retraction map \[ R_x: T_x M \to M. \] to replace your current approximation $x$ to $x_+ := R_x(\Delta)$. Think for example of doing a line-search $R_x(-t \textrm{ grad}_x f)$ for $t>0$ where $\textrm{ grad}_x f$ is the Riemannian gradient of $f$.

(The retraction map has to fulfill some properties, in order for this to work, likes smoothness and being a first-order approximation of the geodesics (see below).)

Due to the left (or right) action of a Lie group on itself by multiplication, the exponential mapping at the identity $\exp$ can be transported to get a retraction at $x$ as $x\exp$. As Theo already explained, $\exp$ does not need to be a global diffeomorphism, but that is not needed for optimization, since we perform updates locally.

Another typical choice for $R_x$ are the geodesics in $x$. For some metrics, the $\exp$ coincides with the geodesics (for instance, bi-invariant metrics), but not always. One can also use cheaper alternatives for $R_x$ if your are only concerned with optimization. A nice reference for this retraction-based optimization on manifolds (and so, also Lie groups) is http://press.princeton.edu/titles/8586.html .

Answer by Bart for Find the point on the Stiefel Manifold that is closest to a matrix

2011-03-31T18:29:42Z

Are you sure you need the distance function $\|XX^T-YY^T\|_2$? If not, the solution to \[ \min \{\|E\|: E \in \mathbb{R}^{m \times n}, (X+E)^T(X+E) = I \} \] for the 2-norm and the Frobenius norm is the polar decomposition; see, e.g., section 4 in http://www.maths.man.ac.uk/~nareports/narep161.pdf .

Maybe you do want $\|XX^T-YY^T\|_2$ as distance function because of the equivalence by the orthogonal group. In that case you maybe want to rephrase your problem on the Grassmann manifold on linear subspaces. In fact, the Stiefel manifold with the orthogonal group factored out is exactly the Grassmann manifold. There is a nice paper about this: http://dx.doi.org/10.1137/S0895479895290954 .

Orbits of semi-algebraic actions

2011-03-31T09:24:40Z

Hello all,

I recently came across the following Theorem in Gibson (Singular points of smooth mappings, 1979). Since I haven't seen this result somewhere else and this reference is not so widespread, I was wondering if it is correct, known or trivial?

Theorem B4 in Gibson79: Let $\phi: G \times M \to M$ be a smooth action of a Lie group $G$ on a smooth manifold $M$. Suppose that the action is semi-algebraic (i.e., the graph of $\phi$ is a semi-algebraic set). Then all the orbits are smooth submanifolds of $M$.

(Smooth means $C^\infty$; smooth submanifold means a differential manifold that is embedded.)

The proof goes as follows. The orbit at $x \in M$ is semi-algebraic by Tarski-Seidenberg. Every non-void semi-algebraic has at least a one neighbourhood where it is a submanifold in $M$. Since orbits are homogeneous by the action of $G$, this neigbourhood extends to the whole orbit.

Thanks!

Do surjections exist which are not submersions on a set of measure non-zero.

2011-03-30T21:28:12Z

Let $f: M \to N$ be a smooth maps between smooth manifolds. Then $f$ is a submersion (by definition) if its differential is also surjective. Now suppose $f$ is surjective. Is it possible that the surjective map $f$ fails to be a submersion on a set in $N$ of measure non-zero? If so, what is such a map?

Suppose the manifolds $M$ and $N$ are non-compact. Does this change the previous answer?

Thanks!

Comment by Bart

2011-08-24T14:19:46Z

Apparently, in the published version there is the condition that the k-th partial derivative of $f \circ u$ needs to be smaller than $C k! / r^k$ for some $r>0$.

Comment by Bart

2011-08-24T13:35:46Z

Thanks Willie. Looking at the Boman paper, demanding smoothness along only analytic curves is indeed not sufficient. It turns out that when $f \circ u$ is real analytic for every real analytic curve $u$, that $f$ is real analytic. See "An Ontology of Directional Regularity Implying Joint Regularity" published in Real Analysis Exchange, available at math.wustl.edu/~sk/joint.pdf .

Comment by Bart

2011-08-24T12:15:55Z

That is indeed a nice counterexample. Would you happen to have a reference of this result of Jan Boman? In addition, would smoothness along all real analytic curves be sufficient too?

Comment by Bart

2011-04-04T08:34:07Z

@José: Thanks for the explanation! (Maybe you can specify in the answer that you consider the $G$-invariant metric.)

Comment by Bart

2011-04-03T16:35:50Z

@José, maybe I am missing something here, but I don't see what the positivity of the OP (orthogonal product?) has to do with $H$ being a subgroup of the orthogonal group? Any $G/H$ with $H$ a closed Lie subgroup of $G$ is a homogeneous space. For sure, one can put a positive OP on $G/H$.

Comment by Bart

2011-04-03T09:25:04Z

I don't think you can find a reductive split for any Riemannian homogeneous space since $H$ does not need to be compact. It only needs to be closed in $G$.