Tensor decompositions have been successfully applied to multidimensional data recovery. However, classical tensor decompositions are not suitable for emerging spatio-irregular multidimensional data (i.e., spatio-irregular tensor), whose spatial domain is non-rectangular, e.g., spatial transcriptomics data from bioinformatics and semantic units from computer vision. By using preprocessing (e.g., zero-padding or element-wise 0-1 weighting), the spatio-irregular tensor can be converted to a spatio-regular tensor and then classical tensor decompositions can be applied, but this strategy inevitably introduces bias information, leading to artifacts. How to design a tensor-based method suitable for emerging spatio-irregular tensors is an imperative challenge. To address this challenge, we propose a learnable transform-assisted tensor singular value decomposition (LTA-TSVD) for spatio-irregular tensor recovery, which allows us to leverage the intrinsic structure behind the spatio-irregular tensor. Specifically, we design a learnable transform to project the original spatio-irregular tensor into its latent spatio-regular tensor, and then the latent low-rank structure is captured by classical TSVD on the resulting regular tensor. Empowered by LTA-TSVD, we develop spatio-irregular low-rank tensor completion (SIR-LRTC) and spatio-irregular tensor robust principal component analysis (SIR-TRPCA) models for the spatio-irregular tensor imputation and denoising respectively, and we design corresponding solving algorithms with theoretical convergence. Extensive experiments including the spatial transcriptomics data imputation and hyperspectral image denoising show SIR-LRTC and SIR-TRPCA are superior performance to competing approaches and benefit downstream applications.

This paper proposes a bi-level tensor decomposition (BLTD), properly exploiting the characterization advantages of tensor subspace representation (TSR) and tensor ring decomposition (TRD). More specifically, the first level is related to the decomposition of a third-order tensor into its TSR using the tensor-tensor product (t-product), and the second level performs TRD on the coefficient tensor obtained by TSR. Leveraging the proposed BLTD, we design a bi-level tensor nuclear norm (BLTNN)-based model for hyperspectral images (HSIs) denoising. To solve the model, we develop an efficient alternating direction method of multipliers (ADMM)-based algorithm. Experimental results demonstrate the superior performance of our method compared to existing methods.

Recently, tensor singular value decomposition (t-SVD) has emerged as a promising tool for hyperspectral image (HSI) processing. In the t-SVD, there are two key building blocks: (i) the low-rank enhanced transform and (ii) the accompanying low-rank characterization of transformed frontal slices. Previous t-SVD methods mainly focus on the developments of (i), while neglecting the other important aspect, i.e., the exact characterization of transformed frontal slices. In this letter, we exploit the potentiality in both building blocks by leveraging the Hierarchical nonlinear transform and the Hierarchical matrix factorization to establish a new Tensor Factorization (termed as H2TF). Compared to shallow counter partners, e.g., low-rank matrix factorization or its convex surrogates, H2TF can better capture complex structures of transformed frontal slices due to its hierarchical modeling abilities. We then suggest the H2TF-based HSI denoising model and develop an alternating direction method of multipliers-based algorithm to address the resultant model. Extensive experiments validate the superiority of our method over state-of-the-art HSI denoising methods.

In-memory key-value store (IMKVS) has gained great popularity in data centers. However, big data brings great challenges in performance and power consumption because of the general-purpose Von Neumann computer architecture. Remote direct memory access (RDMA) technology supporting zero-copy networking could partly alleviate the problem but is still not efficient for KVS. To overcome this problem, we present a flexible and ultra-low-latency IMKVS system named FULL-KV, based on a CPU-FPGA heterogeneous architecture. The FPGA serves as a KVS accelerator that can bypass the CPU and implement both the network stacks and the KVS processing with a highly parallel hardware architecture. The system latency of FULL-KV can achieve as low as 1.5μs/2.2μs for the PUT/GET operation, which is 3.0x/1.5x faster than current state-of-the-art hardware-based KVS systems. Besides, FULL-KV can support 4x larger values (up to 4M bytes). Given a total Ethernet bandwidth of 20Gbps, the peak throughput of the single-node FULL-KV can reach 26.0 million key-value operations per second (Mops). In the two-node test system with a commercial Ethernet switch, the peak throughput can reach 52Mops, manifesting the system scalability and practicability.

In recent years, a variety of methods for low-latency key-value store (KVS), such as remote direct memory access (RDMA), have been proposed. However, a majority of KVS systems do not support to access and query data stored in multiple versions, making them inapplicable to application scenarios like snapshot. In this paper, we present a low-latency multi-version in-memory KVS on an FPGA-CPU platform. In order to reduce latency, we store all keys into a hash table using cuckoo hashing on an FPGA board and organize each group of version-value pairs that are corresponded with the identical key into a B-tree in the host memory. The proposed architecture can perform put, get, delete, CAS, getPredecessor and range query operations within a B-tree. Every operation except range query can be completed bypassing the host CPU. The experimental results show that the average latency of get operation within a B-tree of 5 levels is less than 8?s which is at least 9x faster than other implementations with the help of CPU.

We study the problem of testing whether an unknown n -variable Boolean function is a k -junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0,1} n . Our first main result is that distribution-free k -junta testing can be performed, with one-sided error, by an adaptive algorithm that uses Õ( k 2 )/ϵ queries (independent of n ). Complementing this, our second main result is a lower bound showing that any non-adaptive distribution-free k -junta testing algorithm must make Ω(2 k /3 ) queries even to test to accuracy ϵ = 1/3. These bounds establish that while the optimal query complexity of non-adaptive k -junta testing is 2 Θ( k ) , for adaptive testing it is poly( k ), and thus show that adaptivity provides an exponential improvement in the distribution-free query complexity of testing juntas.

In-memory key-value store (KVS) is critical infrastructure in data centers and is facing challenges in performance and power consumption with the development of the big data technology, which mainly results from the low efficiency of the multi-level memory hierarchy of the CPU-based system. Remote direct memory access (RDMA) technology partly alleviates the problems, but it is still not efficient for KVS, especially for the PUT operation. In this paper, we present an ultra-low-latency and flexible in-memory KVS system based on the CPU-FPGA heterogeneous architecture, which leverages FPGA to serve as a KVS accelerator. We design a highly parallel accelerator architecture with several novel techniques, including memory pre-allocation, fragmentation processing, and decoupling design, to achieve ultra-low latency, high flexibility, efficiency, and scalability. The system workload can scale up with the storage capacity due to the decoupling design which stores the hash table in onboard DRAM memory and values in the host memory. For each KVS operation, at most one PCIe DMA is needed, which achieves high efficiency. Compared with current hardware-based KVS systems, the proposed one is more flexible, where the supported value range is 4x wider (from 1 byte to 4M bytes). In 10Gbps Ethernet, the peak throughput of the system can reach 13.6 million key-value operations per second (Mops), achieving nearly full utilization of the Ethernet bandwidth. The system latency can achieve as low as 1.2us for the PUT operation and 1.7us for the GET operation, which is 3.8x and 2.0x faster respectively than current state-of-the-art KVS systems.

We study the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0,1}n. Our first main result is that distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that uses Õ(k2)/є queries (independent of n). Complementing this, our second main result is a lower bound showing that any non-adaptive distribution-free k-junta testing algorithm must make Ω(2k/3) queries even to test to accuracy є=1/3. These bounds establish that while the optimal query complexity of non-adaptive k-junta testing is 2Θ(k), for adaptive testing it is poly(k), and thus show that adaptivity provides an exponential improvement in the distribution-free query complexity of testing juntas.

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function f :{0,1} n → {0,1} is a k -junta or ϵ-far from every k -junta must make Ω ˜ ( k 3/2 ) / ϵ) many queries for a wide range of parameters k and ϵ. Our result dramatically improves previous lower bounds and is essentially optimal since there is a known non-adaptive junta tester which makes Ω ˜ ( k 3/2 ) / ϵ queries. Combined with the known existence of an adaptive tester which makes O ( k log k + k /ϵ) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function f is a k-junta or epsilon-far from every k-junta must make ~Omega(k^{3/2}/ epsilon) many queries for a wide range of parameters k and epsilon. Our result dramatically improves previous lower bounds from [BGSMdW13,STW15], and is essentially optimal given Blais's non-adaptive junta tester from [Blais08], which makes ~O(k^{3/2})/epsilon queries. Combined with the adaptive tester of [Blais09] which makes O(k log k + k / epsilon) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.

We give an adaptive algorithm that tests whether an unknown Boolean function f : {0, 1}n→ {0, 1} is unate (i.e. every variable of f is either non-decreasing or non-increasing) or ε-far from unate with one-sided error and Õ(n3/4/ϵ2) many queries. This improves on the best adaptive O(n/ϵ)-query algorithm from Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova and Seshadhri [1] when 1/ϵ1/4. Combined with the Ω̃(n)query lower bound for non-adaptive algorithms with one-sided error of [2], [3], we conclude that adaptivity helps for the testing of unateness with one-sided error. A crucial component of our algorithm is a new subroutine for finding bi-chromatic edges in the Boolean hypercube called adaptive edge search.

We prove a lower bound of Ω(n1/3) for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function f:{0,1}n→ {0,1} is monotone versus far from monotone. This improves the recent lower bound of Ω(n1/4) for the same problem by Belovs and Blais (STOC'16). Our result builds on a new family of random Boolean functions that can be viewed as a two-level extension of Talagrand's random DNFs.

We improve both upper and lower bounds for the distribution-free testing of monotone conjunctions. Given oracle access to an unknown Boolean function f: {0, 1}n → {0, 1} and sampling oracle access to an unknown distribution over {0, 1}n, we present an Õ(n1/3/∊5)-query algorithm that tests whether f is a monotone conjunction versus ∊-far from any monotone conjunction with respect to . This improves the previous best upper bound of Õ(n1/2/∊) by Dolev and Ron [DR11], when 1/∊ is small compared to n. For some constant ∊0 > 0, we also prove a lower bound of for the query complexity, improving the previous best lower bound of by Glasner and Servedio [GS09]. Our upper and lower bounds are tight, up to a polylogarithmic factor, when the distance parameter ∊ is a constant. Furthermore, the same upper and lower bounds can be extended to the distribution-free testing of general conjunctions, and the lower bound can be extended to that of decision lists and linear threshold functions.