A1GM method improves efficiency in reconstructing missing data using KL divergence.
problem Efficiently reconstructing missing data in matrices.
method Fast non-gradient-based rank-1 NMF using KL divergence.
result A1GM outperforms gradient methods in efficiency with competitive reconstruction errors.
Gradient Descent with small random initialization solves rank-1 matrix completion efficiently.
problem Matrix completion for rank-1 symmetric matrices.
method Gradient Descent with small random initialization.
result Gradient Descent converges to the ground truth for rank-1 symmetric matrix completion.
Paper presents a rank-1 approximation method for natural policy gradients in deep RL.
problem Computing natural gradients requires inverting the Fisher Information Matrix, which is computationally expensive.
method Develops a rank-1 approximation to the inverse Fisher Information Matrix for efficient natural policy optimization.
result The rank-1 approximation converges faster and has similar sample complexity to stochastic policy gradient methods.
A new bandit algorithm finds the max entry of a rank-1 matrix efficiently.
problem Online learning with unobserved values in matrix products.
method Rank1Elim algorithm for stochastic rank-1 bandits.
result Rank1Elim achieves linear regret bound in K+L, 1/Δ, and logn. PSMM method optimizes matrix sufficient dimension reduction.
problem Feature matrices with row- and column-wise interpretations require efficient dimension reduction.
method PSMM method converts matrix problem into classification problems using rank-1 normal matrix.
result PSMM outperforms existing methods and provides strong interpretability.
A framework for efficiently solving structured matrix factorization problems.
problem Efficiently representing real-world data with structured vectors.
method Generalized greedy pursuit framework and atomic power method for non-convex subproblems.
result Linear convergence for approximation over arbitrary dictionaries.
Rank-1 BNNs improve efficiency and scalability of Bayesian neural nets.
problem Underfitting and lack of scalability in Bayesian neural networks.
method Propose a rank-1 parameterization of BNNs and use mixture approximate posteriors.
result Rank-1 BNNs achieve state-of-the-art performance across various datasets.
Optimizes matching in weighted graphs with semi-bandit sampling.
problem Finding optimal pairings in weighted graphs with sequential sampling.
method Leverages rank-1 assumption on adjacency matrix to reduce sample complexity and regret.
result Achieves linear dependency in the number of vertices for sample complexity and regret.
Four algorithms improve sparse tensor BR1Approx with theoretical guarantees.
problem Sparse tensor best rank-1 approximation.
method Four approximation algorithms exploiting multilinearity and sparsity.
result Theoretical worst-case approximation lower bounds for all algorithms.
A scalable distributed S-LSR1 algorithm reduces communication costs.
problem Efficiently scaling S-LSR1 for large-scale distributed optimization.
method Proposes DS-LSR1, a communication-efficient variant of S-LSR1.
result DS-LSR1 scales well in problem dimension and data points.
Algorithm recovers factors of rank-1 matrices from noisy measurements.
problem Estimating factors of a rank-1 matrix from nonlinearly transformed and noisy measurements.
method Alternating minimization with random initialization and analysis of empirical error recursion.
result Algorithm converges geometrically fast from random initialization, with sharp guarantees.
Consider a movie recommendation system where apart from the ratings information, side information such as user's age or movie's genre is also available. Unlike standard matrix completion, in this setting one should be able to predict inductively on new users/movies. In this paper, we study the problem of inductive matr…
We analyze the structure of covariance matrices under graph constraints.
problem Analyzing the structure of covariance matrices under graph constraints.
method We explore the algebraic structure of the solution space of convex optimization problem Constrained Minimum Trace Factor Analysis (CMTFA) under a latent star topology.
result CMTFA can have either a rank 1 or a rank n-1 solution, with conditions for both.
New compression technique reduces RNN size by 2-4x without sacrificing accuracy.
problem Large and compute-intensive RNNs on edge devices with run-time constraints.
method Hybrid Matrix Decomposition (HMD) splits weight matrix into unconstrained and rank-1 blocks.
result HMD achieves 2-4x compression with faster run-time and similar accuracy.
New method predicts and optimizes matrix recovery from noisy measurements.
problem Recovering rank-1 matrices from Gaussian measurements with noise.
method Stochastic prox-linear iterative algorithm with trajectory predictions.
result The method converges linearly with accurate predictions of error.
Estimates rank-one spikes from heavy-tailed noise using self-avoiding walks.
problem Estimating rank-one spikes from heavy-tailed noise.
method Self-avoiding walks to count and estimate the spikes.
result Optimal estimation up to the BBP threshold for heavy-tailed noise.
In this paper we consider the Poisson algebraic structure associated with a classical r-matrix, i.e. with a solution of the modified classical Yang--Baxter equation. In Section 1 we recall the concept and basic facts of the r-matrix type Poisson orbits. Then we describe the r-matrix Poisson pencil (i.e the pair o…
Gradient descent aligns weights in deep linear networks for binary classification.
problem Aligning weights in deep linear networks for binary classification.
method Gradient descent applied to strictly decreasing loss functions.
result Normalized weight matrices align across layers, converging to the maximum margin solution.
This work shows that a simple local search can recover true principal components in non-negative rank-1 RPCA.
problem Recovering true principal components in non-negative rank-1 robust principal component analysis with noisy measurements.
method Using the Burer-Monteiro approach to cast RPCA as a non-convex and non-smooth ℓ1 optimization problem. result The low-dimensional formulation of symmetric and asymmetric positive rank-1 RPCA has a unique global solution and no spurious local solutions.
Proposes a new algorithm for click feedback in search results.
problem Learning to predict user clicks based on relevance and position.
method Developed a Bernoulli rank-1 bandit learning problem and proposed Rank1ElimKL to improve performance. result Rank1ElimKL outperforms Rank1Elim in various scenarios, including real-world data.
PSI-LinUCB improves scalability for large recommender systems.
problem Efficiently training and inferring for large action spaces in recommender systems.
method Represent inverse design matrix as diagonal + low-rank correction, derive stable rank-1 and batched updates, use projector-splitting integrator.
result Demonstrated effectiveness on recommender system datasets, achieving scalable training and inference.
No non-product Hessian rank 1 affine homogeneous hypersurfaces exist in dimensions 5 and above.
problem Identifying non-product Hessian rank 1 affine homogeneous hypersurfaces in higher dimensions.
method Developed a normal form for hypersurfaces under the affine group, up to order ≤ n+5, in any dimension n ≥ 2.
result Non-existence of non-product Hessian rank 1 affine homogeneous hypersurfaces in dimensions 5 and above.
Proves conditions for Fourier transforms in rank 1 symmetric spaces.
problem Understanding Fourier transform bounds in symmetric spaces.
method Proves sufficient and necessary conditions using Lipschitz and Fourier type integral conditions.
result Establishes bounds for Fourier transforms in rank 1 symmetric spaces with specific moduli of continuity.
Study shows dynamics of rank 1 orbifolds in flat surfaces.
problem Characterize dynamics of rank 1 affine invariant orbifolds.
method Analyzes M-isoperiodic foliations and their ergodic properties.
result Leaves of the isoperiodic foliation are either all closed or all dense.
Sharp isoperimetric inequalities for Neumann eigenvalues in symmetric spaces.
problem Finding bounds for eigenvalues of Neumann Laplacian on domains in symmetric spaces.
method Proving sharp inequalities for eigenvalues in compact and noncompact rank-1 symmetric spaces.
result Generalization of previous results for hyperbolic space and symmetric spaces.
Study Morse-Novikov cohomology for 1-forms on rank 1 manifolds.
problem Analyzing cohomology of closed one-forms on manifolds.
method Explicit computation and discussion of locally conformally symplectic manifolds.
result Explicit computation for Inoue surface S^0.
A simple sketch improves online eigenvector and SDP problems.
problem Online eigenvector and semidefinite programming problems.
method Randomized mirror projection and mirror descent analysis.
result Regret bounds similar to MMW with reduced complexity.
Study on renormalized volume for hyperbolic 3-manifolds, including rank-1 cusps.
problem Defining and studying renormalized volume for geometrically finite hyperbolic 3-manifolds.
method Defined renormalized volume, proved variation formula, and showed convergence for degenerating metrics.
result Renormalized volume converges to the limiting metric for certain families of convex co-compact hyperbolic metrics.
Right inverse found for Cartan differential in rank-1 symmetric spaces.
problem Finding a right inverse for the Cartan differential in symmetric spaces.
method Integral operator approach to the Cartan differential on exact forms.
result Extension of Gauss linking integral to rank-1 symmetric spaces.
The paper describes hyperkähler geometry of cotangent bundles using rank-1 projections.
problem Understanding hyperkähler geometry of cotangent bundles via algebraic methods.
method Algebraic description via the scheme of rank-1 projections, isometric embeddings, and generalizations.
result Explicit isometric embeddings and generalizations of hyperkähler geometry.
GD learns matrix solutions incrementally, revealing insights into generalization.
problem Matrix sensing problem of recovering low-rank matrices from linear measurements.
method Fine-grained analysis of GD dynamics for matrix sensing.
result GD follows an incremental learning procedure, solving matrices of increasing ranks.
Volume comparison theorem for rank 1 symmetric spaces proved.
problem Volume comparison for symmetric spaces of non-compact type.
method Normalized Ricci--DeTurck flow to analyze volume functional and derive monotonicity properties.
result Volume comparison theorem established for rank 1 symmetric spaces of non-compact type.
Research examines rank 1 abelian subgroups in 2-knot groups.
problem Identifying rank 1 abelian normal subgroups in 2-knot groups.
method Analyzes properties of 2-knot groups and their subgroups.
result Either 2-knot groups have no minimal Seifert hypersurface or they are topologically equivalent to a specific example.
Simple AMP algorithm robust to adversarial corruption.
problem Robust approximate message passing in spiked matrix models.
method Spectral pre-processing combined with robust spectral initialization.
result AMP output is close to correct for corrupted data.
Proposes a new method for high-dimensional data analysis.
problem Sparse PCA limitations in high-dimensional data analysis.
method Low-rank principal eigenmatrix analysis, matricized rank-truncated power method.
result Competitive empirical performance in synthetic data sets.
Defines foliation criterion for dense isoperiodic leaves in rank 1 affine orbifolds.
problem Dynamics of isoperiodic leaves in rank 1 affine invariant suborbifolds.
method Defines foliation FM and establishes density criterion.
result Establishes criterion for density of isoperiodic leaves.
Study shows renormalized volume is locally convex for certain hyperbolic 3-manifolds.
problem Understanding critical points of renormalized volume in hyperbolic 3-manifolds.
method Introduced a modified definition of renormalized volume that is additive under gluing, and studied local properties.
result Renormalized volume is locally convex around critical points in acylindrical geometrically finite hyperbolic 3-manifolds with rank-1 cusps.
Study on diagonal and separating coordinates for symmetric spaces of rank 1.
problem Existence and nonexistence of diagonal and separating coordinates for symmetric spaces of rank 1.
method Generalization of results by Gauduchon and Moroianu, 2020, and analysis of constant sectional curvature and orthogonal separation of variables.
result Diagonal coordinates exist if and only if the symmetric space has constant sectional curvature.
Improves detection of low-rank signals from noisy data matrices.
problem Statistical detection of low-rank signals in noisy data matrices.
method Entrywise pre-transforming data matrix for non-Gaussian noise, sharp phase transition thresholds, central limit theorem for linear spectral statistics, hypothesis test.
result Improves detection of low-rank signals from noisy data matrices, generalizing known results.
Based on a new atomic norm, we propose a new convex formulation for sparse matrix factorization problems in which the number of nonzero elements of the factors is assumed fixed and known. The formulation counts sparse PCA with multiple factors, subspace clustering and low-rank sparse bilinear regression as potential ap…
Paper proves conditions for nonconvex matrix recovery to avoid spurious local minima.
problem Ensuring no spurious local minima in nonconvex matrix recovery.
method Sharp restricted isometry bounds proof technique.
result RIP constant of δ < 1/2 is necessary and sufficient for exact recovery.
We establish the proportionality principle between the Riemannian volume and locally finite simplicial volume for Q-rank 1 locally symmetric spaces covered by products of hyperbolic spaces, giving the first examples for manifolds whose cusp groups are not necessarily amenable. Also, we give a simple direct proof of the…
Study of Martin boundary for rank 1 manifolds with nonpositive curvature.
problem Understanding the Martin boundary for specific types of manifolds.
method Modification of Ancona's argument to analyze the geometric and Martin boundaries.
result A residual set in the geometric boundary corresponds naturally to a subset of the Martin boundary.
We use generalised cross--ratios to prove the Ptolemaean inequality and the Theorem of Ptolemaeus in the setting of the boundary of symmetric Riemannian spaces of rank 1 and of negative curvature.
For a given lattice, we establish an equivalence involving a closed zone of the corresponding Voronoi polytope, a lamina hyperplane of the corresponding Delaunay partition and a quadratic form of rank 1 being an extreme ray of the corresponding L-type domain.
STARK learns structured dictionaries for tensor data.
problem Representing multidimensional data with structured dictionaries.
method Solves a convex relaxation of a nonconvex rank-1 tensor recovery problem.
result Empirical results show promising performance for tensors of any order.
Sign-RIP improves robust low-rank matrix recovery by preserving norms even with corrupted measurements.
problem Robust low-rank matrix recovery in the presence of corrupted measurements.
method Proposed Sign-RIP, a robust restricted isometry property.
result Sign-RIP guarantees uniform convergence of subdifferentials in robust low-rank matrix recovery.
Paper shows moderate RIP is insufficient for avoiding spurious local minima in matrix recovery.
problem The need for moderate RIP to avoid spurious local minima in matrix recovery.
method Analyzes the necessity of RIP constants and provides counterexamples.
result Counterexamples show spurious local minima exist even with moderate RIP.