Optimization over the set of matrices $X$ that satisfy $X^\top B X = I_p$, referred to as the generalized Stiefel manifold, appears in many applications involving sampled covariance matrices such as the canonical correlation analysis (CCA), independent component analysis (ICA), and the generalized eigenvalue problem (GEVP). Solving these problems is typically done by iterative methods that require a fully formed $B$. We propose a cheap stochastic iterative method that solves the optimization problem while having access only to random estimates of $B$. Our method does not enforce the constraint in every iteration; instead, it produces iterations that converge to critical points on the generalized Stiefel manifold defined in expectation. The method has lower per-iteration cost, requires only matrix multiplications, and has the same convergence rates as its Riemannian optimization counterparts that require the full matrix $B$. Experiments demonstrate its effectiveness in various machine learning applications involving generalized orthogonality constraints, including CCA, ICA, and the GEVP.
相關內容
In this note we show examples of total Boolean functions that depend on $n$ variables and have spectral sensitivity $\Theta(\sqrt{\log n})$, which is asymptotically minimal.
Let $G$ be a graph of a network system with vertices, $V(G)$, representing physical locations and edges, $E(G)$, representing informational connectivity. A \emph{locating-dominating (LD)} set $S \subseteq V(G)$ is a subset of vertices representing detectors capable of sensing an "intruder" at precisely their location or somewhere in their open-neighborhood -- an LD set must be capable of locating an intruder anywhere in the graph. We explore three types of fault-tolerant LD sets: \emph{redundant LD} sets, which allow a detector to be removed, \emph{error-detecting LD} sets, which allow at most one false negative, and \emph{error-correcting LD} sets, which allow at most one error (false positive or negative). In particular, we determine lower and upper bounds for the minimum density of these three fault-tolerant locating-dominating sets in the \emph{infinite king grid}.
We propose a method for estimating a log-concave density on $\mathbb R^d$ from samples, under the assumption that there exists an orthogonal transformation that makes the components of the random vector independent. While log-concave density estimation is hard both computationally and statistically, the independent components assumption alleviates both issues, while still maintaining a large non-parametric class. We prove that under mild conditions, at most $\tilde{\mathcal{O}}(\epsilon^{-4})$ samples (suppressing constants and log factors) suffice for our proposed estimator to be within $\epsilon$ of the original density in squared Hellinger distance. On the computational front, while the usual log-concave maximum likelihood estimate can be obtained via a finite-dimensional convex program, it is slow to compute -- especially in higher dimensions. We demonstrate through numerical experiments that our estimator can be computed efficiently, making it more practical to use.
We study the classic Text-to-Pattern Hamming Distances problem: given a pattern $P$ of length $m$ and a text $T$ of length $n$, both over a polynomial-size alphabet, compute the Hamming distance between $P$ and $T[i\, .\, . \, i+m-1]$ for every shift $i$, under the standard Word-RAM model with $\Theta(\log n)$-bit words. - We provide an $O(n\sqrt{m})$ time Las Vegas randomized algorithm for this problem, beating the decades-old $O(n \sqrt{m \log m})$ running time [Abrahamson, SICOMP 1987]. We also obtain a deterministic algorithm, with a slightly higher $O(n\sqrt{m}(\log m\log\log m)^{1/4})$ running time. Our randomized algorithm extends to the $k$-bounded setting, with running time $O\big(n+\frac{nk}{\sqrt{m}}\big)$, removing all the extra logarithmic factors from earlier algorithms [Gawrychowski and Uzna\'{n}ski, ICALP 2018; Chan, Golan, Kociumaka, Kopelowitz and Porat, STOC 2020]. - For the $(1+\epsilon)$-approximate version of Text-to-Pattern Hamming Distances, we give an $\tilde{O}(\epsilon^{-0.93}n)$ time Monte Carlo randomized algorithm, beating the previous $\tilde{O}(\epsilon^{-1}n)$ running time [Kopelowitz and Porat, FOCS 2015; Kopelowitz and Porat, SOSA 2018]. Our approximation algorithm exploits a connection with $3$SUM, and uses a combination of Fredman's trick, equality matrix product, and random sampling; in particular, we obtain new results on approximate counting versions of $3$SUM and Exact Triangle, which may be of independent interest. Our exact algorithms use a novel combination of hashing, bit-packed FFT, and recursion; in particular, we obtain a faster algorithm for computing the sumset of two integer sets, in the regime when the universe size is close to quadratic in the number of elements. We also prove a fine-grained equivalence between the exact Text-to-Pattern Hamming Distances problem and a range-restricted, counting version of $3$SUM.
In a graph bisection problem, we are given a graph $G$ with two equally-sized unlabeled communities, and the goal is to recover the vertices in these communities. A popular heuristic, known as spectral clustering, is to output an estimated community assignment based on the eigenvector corresponding to the second smallest eigenvalue of the Laplacian of $G$. Spectral algorithms can be shown to provably recover the cluster structure for graphs generated from certain probabilistic models, such as the Stochastic Block Model (SBM). However, spectral clustering is known to be non-robust to model mis-specification. Techniques based on semidefinite programming have been shown to be more robust, but they incur significant computational overheads. In this work, we study the robustness of spectral algorithms against semirandom adversaries. Informally, a semirandom adversary is allowed to ``helpfully'' change the specification of the model in a way that is consistent with the ground-truth solution. Our semirandom adversaries in particular are allowed to add edges inside clusters or increase the probability that an edge appears inside a cluster. Semirandom adversaries are a useful tool to determine the extent to which an algorithm has overfit to statistical assumptions on the input. On the positive side, we identify classes of semirandom adversaries under which spectral bisection using the _unnormalized_ Laplacian is strongly consistent, i.e., it exactly recovers the planted partitioning. On the negative side, we show that in these classes spectral bisection with the _normalized_ Laplacian outputs a partitioning that makes a classification mistake on a constant fraction of the vertices. Finally, we demonstrate numerical experiments that complement our theoretical findings.
We study the discrete quantum walk on a regular graph $X$ that assigns negative identity coins to marked vertices $S$ and Grover coins to the unmarked ones. We find combinatorial bases for the eigenspaces of the transtion matrix, and derive a formula for the average vertex mixing matrix $\AMM$. We then find bounds for entries in $\AMM$, and study when these bounds are tight. In particular, the average probabilities between marked vertices are lower bounded by a matrix determined by the induced subgraph $X[S]$, the vertex-deleted subgraph $X\backslash S$, and the edge deleted subgraph $X-E(S)$. We show this bound is achieved if and only if the marked vertices have walk-equitable neighborhoods in the vertex-deleted subgraph. Finally, for quantum walks attaining this bound, we determine when $\AMM[S,S]$ is symmetric, positive semidefinite or uniform.
We consider temporal numeric planning problems $\Pi$ expressed in PDDL2.1 level 3, and show how to produce SMT formulas $(i)$ whose models correspond to valid plans of $\Pi$, and $(ii)$ that extend the recently proposed planning with patterns approach from the numeric to the temporal case. We prove the correctness and completeness of the approach and show that it performs very well on 10 domains with required concurrency.
This paper presents an algorithmic method for generating random orthogonal matrices \(A\) that satisfy the property \(A^t S A = S\), where \(S\) is a fixed real invertible symmetric or skew-symmetric matrix. This method is significant as it generalizes the procedures for generating orthogonal matrices that fix a general fixed symmetric or skew-symmetric bilinear form. These include orthogonal matrices that fall to groups such as the symplectic group, Lorentz group, Poincar\'e group, and more generally the indefinite orthogonal group, to name a few. These classes of matrices play crucial roles in diverse fields such as theoretical physics, where they are used to describe symmetries and conservation laws, as well as in computational geometry, numerical analysis, and number theory, where they are integral to the study of quadratic forms and modular forms. The implementation of our algorithms can be accomplished using standard linear algebra libraries.
Let $P$ be a set of points in the plane and let $m$ be an integer. The goal of Max Cover by Unit Disks problem is to place $m$ unit disks whose union covers the maximum number of points from~$P$. We are interested in the dynamic version of Max Cover by Unit Disks problem, where the points in $P$ appear and disappear over time, and the algorithm must maintain a set \cDalg of $m$ disks whose union covers many points. A dynamic algorithm for this problem is a $k$-stable $\alpha$-approximation algorithm when it makes at most $k$ changes to \cDalg upon each update to the set $P$ and the number of covered points at time $t$ is always at least $\alpha \cdot \opt(t)$, where $\opt(t)$ is the maximum number of points that can be covered by m disks at time $t$. We show that for any constant $\varepsilon>0$, there is a $k_{\varepsilon}$-stable $(1-\varepsilon)$-approximation algorithm for the dynamic Max Cover by Unit Disks problem, where $k_{\varepsilon}=O(1/\varepsilon^3)$. This improves the stability of $\Theta(1/\eps^4)$ that can be obtained by combining results of Chaplick, De, Ravsky, and Spoerhase (ESA 2018) and De~Berg, Sadhukhan, and Spieksma (APPROX 2023). Our result extends to other fat similarly-sized objects used in the covering, such as arbitrarily-oriented unit squares, or arbitrarily-oriented fat ellipses of fixed diameter. We complement the above result by showing that the restriction to fat objects is necessary to obtain a SAS. To this end, we study the Max Cover by Unit Segments problem, where the goal is to place $m$ unit-length segments whose union covers the maximum number of points from $P$. We show that there is a constant $\varepsilon^* > 0$ such that any $k$-stable $(1 + \varepsilon^*)$-approximation algorithm must have $k=\Omega(m)$, even when the point set never has more than four collinear points.
A matrix $\Phi \in \mathbb{R}^{Q \times N}$ satisfies the restricted isometry property if $\|\Phi x\|_2^2$ is approximately equal to $\|x\|_2^2$ for all $k$-sparse vectors $x$. We give a construction of RIP matrices with the optimal $Q = O(k \log(N/k))$ rows using $O(k\log(N/k)\log(k))$ bits of randomness. The main technical ingredient is an extension of the Hanson-Wright inequality to $\epsilon$-biased distributions.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191