Improved stability for matrix recovery from rank-one measurements.
problem Phase retrieval problem of recovering rank-one positive semidefinite matrices.
method Developed a smoothing Newton method based on Bures-Wasserstein gradient descent.
result Superlinear convergence with rigorous guarantees and stable implementation.
Gradient descent solves rank-one matrix estimation problem with detailed time evolution analysis.
problem Estimating a rank-one symmetric matrix corrupted by noise.
method Gradient descent on a sphere, using local versions of the semi-circle law.
result Explicit formulas for the time evolution of the estimator and cost function, revealing phase transitions.
Study shows generative priors improve rank-one matrix recovery with optimal sample complexity.
problem Recovering a rank-one signal matrix from noisy data with additional prior information.
method Analysis of a nonlinear least squares objective with a favorable global optimization landscape.
result Established optimal sample complexity for generative priors in rank-one matrix recovery.
Study shows how fast a specific matrix completion method works.
problem Completing a rank-one matrix from a subset of revealed entries.
method Alternating minimization approach for matrix completion.
result Polynomial upper bound on convergence rate.
This paper sets fundamental limits for rank-one matrix estimation with varying noise levels.
problem Estimating a rank-one matrix from Gaussian observations with different noise levels across blocks.
method Novel reduction from heterogeneous noise to homogeneous noise, proving asymptotic error bounds.
result Asymptotically exact formulas for minimum mean-squared error in estimating rank-one matrix and factors.
Rank-one measurements limit feasible sets for low-rank PSD matrices.
problem Feasibility of PSD matrices under rank-one measurements.
method Characterization of feasible sets for PSD matrices given rank-one projections.
result Radius of feasible sets determines singleton solution sets for low-rank matrices.
Study quantifies performance gap between tensor and matrix-based approaches in nested matrix-tensor model.
problem Estimating a planted signal in a nested matrix-tensor model.
method Comparing tensor-based and matrix-based approaches for best rank-one approximation of tensor data.
result Derives precise algorithmic threshold for the unfolding approach and shows BBP-type transition behavior.
We consider the problem of estimation of a low-rank matrix from a limited number of noisy rank-one projections. In particular, we propose two fast, non-convex \emph{proper} algorithms for matrix recovery and support them with rigorous theoretical analysis. We show that the proposed algorithms enjoy linear convergence a…
Novel algorithm for Markov decision processes using rank-one approximation.
problem Solving planning and learning problems of Markov decision processes.
method Policy iteration with rank-one approximation of transition probability matrix.
result The proposed algorithm consistently outperforms first-order algorithms and their accelerated versions.
New algorithms improve rank one signal estimation from noisy data.
problem Estimating a rank one signal matrix from corrupted data with rotationally invariant noise.
method Developed approximate message-passing algorithms exploiting eigenvalues and iterates denoisers.
result Achieves optimal asymptotic estimation error among iterative algorithms.
Convex optimization method recovers low-rank matrices from rank-one projections efficiently.
problem Recovering low-rank matrices from limited rank-one projections.
method Unlifted convex optimization with subgradient method.
result The estimator succeeds with high probability if the number of measurements exceeds r2(d1+d2) up to logarithmic factors. We consider worker skill estimation for the single-coin Dawid-Skene crowdsourcing model. In practice, skill-estimation is challenging because worker assignments are sparse and irregular due to the arbitrary and uncontrolled availability of workers. We formulate skill estimation as a rank-one correlation-matrix completi…
New method unifies and formalizes data partitioning using a single vector.
problem Data partitioning and clustering methods.
method Rank-one matrix factorization and denoising of piecewise constant signals.
result Demonstrates robustness of denoising step in partitioning.
Estimates the probability of a random symmetric tensor being close to rank-one.
problem Estimating the probability of a random symmetric tensor being close to rank-one.
method Using Weyl's tube formula and techniques from Random Matrix theory, we study metric invariants of the real Veronese variety.
result Explicit formula for the reach and curvature coefficients of the real Veronese variety with respect to the Bombieri-Weyl metric.
Study on signal-plus-noise decomposition in nonlinear spiked random matrices.
problem Nonlinear spiked random matrix models with rank-one signal and noise.
method Signal-plus-noise decomposition and phase transition analysis.
result Identified precise phase transitions in signal components at critical thresholds.
We develop an efficient alternating framework for learning a generalized version of Factorization Machine (gFM) on steaming data with provable guarantees. When the instances are sampled from d dimensional random Gaussian vectors and the target second order coefficient matrix in gFM is of rank k, our algorithm conve…
Paper proposes a tensor model for clustering noisy multi-view data.
problem Clustering noisy multi-view data with non-uniform variances.
method Nested matrix-tensor model for best rank-one approximation.
result Theoretical results predict the exact accuracy of clustering.
Study on tensor signal estimation from incomplete data.
problem Estimating a rank-one tensor signal from noisy, incomplete data.
method Reduction to random matrix model for spectral analysis.
result Loss of performance due to incomplete data.
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.
AMP method reconstructs rank-one matrices from noisy data efficiently.
problem Reconstructing rank-one matrices with prior structural information from noisy observations.
method Approximate Message Passing (AMP) with random initialization.
result AMP from random initialization converges rapidly and globally.
New methods estimate covariance for matrix data without assuming fixed size or specific distributions.
problem Estimating covariance for high-dimensional matrix data without distributional assumptions.
method Unified framework for bandable covariance estimation with rank one approximation, robust to heavy-tailed data.
result Proposed estimators are rate-optimal and perform well in simulations and real applications.
Paper shows no spurious local minima in a specific matrix factorization problem.
problem Optimization of ℓ1-norm rank-one symmetric matrix factorization. method Second-order variational analysis to study the landscape of the problem.
result Any second-order stationary point is globally optimal.
New method solves matrix completion problems to certifiable optimality.
problem Certifying optimality in low-rank matrix completion.
method Disjunctive branch-and-bound scheme for convex relaxation.
result Decreases optimality gap by two orders of magnitude.
We consider the weak detection problem in a rank-one spiked Wigner data matrix where the signal-to-noise ratio is small so that reliable detection is impossible. We propose a hypothesis test on the presence of the signal by utilizing the linear spectral statistics of the data matrix. The test is data-driven and does no…
This work presents a novel approach to train invertible linear layers by adding rank-one perturbations.
problem Training invertible linear layers during optimization with gradient-based methods is challenging.
method Train rank-one perturbations and add them to weight matrices infrequently, keeping track of inverses and determinants.
result Invertible linear layers improve mixing and mode separation in normalizing flows.
Study linear perturbations of Spin(7) metrics, finding only rank one nilpotent matrices.
problem Linear perturbations of Spin(7) metrics.
method Applying the method of linear perturbations to Spin(7)-structures.
result Only rank one nilpotent matrices determine nontrivial perturbations.
Estimation of low-rank matrices is of significant interest in a range of contemporary applications. In this paper, we introduce a rank-one projection model for low-rank matrix recovery and propose a constrained nuclear norm minimization method for stable recovery of low-rank matrices in the noisy case. The procedure is…
New algorithms detect and estimate rank-one signals with prior directional information.
problem Detecting and estimating rank-one signals with directional prior information.
method Construct nonlinear Laplacians and examine top eigenvalues and eigenvectors.
result Nonlinear Laplacian algorithms outperform direct spectral methods for biased signals.
We propose a geometric assumption on nonnegative data matrices such that under this assumption, we are able to provide upper bounds (both deterministic and probabilistic) on the relative error of nonnegative matrix factorization (NMF). The algorithm we propose first uses the geometric assumption to obtain an exact clus…
This work presents GROUSE (Grassmanian Rank-One Update Subspace Estimation), an efficient online algorithm for tracking subspaces from highly incomplete observations. GROUSE requires only basic linear algebraic manipulations at each iteration, and each subspace update can be performed in linear time in the dimension of…
SON-NMF estimates nonnegative rank on-the-fly for NMF.
problem Estimating the nonnegative rank of data in NMF.
method Sum-of-norms (SON) regularization to reduce rank, combined with a first-order BCD algorithm.
result SON-NMF can automatically estimate the rank from data without prior knowledge.
In this paper, we study the adversarial robustness of subspace learning problems. Different from the assumptions made in existing work on robust subspace learning where data samples are contaminated by gross sparse outliers or small dense noises, we consider a more powerful adversary who can first observe the data matr…
We formulate and solve a tensor model using a latent-variable approach.
problem Parameter inference for Poisson canonical polyadic tensor models.
method Latent-variable formulation, Expectation-Maximization algorithms, Fisher information matrices.
result Derivation of Fisher information for PCP models, insights into model well-posedness.
Study TMF-valued TQFT for closed 3-manifolds using torsion linking pairings.
problem Explicit description of TMF-module state space for closed 3-manifolds.
method Construct canonical invariants and tokenization from torsion linking pairings.
result Explicit model for TMF-module state space in terms of rank-one TMF-module.
Extended Rank-One Theorem to special metric spaces.
problem Extending a theorem to new types of spaces.
method Applied to a new class of metric measure spaces.
result Rank-One Theorem proven for RCD(K,N) spaces. Incremental versions of batch algorithms are often desired, for increased time efficiency in the streaming data setting, or increased memory efficiency in general. In this paper we present a novel algorithm for incremental kernel PCA, based on rank one updates to the eigendecomposition of the kernel matrix, which is mo…
Gradient descent with growing learning rate enables learning non-linear features in neural networks.
problem Learning non-linear features in two-layer neural networks.
method Using gradient descent with a learning rate that grows with the sample size.
result Multiple rank-one components emerge, each corresponding to a specific polynomial feature.
In this paper, we show that the simplicial volume of Q-rank one locally symmetric spaces covered by the product of R-rank one symmetric spaces is strictly positive.
This expository paper details the theory of rank one Higgs bundles over a closed Riemann surface X and their relationship to representations of the fundamental group of X. We construct an equivalence between the deformation theories of flat connections and Higgs pairs. This provides an identification of moduli spaces a…
Constructs explicit p-harmonic functions on specific Lie groups.
problem Finding explicit p-harmonic functions on a specific class of Lie groups.
method Constructs explicit p-harmonic functions on rank-one Lie groups of Iwasawa type.
result Proves existence of proper p-harmonic functions on these groups.
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 the problem of estimating a low-rank matrix when its entries are perturbed by Gaussian noise. If the empirical distribution of the entries of the spikes is known, optimal estimators that exploit this knowledge can substantially outperform simple spectral approaches. Recent work characterizes the asymptotic acc…
We develop a notion of rank one properly convex domains (or Hilbert geometries) in the real projective space. This is in the spirit of rank one non-positively curved Riemannian manifolds and CAT(0) spaces. We define rank one isometries for Hilbert geometries and characterize them as being equivalent to contracting elem…
The study establishes uncertainty principles on harmonic manifolds of rank one.
problem Developing uncertainty principles for harmonic manifolds of rank one.
method Derivation of various uncertainty principles including Heisenberg, Morgen, Schrödinger, and Hömanders principles.
result Generalization of Hausdorff-Young inequality to harmonic manifolds of rank one.
Spectral methods are popular in detecting global structures in the given data that can be represented as a matrix. However when the data matrix is sparse or noisy, classic spectral methods usually fail to work, due to localization of eigenvectors (or singular vectors) induced by the sparsity or noise. In this work, we …
Study of asymmetric rank-one tensor models with non-Gaussian noise.
problem Analyzing maximum-likelihood estimators for asymmetric rank-one tensor models.
method Spectrally separated branch analysis, resolvent methods, cumulant expansions, Efron-Stein-type variance bounds.
result Asymptotic singular value and mode-wise alignments are robust to non-Gaussian noise.
Classifies foliations on specific symmetric spaces.
problem Classifying foliations on symmetric spaces of rank one.
method Orbit equivalence classification.
result Polar homogeneous foliations classified.
New approach speeds up DNA sequence alignment.
problem Efficiently estimating alignment scores for large sets of reads.
method Rank-one crowdsourcing models and multi-armed bandit algorithm.
result Adaptive algorithm identifies pairs with large alignment scores.