In　recent　years　Wi-Fi　fingerprinting　has　attracted　much　attention　in　indoor　localization　because　of　the　availability　of　high-quality　signal　and　pervasive　deployment　of　wireless　LANs.　For　fingerprint-based　localization,　however,　offline　site　survey　is　usually　time-consuming　and　labor-intensive.　Therefore,　reducing　the　burden　of　offline　site　survey　becomes　an　important　issue　for　fingerprint-based　indoor　localization.　In　this　paper,　using　a　low-tubal-rank　tensor　to　model　Wi-Fi　fingerprints　of　all　reference　points　(RPs),　we　propose　an　adaptive　sampling　scheme　via　approximate　volume　sampling　to　improve　reconstruction　accuracy　of　radio　map　with　reduced　expenditure.　We　propose　a　rank-increasing　strategy　to　effectively　estimate　the　rank　of　the　underlying　fingerprint　tensor　to　alleviate　the　computation　burden　for　tensor　completion.　We　provide　a　theoretical　foundation　to　analyze　the　proposed　scheme　and　derive　the　performance　bounds　in　terms　of　sample　complexity　and　reconstruction　error.　We　prove　that　the　proposed　scheme　can　achieve　a　relative　error　guarantee.　Finally,　we　validate　the　effectiveness　of　the　proposed　scheme　through　extensive　simulations　using　both　synthetic　and　real　datasets.　The　simulation　results　demonstrate　that　the　proposed　scheme　is　able　to　not　only　reduce　reconstruction　error　and　improve　localization　accuracy　but　also　reduce　running　time　compared　to　the　state-of-the-art　schemes.　©　2014　IEEE.